B+tree discussions

[John Arbash Meinel]

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

Robert Collins wrote:
| On Wed, 2008-07-02 at 16:40 -0500, John Arbash Meinel wrote:
|> -----BEGIN PGP SIGNED MESSAGE-----
|> Hash: SHA1
|>
|> I've done some more tweaking. And here are some interesting results:
|
| Cool.
|
| I'm glad you did all this. I was about to start on some similar
| things :).
|
| I'll see the code shortly, but:
|
|
|> 1) I added a value-level cache. So that when we read a leaf node, we
|> cache all the keys in that leaf node. This dramatically improved the
|> "iter_random_one" tests. Such that btree becomes *faster* than graph.
|
| Do you eject lines from the value cache when the leaf is discarded? If
| the answer is (no, the value cache is a lru itself) perhaps the value
| cache should be on CombinedGraphIndex, not the individual index?

ATM it is just another lru, and it is cached per key.

Though given our access patterns, I actually think a FIFOCache might
provide just as much proper caching, and have significantly lower overhead.

|
|> With no cache, the 100 node leaf cache is about 50% efficient (it hits
|> 50k times, and misses 54k times)
|
| Note that the leaf cache probably wants tuning :).
|
|> With a key cache of 10,000 entries, it hits 50% of the time (50.4k hits
|> vs 55k misses), but causes the leaf node cache to drop to 16k hits
|> versus 39k misses.
|> With a key cache of 100,000 entries, we hit 99% of the time (104k hits
|> versus 1k misses), but the leaf node cache only misses on all 1067
checks.
|> With a node cache of 500, 1,000, or 10,000 we hit 99% of the time, but
|> are half the speed of a key cache.
|> With a node cache of 200, we hit 77k versus 27k misses. It still costs
|> us a lot.
|
| I think that that has something to do with the work of finding the node.
|
|
|> 2) The LRUCache has a bit of overhead. Enough that doing (1) slowed down
|> things like search_from_revid.
|
| I think it can be tuned further. Its certainly in the critical path.

Well, a per-key cache gets a lot of hits and is critical. A per-node
cache, not so much. (There is generally at least 100:1 in the number of
nodes versus the number of keys.)

The cost of reloading a node is probably pretty high. As we completely
parse the node, as well as having to read it.

|
|> 3) The biggest penalty in graph.iter_ancestry() is that we search for
|> revision ids in indexes where it is not present. Specifically, we have
|> over 60,000 lookups that miss. Bloom only catches about 6,000 (10%)
of that.
|> Getting rid of the leaf cache in favor of the line cache hurts a lot
|> here. Because we get to the leaf node, and have to read it again to
|> realize that the key we want isn't there.
|> I added the ability to cache that a revision_id isn't present (you add
|> _not_present_object into the cache). However, for iter_ancestry() we
|> don't actually revisit the same revisions multiple times. So it doesn't
|> improve things a lot. It did hit somewhat for get_componets_positions().
|
| I'd rather not cache negative hits - if we promote the line cache to the
| combined index object then a negative hit on one index should always be
| a ghost or a hit on another and then not hit the low level index again.
|

I got rid of this. As mentioned for "search_revision_id" it never was
valid. It did get some hits for components.

I think it is reasonable to bring the line cache up to combined index.
Just didn't get there.


|> 4) I added more instrumentation, to measure hit rate, miss rate, cached
|> node hit rate, etc. It is actually pretty interesting to have, as it
|> gives some good info as to what is really going on.
|
| Yay!
|

Yah, a lot of it now tracks hits and misses for different actions.
Tracking overall misses was quite revealing, IMO.

John
=:->


|> 5) My _multi_bisect_right does help. With no line cache, and only 100
|> leaf node (and internal node) caches:
|>
|> get_components_positions() 28.480s => 14.574s
|> search_from_rev_id() 2.517s => 1.200s
|> miss_torture() 25.094s => 10.960s
|>
|> It is also important to test with the exact same repository. As I
|> commit, the number of packs change, and the performance is impacted.
|
| Yup :)
|
| -Rob

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

iEYEARECAAYFAkhr/EkACgkQJdeBCYSNAAMxzACgzTtwDV2tKK8HWGlzCUTLVkT/
tX8AnRU5UslLUQdnwHtaOwNjEoAEgeTj
=gjbJ
-----END PGP SIGNATURE-----