← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/lru_cache.py

  • Committer: Patch Queue Manager
  • Date: 2016-04-21 04:10:52 UTC
  • mfrom: (6616.1.1 fix-en-user-guide)
  • Revision ID: pqm@pqm.ubuntu.com-20160421041052-clcye7ns1qcl2n7w
(richard-wilbur) Ensure build of English use guide always uses English text
 even when user's locale specifies a different language. (Jelmer Vernooij)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/lru_cache.py
1
 
# Copyright (C) 2006 Canonical Ltd
 
1
# Copyright (C) 2006, 2008, 2009 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
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
"""A simple least-recently-used (LRU) cache."""
18
18
 
19
 
from collections import deque
20
 
import gc
 
19
from __future__ import absolute_import
 
20
 
 
21
from bzrlib import (
 
22
    symbol_versioning,
 
23
    trace,
 
24
    )
 
25
 
 
26
_null_key = object()
 
27
 
 
28
class _LRUNode(object):
 
29
    """This maintains the linked-list which is the lru internals."""
 
30
 
 
31
    __slots__ = ('prev', 'next_key', 'key', 'value')
 
32
 
 
33
    def __init__(self, key, value):
 
34
        self.prev = None
 
35
        self.next_key = _null_key
 
36
        self.key = key
 
37
        self.value = value
 
38
 
 
39
    def __repr__(self):
 
40
        if self.prev is None:
 
41
            prev_key = None
 
42
        else:
 
43
            prev_key = self.prev.key
 
44
        return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
 
45
                                     self.next_key, prev_key)
21
46
 
22
47
 
23
48
class LRUCache(object):
24
49
    """A class which manages a cache of entries, removing unused ones."""
25
50
 
26
 
    def __init__(self, max_cache=100, after_cleanup_size=None):
27
 
        self._max_cache = max_cache
28
 
        if after_cleanup_size is None:
29
 
            self._after_cleanup_size = self._max_cache
30
 
        else:
31
 
            self._after_cleanup_size = min(after_cleanup_size, self._max_cache)
32
 
 
33
 
        self._compact_queue_length = 4*self._max_cache
34
 
 
 
51
    def __init__(self, max_cache=100, after_cleanup_count=None):
35
52
        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
 
53
        # The "HEAD" of the lru linked list
 
54
        self._most_recently_used = None
 
55
        # The "TAIL" of the lru linked list
 
56
        self._least_recently_used = None
 
57
        self._update_max_cache(max_cache, after_cleanup_count)
39
58
 
40
59
    def __contains__(self, key):
41
60
        return key in self._cache
42
61
 
43
62
    def __getitem__(self, key):
44
 
        val = self._cache[key]
45
 
        self._record_access(key)
46
 
        return val
 
63
        cache = self._cache
 
64
        node = cache[key]
 
65
        # Inlined from _record_access to decrease the overhead of __getitem__
 
66
        # We also have more knowledge about structure if __getitem__ is
 
67
        # succeeding, then we know that self._most_recently_used must not be
 
68
        # None, etc.
 
69
        mru = self._most_recently_used
 
70
        if node is mru:
 
71
            # Nothing to do, this node is already at the head of the queue
 
72
            return node.value
 
73
        # Remove this node from the old location
 
74
        node_prev = node.prev
 
75
        next_key = node.next_key
 
76
        # benchmarking shows that the lookup of _null_key in globals is faster
 
77
        # than the attribute lookup for (node is self._least_recently_used)
 
78
        if next_key is _null_key:
 
79
            # 'node' is the _least_recently_used, because it doesn't have a
 
80
            # 'next' item. So move the current lru to the previous node.
 
81
            self._least_recently_used = node_prev
 
82
        else:
 
83
            node_next = cache[next_key]
 
84
            node_next.prev = node_prev
 
85
        node_prev.next_key = next_key
 
86
        # Insert this node at the front of the list
 
87
        node.next_key = mru.key
 
88
        mru.prev = node
 
89
        self._most_recently_used = node
 
90
        node.prev = None
 
91
        return node.value
47
92
 
48
93
    def __len__(self):
49
94
        return len(self._cache)
