|
1 """ |
|
2 This module contains multithread-safe cache implementations. |
|
3 |
|
4 All Caches have |
|
5 |
|
6 getorbuild(key, builder) |
|
7 delentry(key) |
|
8 |
|
9 methods and allow configuration when instantiating the cache class. |
|
10 """ |
|
11 from time import time as gettime |
|
12 |
|
13 class BasicCache(object): |
|
14 def __init__(self, maxentries=128): |
|
15 self.maxentries = maxentries |
|
16 self.prunenum = int(maxentries - maxentries/8) |
|
17 self._dict = {} |
|
18 |
|
19 def clear(self): |
|
20 self._dict.clear() |
|
21 |
|
22 def _getentry(self, key): |
|
23 return self._dict[key] |
|
24 |
|
25 def _putentry(self, key, entry): |
|
26 self._prunelowestweight() |
|
27 self._dict[key] = entry |
|
28 |
|
29 def delentry(self, key, raising=False): |
|
30 try: |
|
31 del self._dict[key] |
|
32 except KeyError: |
|
33 if raising: |
|
34 raise |
|
35 |
|
36 def getorbuild(self, key, builder): |
|
37 try: |
|
38 entry = self._getentry(key) |
|
39 except KeyError: |
|
40 entry = self._build(key, builder) |
|
41 self._putentry(key, entry) |
|
42 return entry.value |
|
43 |
|
44 def _prunelowestweight(self): |
|
45 """ prune out entries with lowest weight. """ |
|
46 numentries = len(self._dict) |
|
47 if numentries >= self.maxentries: |
|
48 # evict according to entry's weight |
|
49 items = [(entry.weight, key) |
|
50 for key, entry in self._dict.items()] |
|
51 items.sort() |
|
52 index = numentries - self.prunenum |
|
53 if index > 0: |
|
54 for weight, key in items[:index]: |
|
55 # in MT situations the element might be gone |
|
56 self.delentry(key, raising=False) |
|
57 |
|
58 class BuildcostAccessCache(BasicCache): |
|
59 """ A BuildTime/Access-counting cache implementation. |
|
60 the weight of a value is computed as the product of |
|
61 |
|
62 num-accesses-of-a-value * time-to-build-the-value |
|
63 |
|
64 The values with the least such weights are evicted |
|
65 if the cache maxentries threshold is superceded. |
|
66 For implementation flexibility more than one object |
|
67 might be evicted at a time. |
|
68 """ |
|
69 # time function to use for measuring build-times |
|
70 |
|
71 def _build(self, key, builder): |
|
72 start = gettime() |
|
73 val = builder() |
|
74 end = gettime() |
|
75 return WeightedCountingEntry(val, end-start) |
|
76 |
|
77 |
|
78 class WeightedCountingEntry(object): |
|
79 def __init__(self, value, oneweight): |
|
80 self._value = value |
|
81 self.weight = self._oneweight = oneweight |
|
82 |
|
83 def value(self): |
|
84 self.weight += self._oneweight |
|
85 return self._value |
|
86 value = property(value) |
|
87 |
|
88 class AgingCache(BasicCache): |
|
89 """ This cache prunes out cache entries that are too old. |
|
90 """ |
|
91 def __init__(self, maxentries=128, maxseconds=10.0): |
|
92 super(AgingCache, self).__init__(maxentries) |
|
93 self.maxseconds = maxseconds |
|
94 |
|
95 def _getentry(self, key): |
|
96 entry = self._dict[key] |
|
97 if entry.isexpired(): |
|
98 self.delentry(key) |
|
99 raise KeyError(key) |
|
100 return entry |
|
101 |
|
102 def _build(self, key, builder): |
|
103 val = builder() |
|
104 entry = AgingEntry(val, gettime() + self.maxseconds) |
|
105 return entry |
|
106 |
|
107 class AgingEntry(object): |
|
108 def __init__(self, value, expirationtime): |
|
109 self.value = value |
|
110 self.weight = expirationtime |
|
111 |
|
112 def isexpired(self): |
|
113 t = gettime() |
|
114 return t >= self.weight |