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

[Matt Nordhoff]

Robert Collins wrote:
> 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

If it's really unlikely that the cache will be filled, but you don't
want the performance cost of an LRUCache, why not compromise and use a
FIFOCache?
--