50
95
 
 
96
    @symbol_versioning.deprecated_method(
 
97
        symbol_versioning.deprecated_in((2, 5, 0)))
51
98
    def add(self, key, value, cleanup=None):
52
 
        """Add a new value to the cache.
53
 
 
54
 
        Also, if the entry is ever removed from the queue, call cleanup.
55
 
        Passing it the key and value being removed.
56
 
 
57
 
        :param key: The key to store it under
58
 
        :param value: The object to store
59
 
        :param cleanup: None or a function taking (key, value) to indicate
60
 
                        'value' sohuld be cleaned up.
61
 
        """
 
99
        if cleanup is not None:
 
100
            raise ValueError("Per-node cleanup functions no longer supported")
 
101
        return self.__setitem__(key, value)
 
102
 
 
103
    def __setitem__(self, key, value):
 
104
        """Add a new value to the cache"""
 
105
        if key is _null_key:
 
106
            raise ValueError('cannot use _null_key as a key')
62
107
        if key in self._cache:
63
 
            self._remove(key)
64
 
        self._cache[key] = value
65
 
        self._cleanup[key] = cleanup
66
 
        self._record_access(key)
 
108
            node = self._cache[key]
 
109
            node.value = value
 
110
            self._record_access(node)
 
111
        else:
 
112
            node = _LRUNode(key, value)
 
113
            self._cache[key] = node
 
114
            self._record_access(node)
67
115
 
68
116
        if len(self._cache) > self._max_cache:
69
117
            # Trigger the cleanup
70
118
            self.cleanup()
71
119
 
 
120
    def cache_size(self):
 
121
        """Get the number of entries we will cache."""
 
122
        return self._max_cache
 
123
 
72
124
    def get(self, key, default=None):
73
 
        if key in self._cache:
74
 
            return self[key]
75
 
        return default
 
125
        node = self._cache.get(key, None)
 
126
        if node is None:
 
127
            return default
 
128
        self._record_access(node)
 
129
        return node.value
 
130
 
 
131
    def keys(self):
 
132
        """Get the list of keys currently cached.
 
133
 
 
134
        Note that values returned here may not be available by the time you
 
135
        request them later. This is simply meant as a peak into the current
 
136
        state.
 
137
 
 
138
        :return: An unordered list of keys that are currently cached.
 
139
        """
 
140
        return self._cache.keys()
 
141
 
 
142
    def as_dict(self):
 
143
        """Get a new dict with the same key:value pairs as the cache"""
 
144
        return dict((k, n.value) for k, n in self._cache.iteritems())
 
145
 
 
146
    items = symbol_versioning.deprecated_method(
 
147
        symbol_versioning.deprecated_in((2, 5, 0)))(as_dict)
76
148
 
77
149
    def cleanup(self):
78
150
        """Clear the cache until it shrinks to the requested size.
79
151
 
80
152
        This does not completely wipe the cache, just makes sure it is under
81
 
        the after_cleanup_size.
 
153
        the after_cleanup_count.
82
154
        """
83
155
        # Make sure the cache is shrunk to the correct size
84
 
        while len(self._cache) > self._after_cleanup_size:
 
156
        while len(self._cache) > self._after_cleanup_count:
85
157
            self._remove_lru()
86
158
 
87
 
    def __setitem__(self, key, value):
88
 
        """Add a value to the cache, there will be no cleanup function."""
89
 
        self.add(key, value, cleanup=None)
90
 
 
91
 
    def _record_access(self, key):
 
159
    def _record_access(self, node):
92
160
        """Record that key was accessed."""
93
 
        self._queue.append(key)
94
 
        # Can't use setdefault because you can't += 1 the result
95
 
        self._refcount[key] = self._refcount.get(key, 0) + 1
96
 
 
97
 
        # If our access queue is too large, clean it up too
98
 
        if len(self._queue) > self._compact_queue_length:
99
 
            self._compact_queue()
100
 
 
101
 
    def _compact_queue(self):
102
 
        """Compact the queue, leaving things in sorted last appended order."""
103
 
        new_queue = deque()
104
 
        for item in self._queue:
