[MERGE] FIFOCache and FIFOSizeCache

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I've been doing some performance testing with adding a cache for
InventoryEntries. And it turns out that while an LRUCache works well, it
has a significant amount of overhead for all of those lookups.

So I went ahead and implemented a FIFOCache which only adds extra
overhead when adding or removing an entry. Unfortunately a subclass of
dict isn't quite as fast as a raw dict for lookup. But it is very close.
(TIMEIT shows it being about 2x slower, but a custom __getitem__
implementation is 4x slower.)

The FIFOCache will also have a smaller memory overhead than LRUCache.
LRUCache has 3 dictionaries and an access queue that can grow quite
large (it is bounded, but still large). FIFO has 2 dicts and a queue,
but I've also optimized it so that if you don't use cleanup functions,
then the cleanup dict stays empty. (I'll go fix that in the LRU code as
well.)

The queue itself is only ever as large as the dict.

This should work reasonably well when you still want a bounded-size
cache, but you aren't accessing older things as often. It probably won't
have quite as high of a hit rate as an LRU, but that is often a
reasonable trade-off versus having to track when something was last
accessed.

Because I'm subclassing dict, I tried to make sure that all
functionality that mutates the dict is either disabled, or maintains the
invariants.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkk+8Z0ACgkQJdeBCYSNAANJJgCfdUlkuZRgIfqchCgRC3g98KXH
nYwAoJ4WWUtOHcer0tvILBI94eJA2aOW
=NUFa
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: fifo_cache.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20081209/49c9f8ea/attachment-0001.diff