← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/lru_cache.py

  • Committer: John Arbash Meinel
  • Date: 2009-03-22 19:05:03 UTC
  • mto: This revision was merged to the branch mainline in revision 4197.
  • Revision ID: john@arbash-meinel.com-20090322190503-wabx7fjrgarxx9c5
LRUCache is now implemented with a dict to a linked list,
rather than multiple dicts.

This turns out to be rather good for memory savings, and even a little
bit faster. Proper data structures FTW.

Still seeing ~500ms overhead versus a FIFO or dict, but some of that
is just the overhead you expect from having to maintain the LRU info.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/lru_cache.py
21
21
from bzrlib import symbol_versioning
22
22
 
23
23
 
 
24
class _LRUNode(object):
 
25
    """This maintains the linked-list which is the lru internals."""
 
26
 
 
27
    __slots__ = ('prev', 'next', 'key', 'value', 'cleanup', 'size')
 
28
 
 
29
    def __init__(self, key, value, cleanup=None):
 
30
        self.prev = None
 
31
        self.next = None
 
32
        self.key = key
 
33
        self.value = value
 
34
        self.cleanup = cleanup
 
35
        # TODO: We could compute this 'on-the-fly' like we used to, and remove
 
36
        #       one pointer from this object, we just need to decide if it
 
37
        #       actually costs us much of anything in normal usage
 
38
        self.size = None
 
39
 
 
40
    def __repr__(self):
 
41
        if self.next is None:
 
42
            next = None
 
43
        else:
 
44
            next = self.next.key
 
45
        if self.prev is None:
 
46
            prev = None
 
47
        else:
 
48
            prev = self.prev.key
 
49
        return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
 
50
                                     next, prev)
 
51
 
 
52
    def run_cleanup(self):
 
53
        if self.cleanup is not None:
 
54
            self.cleanup(self.key, self.value)
 
55
        self.cleanup = None
 
56
        # Just make sure to break any refcycles, etc
 
57
        self.value = None
 
58
 
 
59
 
24
60
class LRUCache(object):
25
61
    """A class which manages a cache of entries, removing unused ones."""
26
62
 
33
69
                                   DeprecationWarning)
34
70
            after_cleanup_count = after_cleanup_size
35
71
        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
 
72
        # The "HEAD" of the lru linked list
 
73
        self._most_recently_used = None
 
74
        # The "TAIL" of the lru linked list
 
75
        self._last_recently_used = None
39
76
        self._update_max_cache(max_cache, after_cleanup_count)
40
77
 
41
78
    def __contains__(self, key):
42
79
        return key in self._cache
43
80
 
44
81
    def __getitem__(self, key):
45
 
        val = self._cache[key]
46
 
        self._record_access(key)
47
 
        return val
 
82
        node = self._cache[key]
 
83
        # TODO: We may want to inline _record_access, to decrease the cost of
 
84
        #       __getitem__ calls
 
85
        self._record_access(node)
 
86
        return node.value
48
87
 
49
88
    def __len__(self):
50
89
        return len(self._cache)
51
90
 
 
91
    def _walk_lru(self):
 
92
        """Walk the LRU list."""
 
93
        node = self._most_recently_used
 
94
        if node is not None:
 
95
            assert node.prev is None
 
96
        while node is not None:
 
97
            if node.next is None:
 
98
                assert node is self._last_recently_used
 
99
            else:
 
100
                assert node.next.prev is node
 
101
            if node.prev is None:
 
102
                assert node is self._most_recently_used
 
103
            else:
 
104
                assert node.prev.next is node
 
105
            yield node
 
106
            node = node.next
 
107
 
52
108
    def add(self, key, value, cleanup=None):
53
109
        """Add a new value to the cache.
54
110
 
61
117
                        'value' sohuld be cleaned up.
62
118
        """
63
119
        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)
 
120
            node = self._cache[key]
 
121
            node.run_cleanup()
 