105
 
            if self._refcount[item] == 1:
106
 
                new_queue.append(item)
107
 
            else:
108
 
                self._refcount[item] -= 1
109
 
        self._queue = new_queue
110
 
        # All entries should be of the same size. There should be one entry in
111
 
        # queue for each entry in cache, and all refcounts should == 1
112
 
        if not (len(self._queue) == len(self._cache) ==
113
 
                len(self._refcount) == sum(self._refcount.itervalues())):
114
 
            raise AssertionError()
115
 
 
116
 
    def _remove(self, key):
117
 
        """Remove an entry, making sure to maintain the invariants."""
118
 
        cleanup = self._cleanup.pop(key)
119
 
        val = self._cache.pop(key)
120
 
        if cleanup is not None:
121
 
            cleanup(key, val)
122
 
        return val
 
161
        # Move 'node' to the front of the queue
 
162
        if self._most_recently_used is None:
 
163
            self._most_recently_used = node
 
164
            self._least_recently_used = node
 
165
            return
 
166
        elif node is self._most_recently_used:
 
167
            # Nothing to do, this node is already at the head of the queue
 
168
            return
 
169
        # We've taken care of the tail pointer, remove the node, and insert it
 
170
        # at the front
 
171
        # REMOVE
 
172
        if node is self._least_recently_used:
 
173
            self._least_recently_used = node.prev
 
174
        if node.prev is not None:
 
175
            node.prev.next_key = node.next_key
 
176
        if node.next_key is not _null_key:
 
177
            node_next = self._cache[node.next_key]
 
178
            node_next.prev = node.prev
 
179
        # INSERT
 
180
        node.next_key = self._most_recently_used.key
 
181
        self._most_recently_used.prev = node
 
182
        self._most_recently_used = node
 
183
        node.prev = None
 
184
 
 
185
    def _remove_node(self, node):
 
186
        if node is self._least_recently_used:
 
187
            self._least_recently_used = node.prev
 
188
        self._cache.pop(node.key)
 
189
        # If we have removed all entries, remove the head pointer as well
 
190
        if self._least_recently_used is None:
 
191
            self._most_recently_used = None
 
192
        if node.prev is not None:
 
193
            node.prev.next_key = node.next_key
 
194
        if node.next_key is not _null_key:
 
195
            node_next = self._cache[node.next_key]
 
196
            node_next.prev = node.prev
 
197
        # And remove this node's pointers
 
198
        node.prev = None
 
199
        node.next_key = _null_key
123
200
 
124
201
    def _remove_lru(self):
125
202
        """Remove one entry from the lru, and handle consequences.
127
204
        If there are no more references to the lru, then this entry should be
128
205
        removed from the cache.
129
206
        """
130
 
        key = self._queue.popleft()
131
 
        self._refcount[key] -= 1
132
 
        if not self._refcount[key]:
133
 
            del self._refcount[key]
134
 
            self._remove(key)
 
207
        self._remove_node(self._least_recently_used)
135
208
 
136
209
    def clear(self):
137
210
        """Clear out all of the cache."""
139
212
        while self._cache:
140
213
            self._remove_lru()
141
214
 
 
215
    def resize(self, max_cache, after_cleanup_count=None):
 
216
        """Change the number of entries that will be cached."""
 
217
        self._update_max_cache(max_cache,
 
218
                               after_cleanup_count=after_cleanup_count)
 
219
 
 
220
    def _update_max_cache(self, max_cache, after_cleanup_count=None):
 
221
        self._max_cache = max_cache
 
222
        if after_cleanup_count is None:
 
223
            self._after_cleanup_count = self._max_cache * 8 / 10
 
224
        else:
 
225
            self._after_cleanup_count = min(after_cleanup_count,
 
226
                                            self._max_cache)
 
227
        self.cleanup()
 
228
 
142
229
 
143
230
class LRUSizeCache(LRUCache):
144
231
    """An LRUCache that removes things based on the size of the values.
146
233
    This differs in that it doesn't care how many actual items there are,
147
234
    it just restricts the cache to be cleaned up after so much data is stored.
148
235
 
149
 
    The values that are added must support len(value).
 
236
    The size of items added will be computed using compute_size(value), which
 
237
    defaults to len() if not supplied.
150
238
    """
