1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
#!/usr/bin/env ruby -w
# encoding: UTF-8
#
# = DataCache.rb -- The TaskJuggler III Project Management Software
#
# Copyright (c) 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014
# by Chris Schlaeger <cs@taskjuggler.org>
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of version 2 of the GNU General Public License as
# published by the Free Software Foundation.
#
require 'time'
require 'singleton'
class TaskJuggler
# These are the entries in the DataCache. They store a value and an access
# counter. The counter can be read and written externally.
class DataCacheEntry
attr_reader :unhashedKey
attr_accessor :hits
# Create a new DataCacheEntry for the _value_. We also store the unhashed
# key to be able to detect hash collisions. The access counter is set to 1
# to increase the chance that it is not flushed immedidate.
def initialize(unhashedKey, value)
@unhashedKey = unhashedKey
@value = value
@hits = 1
end
# Return the value and increase the access counter by 1.
def value
if @hits <= 0
@hits = 1
else
@hits += 1
end
@value
end
end
# This class provides a global data cache that can be used to store and
# retrieve values indexed by a key. The cache is size limited. When maximum
# capacity is reached, a certain percentage of the least requested values is
# dropped from the cache. The primary purpose of this global cache is to
# store values that are expensive to compute but may be need on several
# occasions during the program execution.
class DataCache
include Singleton
def initialize
resize
flush
# Counter for the number of writes to the cache.
@stores = 0
# Counter for the number of found values.
@hits = 0
# Counter for the number of not found values.
@misses = 0
# Counter for hash collisions
@collisions = 0
end
# For now, we use this randomly determined size.
def resize(size = 100000)
@highWaterMark = size
# Flushing out the least used entries is fairly expensive. So we only
# want to do this once in a while. The lowWaterMark determines how much
# of the entries will survive the flush.
@lowWaterMark = size * 0.9
end
# Completely flush the cache. The statistic counters will remain intact,
# but all data values are lost.
def flush
@entries = {}
end
if RUBY_VERSION < '1.9.0'
# Ruby 1.8 has a buggy hash key generation algorithm that leads to many
# hash collisions. We completely disable caching on 1.8.
def cached(*args)
yield
end
else
# _args_ is a set of arguments that unambigously identify the data entry.
# It's converted into a hash to store or recover a previously stored
# entry. If we have a value for the key, return the value. Otherwise call
# the block to compute the value, store it and return it.
def cached(*args)
key = args.hash
if @entries.has_key?(key)
e = @entries[key]
if e.unhashedKey != args
# Two different args produce the same hash key. This should be a
# very rare event!
@collisions += 1
yield
else
@hits += 1
e.value
end
else
@misses += 1
store(yield, args, key)
end
end
end
def to_s
<<"EOT"
Entries: #{@entries.size} Stores: #{@stores} Collisions: #{@collisions}
Hits: #{@hits} Misses: #{@misses}
Hit Rate: #{@hits * 100.0 / (@hits + @misses)}%
EOT
end
private
# Store _value_ into the cache using _key_ to tag it. _key_ must be unique
# and must be used to load the value from the cache again. You cannot
# store nil values!
def store(value, unhashedKey, key)
@stores += 1
if @entries.size > @highWaterMark
while @entries.size > @lowWaterMark
# How many entries do we need to delete to get to the low watermark?
toDelete = @entries.size - @lowWaterMark
@entries.delete_if do |foo, e|
# Hit counts age with every cleanup.
(e.hits -= 1) < 0 && (toDelete -= 1) >= 0
end
end
end
@entries[key] = DataCacheEntry.new(unhashedKey, value)
value
end
end
end
|
