[MERGE] Use a dict for Btree internal nodes instead of LRU

[Robert Collins]

On Thu, 2009-03-26 at 15:57 -0500, John Arbash Meinel wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> At the moment we use an LRUCache for btree internal nodes, with a max of
> 100 records. However, experience has shown that we get 100 nodes per
> page (interestingly this holds true for chk pages). For the Launchpad
> .cix we have 340k records, which fits on 3190 total pages. Of that, 21
> are internal nodes.
> 
> At a factor of 100:1 at each level, you need to have 100*100*100 = 1M
> nodes before the internal node cache would ever start dropping entries.
> As such, it doesn't seem worthwhile to spend any time maintaining an LRU
> for internal nodes.
> 
> I know we intend to have btree's be memory capped, but it just seems
> that just naturally we won't get many internal nodes. We already put
> them into a separate cache because we didn't want leaf-nodes flushing
> them out of the cache.
> 
> I don't know that this is a big win either way, but it just made sense
> to me as I was looking at the code.

I'd really rather not un-cap any part of this code. What is the
performance difference though?

-Rob
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20090327/f03ec5ce/attachment-0001.pgp