151
239
 
152
240
    def __init__(self, max_size=1024*1024, after_cleanup_size=None,
164
252
            The function should take the form "compute_size(value) => integer".
165
253
            If not supplied, it defaults to 'len()'
166
254
        """
167
 
        # This approximates that texts are > 0.5k in size. It only really
168
 
        # effects when we clean up the queue, so we don't want it to be too
169
 
        # large.
170
 
        LRUCache.__init__(self, max_cache=int(max_size/512))
171
 
        self._max_size = max_size
172
 
        if after_cleanup_size is None:
173
 
            self._after_cleanup_size = self._max_size
174
 
        else:
175
 
            self._after_cleanup_size = min(after_cleanup_size, self._max_size)
176
 
 
177
255
        self._value_size = 0
178
256
        self._compute_size = compute_size
179
257
        if compute_size is None:
180
258
            self._compute_size = len
181
 
 
182
 
    def add(self, key, value, cleanup=None):
183
 
        """Add a new value to the cache.
184
 
 
185
 
        Also, if the entry is ever removed from the queue, call cleanup.
186
 
        Passing it the key and value being removed.
187
 
 
188
 
        :param key: The key to store it under
189
 
        :param value: The object to store
190
 
        :param cleanup: None or a function taking (key, value) to indicate
191
 
                        'value' sohuld be cleaned up.
192
 
        """
193
 
        if key in self._cache:
194
 
            self._remove(key)
 
259
        self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
 
260
        LRUCache.__init__(self, max_cache=max(int(max_size/512), 1))
 
261
 
 
262
    def __setitem__(self, key, value):
 
263
        """Add a new value to the cache"""
 
264
        if key is _null_key:
 
265
            raise ValueError('cannot use _null_key as a key')
 
266
        node = self._cache.get(key, None)
195
267
        value_len = self._compute_size(value)
196
268
        if value_len >= self._after_cleanup_size:
 
269
            # The new value is 'too big to fit', as it would fill up/overflow
 
270
            # the cache all by itself
 
271
            trace.mutter('Adding the key %r to an LRUSizeCache failed.'
 
272
                         ' value %d is too big to fit in a the cache'
 
273
                         ' with size %d %d', key, value_len,
 
274
                         self._after_cleanup_size, self._max_size)
 
275
            if node is not None:
 
276
                # We won't be replacing the old node, so just remove it
 
277
                self._remove_node(node)
197
278
            return
 
279
        if node is None:
 
280
            node = _LRUNode(key, value)
 
281
            self._cache[key] = node
 
282
        else:
 
283
            self._value_size -= self._compute_size(node.value)
198
284
        self._value_size += value_len
199
 
        self._cache[key] = value
200
 
        self._cleanup[key] = cleanup
201
 
        self._record_access(key)
 
285
        self._record_access(node)
202
286
 
203
287
        if self._value_size > self._max_size:
204
288
            # Time to cleanup
214
298
        while self._value_size > self._after_cleanup_size:
215
299
            self._remove_lru()
216
300
 
217
 
    def _remove(self, key):
218
 
        """Remove an entry, making sure to maintain the invariants."""
219
 
        val = LRUCache._remove(self, key)
220
 
        self._value_size -= self._compute_size(val)
 
301
    def _remove_node(self, node):
 
302
        self._value_size -= self._compute_size(node.value)
 
303
        LRUCache._remove_node(self, node)
 
304
 
 
305
    def resize(self, max_size, after_cleanup_size=None):
 
306
        """Change the number of bytes that will be cached."""
 
307
        self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
 
308
        max_cache = max(int(max_size/512), 1)
 
309
        self._update_max_cache(max_cache)
 
310
 
 
311
    def _update_max_size(self, max_size, after_cleanup_size=None):
 
312
        self._max_size = max_size
 
313
        if after_cleanup_size is None:
 
314
            self._after_cleanup_size = self._max_size * 8 / 10
 
315
        else:
 
316
            self._after_cleanup_size = min(after_cleanup_size, self._max_size)