« back to all changes in this revision
Viewing changes to bzrlib/lru_cache.py
- browse files at revision 4197
- compare with another revision
- compare with revision 5452
- download diff
- download tarball
- view history from revision 4197
- Committer: Canonical.com Patch Queue Manager
- Date: 2009-03-24 17:01:50 UTC
- mfrom: (4178.3.7 lru_cache_linked_lst)
- Revision ID: pqm@pqm.ubuntu.com-20090324170150-9wtdpv5w7192zdwy
(jam) Improvements to LRUCache structure, use a double-linked-list
- files modified:
- bzrlib/lru_cache.py
added
removed
bzrlib/lru_cache.py
16
16
17
17
"""A simple least-recently-used (LRU) cache."""
18
18
19
from collections import deque
20
21
from bzrlib import symbol_versioning
19
from bzrlib import (
20
symbol_versioning,
21
trace,
22
)
23
24
25
class _LRUNode(object):
26
"""This maintains the linked-list which is the lru internals."""
27
28
__slots__ = ('prev', 'next', 'key', 'value', 'cleanup', 'size')
29
30
def __init__(self, key, value, cleanup=None):
31
self.prev = None
32
self.next = None
33
self.key = key
34
self.value = value
35
self.cleanup = cleanup
36
# TODO: We could compute this 'on-the-fly' like we used to, and remove
37
# one pointer from this object, we just need to decide if it
38
# actually costs us much of anything in normal usage
39
self.size = None
40
41
def __repr__(self):
42
if self.next is None:
43
next = None
44
else:
45
next = self.next.key
46
if self.prev is None:
47
prev = None
48
else:
49
prev = self.prev.key
50
return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
51
next, prev)
52
53
def run_cleanup(self):
54
if self.cleanup is not None:
55
self.cleanup(self.key, self.value)
56
self.cleanup = None
57
# Just make sure to break any refcycles, etc
58
self.value = None
22
59
23
60
24
61
class LRUCache(object):
33
70
DeprecationWarning)
34
71
after_cleanup_count = after_cleanup_size
35
72
self._cache = {}
36
self._cleanup = {}
37
self._queue = deque() # Track when things are accessed
38
self._refcount = {} # number of entries in self._queue for each key
73
# The "HEAD" of the lru linked list
74
self._most_recently_used = None
75
# The "TAIL" of the lru linked list
76
self._last_recently_used = None
39
77
self._update_max_cache(max_cache, after_cleanup_count)
40
78
41
79
def __contains__(self, key):
42
80
return key in self._cache
43
81
44
82
def __getitem__(self, key):
45
val = self._cache[key]
46
self._record_access(key)
47
return val
83
node = self._cache[key]
84
# Inlined from _record_access to decrease the overhead of __getitem__
85
# We also have more knowledge about structure if __getitem__ is
86
# succeeding, then we know that self._most_recently_used must not be
87
# None, etc.
88
mru = self._most_recently_used
89
if node is mru:
90
# Nothing to do, this node is already at the head of the queue
91
return node.value
92
elif node is self._last_recently_used:
93
self._last_recently_used = node.prev
94
# Remove this node from the old location
95
node_prev = node.prev
96
node_next = node.next
97
if node_prev is not None:
98
node_prev.next = node_next
99
if node_next is not None:
100
node_next.prev = node_prev
101
# Insert this node to the front of the list
102
node.next = mru
103
mru.prev = node
104
self._most_recently_used = node
105
node.prev = None
106
return node.value
48
107
49
108
def __len__(self):
50
109
return len(self._cache)
51
110
111
def _walk_lru(self):
112
"""Walk the LRU list, only meant to be used in tests."""
113
node = self._most_recently_used
114
if node is not None:
115
if node.prev is not None:
116
raise AssertionError('the _most_recently_used entry is not'
117
' supposed to have a previous entry'
118
' %s' % (node,))
119
while node is not None:
120
if node.next is None:
121
if node is not self._last_recently_used:
122
raise AssertionError('only the last node should have'
123
' no next value: %s' % (node,))
124
else:
125
if node.next.prev is not node:
126
raise AssertionError('inconsistency found, node.next.prev'
127
' != node: %s' % (node,))
128
if node.prev is None:
129
if node is not self._most_recently_used:
130
raise AssertionError('only the _most_recently_used should'
131
' not have a previous node: %s'
132
% (node,))
133
else:
134
if node.prev.next is not node:
135
raise AssertionError('inconsistency found, node.prev.next'
136
' != node: %s' % (node,))
137
yield node
138
node = node.next
139
52
140
def add(self, key, value, cleanup=None):
53
141
"""Add a new value to the cache.
54
142
55
Also, if the entry is ever removed from the queue, call cleanup.
56
Passing it the key and value being removed.
143
Also, if the entry is ever removed from the cache, call
144
cleanup(key, value).
57
145
58
146
:param key: The key to store it under
59
147
:param value: The object to store
60
148
:param cleanup: None or a function taking (key, value) to indicate
61
'value' sohuld be cleaned up.
149
'value' should be cleaned up.
62
150
"""
63
151
if key in self._cache:
64
self._remove(key)
65
self._cache[key] = value
66
if cleanup is not None:
67
self._cleanup[key] = cleanup
68
self._record_access(key)
152
node = self._cache[key]
153
node.run_cleanup()
154
node.value = value
155
node.cleanup = cleanup
156
else:
157
node = _LRUNode(key, value, cleanup=cleanup)
158
self._cache[key] = node
159
self._record_access(node)
69
160
70
161
if len(self._cache) > self._max_cache:
71
162
# Trigger the cleanup
72
163
self.cleanup()
73
164
165
def cache_size(self):
166
"""Get the number of entries we will cache."""
167
return self._max_cache
168
74
169
def get(self, key, default=None):
75
if key in self._cache:
76
return self[key]
77
return default
170
node = self._cache.get(key, None)
171
if node is None:
172
return default
173
self._record_access(node)
174
return node.value
78
175
79
176
def keys(self):
80
177
"""Get the list of keys currently cached.
87
184
"""
88
185
return self._cache.keys()
89
186
187
def items(self):
188
"""Get the key:value pairs as a dict."""
189
return dict((k, n.value) for k, n in self._cache.iteritems())
190
90
191
def cleanup(self):
91
192
"""Clear the cache until it shrinks to the requested size.
92
193
96
197
# Make sure the cache is shrunk to the correct size
97
198
while len(self._cache) > self._after_cleanup_count:
98
199
self._remove_lru()
99
# No need to compact the queue at this point, because the code that
100
# calls this would have already triggered it based on queue length
101
200
102
201
def __setitem__(self, key, value):
103
202
"""Add a value to the cache, there will be no cleanup function."""
104
203
self.add(key, value, cleanup=None)
105
204
106
def _record_access(self, key):
205
def _record_access(self, node):
107
206
"""Record that key was accessed."""
108
self._queue.append(key)
109
# Can't use setdefault because you can't += 1 the result
110
self._refcount[key] = self._refcount.get(key, 0) + 1
111
112
# If our access queue is too large, clean it up too
113
if len(self._queue) > self._compact_queue_length:
114
self._compact_queue()
115
116
def _compact_queue(self):
117
"""Compact the queue, leaving things in sorted last appended order."""
118
new_queue = deque()
119
for item in self._queue:
120
if self._refcount[item] == 1:
121
new_queue.append(item)
122
else:
123
self._refcount[item] -= 1
124
self._queue = new_queue
125
# All entries should be of the same size. There should be one entry in
126
# queue for each entry in cache, and all refcounts should == 1
127
if not (len(self._queue) == len(self._cache) ==
128
len(self._refcount) == sum(self._refcount.itervalues())):
129
raise AssertionError()
130
131
def _remove(self, key):
132
"""Remove an entry, making sure to maintain the invariants."""
133
cleanup = self._cleanup.pop(key, None)
134
val = self._cache.pop(key)
135
if cleanup is not None:
136
cleanup(key, val)
137
return val
207
# Move 'node' to the front of the queue
208
if self._most_recently_used is None:
209
self._most_recently_used = node
210
self._last_recently_used = node
211
return
212
elif node is self._most_recently_used:
213
# Nothing to do, this node is already at the head of the queue
214
return
215
elif node is self._last_recently_used:
216
self._last_recently_used = node.prev
217
# We've taken care of the tail pointer, remove the node, and insert it
218
# at the front
219
# REMOVE
220
if node.prev is not None:
221
node.prev.next = node.next
222
if node.next is not None:
223
node.next.prev = node.prev
224
# INSERT
225
node.next = self._most_recently_used
226
self._most_recently_used = node
227
node.next.prev = node
228
node.prev = None
229
230
def _remove_node(self, node):
231
if node is self._last_recently_used:
232
self._last_recently_used = node.prev
233
self._cache.pop(node.key)
234
# If we have removed all entries, remove the head pointer as well
235
if self._last_recently_used is None:
236
self._most_recently_used = None
237
node.run_cleanup()
138
238
139
239
def _remove_lru(self):
140
240
"""Remove one entry from the lru, and handle consequences.
142
242
If there are no more references to the lru, then this entry should be
143
243
removed from the cache.
144
244
"""
145
key = self._queue.popleft()
146
self._refcount[key] -= 1
147
if not self._refcount[key]:
148
del self._refcount[key]
149
self._remove(key)
245
self._remove_node(self._last_recently_used)
150
246
151
247
def clear(self):
152
248
"""Clear out all of the cache."""
164
260
if after_cleanup_count is None:
165
261
self._after_cleanup_count = self._max_cache * 8 / 10
166
262
else:
167
self._after_cleanup_count = min(after_cleanup_count, self._max_cache)
168
169
self._compact_queue_length = 4*self._max_cache
170
if len(self._queue) > self._compact_queue_length:
171
self._compact_queue()
263
self._after_cleanup_count = min(after_cleanup_count,
264
self._max_cache)
172
265
self.cleanup()
173
266
174
267
178
271
This differs in that it doesn't care how many actual items there are,
179
272
it just restricts the cache to be cleaned up after so much data is stored.
180
273
181
The values that are added must support len(value).
274
The size of items added will be computed using compute_size(value), which
275
defaults to len() if not supplied.
182
276
"""
183
277
184
278
def __init__(self, max_size=1024*1024, after_cleanup_size=None,
200
294
self._compute_size = compute_size
201
295
if compute_size is None:
202
296
self._compute_size = len
203
# This approximates that texts are > 0.5k in size. It only really
204
# effects when we clean up the queue, so we don't want it to be too
205
# large.
206
297
self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
207
298
LRUCache.__init__(self, max_cache=max(int(max_size/512), 1))
208
299
209
300
def add(self, key, value, cleanup=None):
210
301
"""Add a new value to the cache.
211
302
212
Also, if the entry is ever removed from the queue, call cleanup.
213
Passing it the key and value being removed.
303
Also, if the entry is ever removed from the cache, call
304
cleanup(key, value).
214
305
215
306
:param key: The key to store it under
216
307
:param value: The object to store
217
308
:param cleanup: None or a function taking (key, value) to indicate
218
'value' sohuld be cleaned up.
309
'value' should be cleaned up.
219
310
"""
220
if key in self._cache:
221
self._remove(key)
311
node = self._cache.get(key, None)
222
312
value_len = self._compute_size(value)
223
313
if value_len >= self._after_cleanup_size:
314
# The new value is 'too big to fit', as it would fill up/overflow
315
# the cache all by itself
316
trace.mutter('Adding the key %r to an LRUSizeCache failed.'
317
' value %d is too big to fit in a the cache'
318
' with size %d %d', key, value_len,
319
self._after_cleanup_size, self._max_size)
320
if node is not None:
321
# We won't be replacing the old node, so just remove it
322
self._remove_node(node)
323
if cleanup is not None:
324
cleanup(key, value)
224
325
return
326
if node is None:
327
node = _LRUNode(key, value, cleanup=cleanup)
328
self._cache[key] = node
329
else:
330
self._value_size -= node.size
331
node.size = value_len
225
332
self._value_size += value_len
226
self._cache[key] = value
227
if cleanup is not None:
228
self._cleanup[key] = cleanup
229
self._record_access(key)
333
self._record_access(node)
230
334
231
335
if self._value_size > self._max_size:
232
336
# Time to cleanup
242
346
while self._value_size > self._after_cleanup_size:
243
347
self._remove_lru()
244
348
245
def _remove(self, key):
246
"""Remove an entry, making sure to maintain the invariants."""
247
val = LRUCache._remove(self, key)
248
self._value_size -= self._compute_size(val)
349
def _remove_node(self, node):
350
self._value_size -= node.size
351
LRUCache._remove_node(self, node)
249
352
250
353
def resize(self, max_size, after_cleanup_size=None):
251
354
"""Change the number of bytes that will be cached."""
Loggerhead is a web-based interface for Breezy
Version: 2.0.1