/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/lru_cache.py

  • Committer: John Arbash Meinel
  • Date: 2009-04-16 22:06:25 UTC
  • mto: This revision was merged to the branch mainline in revision 4323.
  • Revision ID: john@arbash-meinel.com-20090416220625-hejrugy3r5qwlut9
Restore the ability to handle None as a key.
We now use _null_key instead of None to indicate the end-of-refs.
This means we now check that _null_key isn't used as an actual key.
This slows us down from 7.1 => 7.3s or so.
Interestingly, the globals lookup of _null_key was faster than
node is self._lru (7.5s+). I was a bit surprised at that.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/lru_cache.py
1
 
# Copyright (C) 2006, 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2006, 2008 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
43
43
        if self.prev is None:
44
44
            prev_key = None
45
45
        else:
46
 
            prev_key = self.prev.key
 
46
            prev_key = self.prev_key
47
47
        return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
48
48
                                     self.next_key, prev_key)
49
49
 
50
50
    def run_cleanup(self):
51
 
        try:
52
 
            if self.cleanup is not None:
53
 
                self.cleanup(self.key, self.value)
54
 
        finally:
55
 
            # cleanup might raise an exception, but we want to make sure
56
 
            # to break refcycles, etc
57
 
            self.cleanup = None
58
 
            self.value = None
 
51
        if self.cleanup is not None:
 
52
            self.cleanup(self.key, self.value)
 
53
        self.cleanup = None
 
54
        # Just make sure to break any refcycles, etc
 
55
        self.value = None
59
56
 
60
57
 
61
58
class LRUCache(object):
73
70
        # The "HEAD" of the lru linked list
74
71
        self._most_recently_used = None
75
72
        # The "TAIL" of the lru linked list
76
 
        self._least_recently_used = None
 
73
        self._last_recently_used = None
77
74
        self._update_max_cache(max_cache, after_cleanup_count)
78
75
 
79
76
    def __contains__(self, key):
94
91
        node_prev = node.prev
95
92
        next_key = node.next_key
96
93
        # benchmarking shows that the lookup of _null_key in globals is faster
97
 
        # than the attribute lookup for (node is self._least_recently_used)
 
94
        # than the attribute lookup for (node is self._last_recently_used)
98
95
        if next_key is _null_key:
99
 
            # 'node' is the _least_recently_used, because it doesn't have a
 
96
            # 'node' is the _last_recently_used, because it doesn't have a
100
97
            # 'next' item. So move the current lru to the previous node.
101
 
            self._least_recently_used = node_prev
 
98
            self._last_recently_used = node_prev
102
99
        else:
103
100
            node_next = cache[next_key]
104
101
            node_next.prev = node_prev
123
120
                                     ' %s' % (node,))
124
121
        while node is not None:
125
122
            if node.next_key is _null_key:
126
 
                if node is not self._least_recently_used:
 
123
                if node is not self._last_recently_used:
127
124
                    raise AssertionError('only the last node should have'
128
125
                                         ' no next value: %s' % (node,))
129
126
                node_next = None
159
156
            raise ValueError('cannot use _null_key as a key')
160
157
        if key in self._cache:
161
158
            node = self._cache[key]
162
 
            try:
163
 
                node.run_cleanup()
164
 
            finally:
165
 
                # Maintain the LRU properties, even if cleanup raises an
166
 
                # exception
167
 
                node.value = value
168
 
                node.cleanup = cleanup
169
 
                self._record_access(node)
 
159
            node.run_cleanup()
 
160
            node.value = value
 
161
            node.cleanup = cleanup
170
162
        else:
171
163
            node = _LRUNode(key, value, cleanup=cleanup)
172
164
            self._cache[key] = node
173
 
            self._record_access(node)
 
165
        self._record_access(node)
174
166
 
175
167
        if len(self._cache) > self._max_cache:
176
168
            # Trigger the cleanup
221
213
        # Move 'node' to the front of the queue
222
214
        if self._most_recently_used is None:
223
215
            self._most_recently_used = node
224
 
            self._least_recently_used = node
 
216
            self._last_recently_used = node
225
217
            return
226
218
        elif node is self._most_recently_used:
227
219
            # Nothing to do, this node is already at the head of the queue
229
221
        # We've taken care of the tail pointer, remove the node, and insert it
230
222
        # at the front
231
223
        # REMOVE
232
 
        if node is self._least_recently_used:
233
 
            self._least_recently_used = node.prev
 
224
        if node is self._last_recently_used:
 
225
            self._last_recently_used = node.prev
234
226
        if node.prev is not None:
235
227
            node.prev.next_key = node.next_key
236
228
        if node.next_key is not _null_key:
243
235
        node.prev = None
244
236
 
245
237
    def _remove_node(self, node):
246
 
        if node is self._least_recently_used:
247
 
            self._least_recently_used = node.prev
 
238
        if node is self._last_recently_used:
 
239
            self._last_recently_used = node.prev
248
240
        self._cache.pop(node.key)
249
241
        # If we have removed all entries, remove the head pointer as well
250
 
        if self._least_recently_used is None:
 
242
        if self._last_recently_used is None:
251
243
            self._most_recently_used = None
252
 
        try:
253
 
            node.run_cleanup()
254
 
        finally:
255
 
            # cleanup might raise an exception, but we want to make sure to
256
 
            # maintain the linked list
257
 
            if node.prev is not None:
258
 
                node.prev.next_key = node.next_key
259
 
            if node.next_key is not _null_key:
260
 
                node_next = self._cache[node.next_key]
261
 
                node_next.prev = node.prev
262
 
            # And remove this node's pointers
263
 
            node.prev = None
264
 
            node.next_key = _null_key
 
244
        node.run_cleanup()
 
245
        # Now remove this node from the linked list
 
246
        if node.prev is not None:
 
247
            node.prev.next_key = node.next_key
 
248
        if node.next_key is not _null_key:
 
249
            node_next = self._cache[node.next_key]
 
250
            node_next.prev = node.prev
 
251
        # And remove this node's pointers
 
252
        node.prev = None
 
253
        node.next_key = _null_key
265
254
 
266
255
    def _remove_lru(self):
267
256
        """Remove one entry from the lru, and handle consequences.
269
258
        If there are no more references to the lru, then this entry should be
270
259
        removed from the cache.
271
260
        """
272
 
        self._remove_node(self._least_recently_used)
 
261
        self._remove_node(self._last_recently_used)
273
262
 
274
263
    def clear(self):
275
264
        """Clear out all of the cache."""