122
            node.value = value
 
123
            node.cleanup = cleanup
 
124
        else:
 
125
            node = _LRUNode(key, value, cleanup=cleanup)
 
126
            self._cache[key] = node
 
127
        self._record_access(node)
69
128
 
70
129
        if len(self._cache) > self._max_cache:
71
130
            # Trigger the cleanup
76
135
        return self._max_cache
77
136
 
78
137
    def get(self, key, default=None):
79
 
        if key in self._cache:
80
 
            return self[key]
81
 
        return default
 
138
        node = self._cache.get(key, None)
 
139
        if node is None:
 
140
            return default
 
141
        return node.value
82
142
 
83
143
    def keys(self):
84
144
        """Get the list of keys currently cached.
91
151
        """
92
152
        return self._cache.keys()
93
153
 
 
154
    def items(self):
 
155
        """Get the key:value pairs as a dict."""
 
156
        return dict((k, n.value) for k, n in self._cache.iteritems())
 
157
 
94
158
    def cleanup(self):
95
159
        """Clear the cache until it shrinks to the requested size.
96
160
 
107
171
        """Add a value to the cache, there will be no cleanup function."""
108
172
        self.add(key, value, cleanup=None)
109
173
 
110
 
    def _record_access(self, key):
 
174
    def _record_access(self, node):
111
175
        """Record that key was accessed."""
112
 
        self._queue.append(key)
113
 
        # Can't use setdefault because you can't += 1 the result
114
 
        self._refcount[key] = self._refcount.get(key, 0) + 1
115
 
 
116
 
        # If our access queue is too large, clean it up too
117
 
        if len(self._queue) > self._compact_queue_length:
118
 
            self._compact_queue()
119
 
 
120
 
    def _compact_queue(self):
121
 
        """Compact the queue, leaving things in sorted last appended order."""
122
 
        new_queue = deque()
123
 
        for item in self._queue:
124
 
            if self._refcount[item] == 1:
125
 
                new_queue.append(item)
126
 
            else:
127
 
                self._refcount[item] -= 1
128
 
        self._queue = new_queue
129
 
        # All entries should be of the same size. There should be one entry in
130
 
        # queue for each entry in cache, and all refcounts should == 1
131
 
        if not (len(self._queue) == len(self._cache) ==
132
 
                len(self._refcount) == sum(self._refcount.itervalues())):
133
 
            raise AssertionError()
134
 
 
135
 
    def _remove(self, key):
136
 
        """Remove an entry, making sure to maintain the invariants."""
137
 
        cleanup = self._cleanup.pop(key, None)
138
 
        val = self._cache.pop(key)
139
 
        if cleanup is not None:
140
 
            cleanup(key, val)
141
 
        return val
 
176
        # Move 'node' to the front of the queue
 
177
        if self._most_recently_used is None:
 
178
            assert len(self._cache) == 1
 
179
            self._most_recently_used = node
 
180
            self._last_recently_used = node
 
181
            assert node.next == None
 
182
            assert node.prev == None
 
183
            return
 
184
        elif node is self._most_recently_used:
 
185
            # Nothing to do, this node is already at the head of the queue
 
186
            return
 
187
        elif node is self._last_recently_used:
 
188
            assert self._last_recently_used is not None
 
189
            self._last_recently_used = node.prev
 
190
            assert self._last_recently_used is not None
 
191
        # We've taken care of the tail pointer, remove the node, and insert it
 
192
        # at the front
 
193
        # REMOVE
 
194
        if node.prev is not None:
 
195
            node.prev.next = node.next
 
196
        if node.next is not None:
 
197
            node.next.prev = node.prev
 
198
        # INSERT
 
199
        node.next = self._most_recently_used
 
200
        self._most_recently_used = node
 
201
        node.next.prev = node
 
202
        node.prev = None
 
203
 
 
204
    def _remove_node(self, node):
 
205
        assert node is not None
 
206
        if node is self._last_recently_used:
 
207
            self._last_recently_used = node.prev
 
208
        node2 = self._cache.pop(node.key)
 
209
        assert node2 is node
 
210
        del node2
 
211
        # If we have removed all entries, remove the head pointer as well
 
212
        if self._last_recently_used is None:
 
213
            if len(self._cache) != 0:
 
214
                import pdb; pdb.set_trace()
 
215
            assert len(self._cache) == 0
 
216
            assert self._most_recently_used is node
 
217
            self._most_recently_used = None
 
218
        node.run_cleanup()
 
219
        # Shouldn't be necessary
 
220
        # node.next = None
 
221
        # node.prev = None
142
222
 
143
223
    def _remove_lru(self):
144
224
        """Remove one entry from the lru, and handle consequences.
