Rev 3892: Add a FIFOSizeCache which is constrained based on the size of the values. in http://bzr.arbash-meinel.com/branches/bzr/1.11/fifo_cache
John Arbash Meinel
john at arbash-meinel.com
Tue Dec 9 22:27:02 GMT 2008
At http://bzr.arbash-meinel.com/branches/bzr/1.11/fifo_cache
------------------------------------------------------------
revno: 3892
revision-id: john at arbash-meinel.com-20081209222640-u3iece2ixcd0q7lj
parent: john at arbash-meinel.com-20081209220341-9d70gll0szipelao
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: fifo_cache
timestamp: Tue 2008-12-09 16:26:40 -0600
message:
Add a FIFOSizeCache which is constrained based on the size of the values.
-------------- next part --------------
=== modified file 'bzrlib/fifo_cache.py'
--- a/bzrlib/fifo_cache.py 2008-12-09 21:57:36 +0000
+++ b/bzrlib/fifo_cache.py 2008-12-09 22:26:40 +0000
@@ -38,6 +38,7 @@
self.add(key, value, cleanup=None)
def __delitem__(self, key):
+ # Remove the key from an arbitrary location in the queue
self._queue.remove(key)
self._remove(key)
@@ -58,10 +59,10 @@
del self[key]
self._queue.append(key)
dict.__setitem__(self, key, value)
+ if cleanup is not None:
+ self._cleanup[key] = cleanup
if len(self) > self._max_cache:
self.cleanup()
- if cleanup is not None:
- self._cleanup[key] = cleanup
def cleanup(self):
"""Clear the cache until it shrinks to the requested size.
@@ -138,3 +139,81 @@
if kwargs:
for key, val in kwargs.iteritems():
self.add(key, val)
+
+
+class FIFOSizeCache(FIFOCache):
+ """An FIFOCache that removes things based on the size of the values.
+
+ This differs in that it doesn't care how many actual items there are,
+ it restricts the cache to be cleaned based on the size of the data.
+ """
+
+ def __init__(self, max_size=1024*1024, after_cleanup_size=None,
+ compute_size=None):
+ """Create a new FIFOSizeCache.
+
+ :param max_size: The max number of bytes to store before we start
+ clearing out entries.
+ :param after_cleanup_size: After cleaning up, shrink everything to this
+ size (defaults to 80% of max_size).
+ :param compute_size: A function to compute the size of a value. If
+ not supplied we default to 'len'.
+ """
+ # Arbitrary, we won't really be using the value anyway.
+ FIFOCache.__init__(self, max_cache=max_size)
+ self._max_size = max_size
+ if after_cleanup_size is None:
+ self._after_cleanup_size = self._max_size * 8 / 10
+ else:
+ self._after_cleanup_size = min(after_cleanup_size, self._max_size)
+
+ self._value_size = 0
+ self._compute_size = compute_size
+ if compute_size is None:
+ self._compute_size = len
+
+ def add(self, key, value, cleanup=None):
+ """Add a new value to the cache.
+
+ Also, if the entry is ever removed from the queue, call cleanup.
+ Passing it the key and value being removed.
+
+ :param key: The key to store it under
+ :param value: The object to store, this value by itself is >=
+ after_cleanup_size, then we will not store it at all.
+ :param cleanup: None or a function taking (key, value) to indicate
+ 'value' sohuld be cleaned up.
+ """
+ # Even if the new value won't be stored, we need to remove the old
+ # value
+ if key in self:
+ # Remove the earlier reference to this key, adding it again bumps
+ # it to the end of the queue
+ del self[key]
+ value_len = self._compute_size(value)
+ if value_len >= self._after_cleanup_size:
+ return
+ self._queue.append(key)
+ dict.__setitem__(self, key, value)
+ if cleanup is not None:
+ self._cleanup[key] = cleanup
+ self._value_size += value_len
+ if self._value_size > self._max_size:
+ # Time to cleanup
+ self.cleanup()
+
+ def cleanup(self):
+ """Clear the cache until it shrinks to the requested size.
+
+ This does not completely wipe the cache, just makes sure it is under
+ the after_cleanup_size.
+ """
+ # Make sure the cache is shrunk to the correct size
+ while self._value_size > self._after_cleanup_size:
+ self._remove_oldest()
+
+ def _remove(self, key):
+ """Remove an entry, making sure to maintain the invariants."""
+ val = FIFOCache._remove(self, key)
+ self._value_size -= self._compute_size(val)
+ return val
=== modified file 'bzrlib/tests/test_fifo_cache.py'
--- a/bzrlib/tests/test_fifo_cache.py 2008-12-09 22:03:41 +0000
+++ b/bzrlib/tests/test_fifo_cache.py 2008-12-09 22:26:40 +0000
@@ -189,3 +189,62 @@
self.expectFailure("we don't call cleanups during __del__",
self.assertEqual, [(1, 2)], log)
self.assertEqual([(1, 2)], log)
+
+
+class TestFIFOSizeCache(tests.TestCase):
+
+ def test_add_is_present(self):
+ c = fifo_cache.FIFOSizeCache()
+ c[1] = '2'
+ self.assertTrue(1 in c)
+ self.assertEqual(1, len(c))
+ self.assertEqual('2', c[1])
+ self.assertEqual('2', c.get(1))
+ self.assertEqual('2', c.get(1, None))
+ self.assertEqual([1], c.keys())
+ self.assertEqual([1], list(c.iterkeys()))
+ self.assertEqual([(1, '2')], c.items())
+ self.assertEqual([(1, '2')], list(c.iteritems()))
+ self.assertEqual(['2'], c.values())
+ self.assertEqual(['2'], list(c.itervalues()))
+ self.assertEqual({1: '2'}, c)
+
+ def test_missing(self):
+ c = fifo_cache.FIFOSizeCache()
+ self.assertRaises(KeyError, c.__getitem__, 1)
+ self.assertFalse(1 in c)
+ self.assertEqual(0, len(c))
+ self.assertEqual(None, c.get(1))
+ self.assertEqual(None, c.get(1, None))
+ self.assertEqual([], c.keys())
+ self.assertEqual([], list(c.iterkeys()))
+ self.assertEqual([], c.items())
+ self.assertEqual([], list(c.iteritems()))
+ self.assertEqual([], c.values())
+ self.assertEqual([], list(c.itervalues()))
+ self.assertEqual({}, c)
+
+ def test_add_maintains_fifo(self):
+ c = fifo_cache.FIFOSizeCache(10, 8)
+ c[1] = 'ab'
+ c[2] = 'cde'
+ c[3] = 'fghi'
+ self.assertEqual({1: 'ab', 2: 'cde', 3: 'fghi'}, c)
+ c[4] = 'jkl' # Collapse
+ self.assertEqual({3: 'fghi', 4: 'jkl'}, c)
+ # Replacing an item will bump it to the end of the queue
+ c[3] = 'mnop'
+ self.assertEqual({3: 'mnop', 4: 'jkl'}, c)
+ c[5] = 'qrst'
+ self.assertEqual({3: 'mnop', 5: 'qrst'}, c)
+
+ def test_adding_large_key(self):
+ c = fifo_cache.FIFOSizeCache(10, 8)
+ c[1] = 'abcdefgh' # Adding a large key won't get cached at all
+ self.assertEqual({}, c)
+ c[1] = 'abcdefg'
+ self.assertEqual({1: 'abcdefg'}, c)
+ # Replacing with a too-large key will remove it
+ c[1] = 'abcdefgh'
+ self.assertEqual({}, c)
+ self.assertEqual(0, c._value_size)
More information about the bazaar-commits
mailing list