146
226
        If there are no more references to the lru, then this entry should be
147
227
        removed from the cache.
148
228
        """
149
 
        key = self._queue.popleft()
150
 
        self._refcount[key] -= 1
151
 
        if not self._refcount[key]:
152
 
            del self._refcount[key]
153
 
            self._remove(key)
 
229
        self._remove_node(self._last_recently_used)
154
230
 
155
231
    def clear(self):
156
232
        """Clear out all of the cache."""
168
244
        if after_cleanup_count is None:
169
245
            self._after_cleanup_count = self._max_cache * 8 / 10
170
246
        else:
171
 
            self._after_cleanup_count = min(after_cleanup_count, self._max_cache)
172
 
 
173
 
        self._compact_queue_length = 4*self._max_cache
174
 
        if len(self._queue) > self._compact_queue_length:
175
 
            self._compact_queue()
 
247
            self._after_cleanup_count = min(after_cleanup_count,
 
248
                                            self._max_cache)
176
249
        self.cleanup()
177
250
 
178
251
 
204
277
        self._compute_size = compute_size
205
278
        if compute_size is None:
206
279
            self._compute_size = len
207
 
        # This approximates that texts are > 0.5k in size. It only really
208
 
        # effects when we clean up the queue, so we don't want it to be too
209
 
        # large.
210
280
        self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
211
281
        LRUCache.__init__(self, max_cache=max(int(max_size/512), 1))
212
282
 
221
291
        :param cleanup: None or a function taking (key, value) to indicate
222
292
                        'value' sohuld be cleaned up.
223
293
        """
224
 
        if key in self._cache:
225
 
            self._remove(key)
 
294
        node = self._cache.get(key, None)
226
295
        value_len = self._compute_size(value)
227
296
        if value_len >= self._after_cleanup_size:
 
297
            if node is not None:
 
298
                # The new value is too large, we won't be replacing the value,
 
299
                # just removing the node completely
 
300
                self._remove_node(node)
228
301
            return
 
302
        if node is None:
 
303
            node = _LRUNode(key, value, cleanup=cleanup)
 
304
            self._cache[key] = node
 
305
        else:
 
306
            self._value_size -= node.size
 
307
        node.size = value_len
229
308
        self._value_size += value_len
230
 
        self._cache[key] = value
231
 
        if cleanup is not None:
232
 
            self._cleanup[key] = cleanup
233
 
        self._record_access(key)
 
309
        self._record_access(node)
234
310
 
235
311
        if self._value_size > self._max_size:
236
312
            # Time to cleanup
246
322
        while self._value_size > self._after_cleanup_size:
247
323
            self._remove_lru()
248
324
 
249
 
    def _remove(self, key):
250
 
        """Remove an entry, making sure to maintain the invariants."""
251
 
        val = LRUCache._remove(self, key)
252
 
        self._value_size -= self._compute_size(val)
 
325
    def _remove_node(self, node):
 
326
        self._value_size -= node.size
 
327
        LRUCache._remove_node(self, node)
253
328
 
254
329
    def resize(self, max_size, after_cleanup_size=None):
255
330
        """Change the number of bytes that will be cached."""