B+Tree indices: ongoing progress

[Robert Collins]

On Tue, 2008-07-01 at 22:46 -0500, John Arbash Meinel wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Robert Collins wrote:
> | On Wed, 2008-07-02 at 13:19 +1000, Robert Collins wrote:
> |
> |
> |> And some good news:
> |> Baseline overhead: Read 92994 keys in 7.075
> |> GraphIndex: Wrote 10147567 bytes in 10.949
> |> GraphIndex: iter_all_entries in 9.671
> |> GraphIndex: iter_random_one in 11.915
> |> GraphIndex: get_components_positions(2000) in 20.535
> |> GraphIndex: search_from_revid in 6.516
> |> GraphIndex: miss torture in 343.138
> |> GraphIndex: -------Done---------
> |> Baseline overhead: Read 92994 keys in 7.072
> |> BTreeIndex: Wrote 4104336 bytes in 20.299
> |> BTreeIndex: iter_all_entries in 1.850
> |> BTreeIndex: iter_random_one in 115.365
> |> BTreeIndex: get_components_positions(2000) in 33.332
> |> BTreeIndex: search_from_revid in 4.581
> |> BTreeIndex: miss torture in 41.803
> |> BTreeIndex: -------Done---------
> |>

On the same repository, with bloom filters added:
Baseline overhead: Read 92994 keys in 6.734
BTreeIndex: Wrote 4108432 bytes in 28.415
BTreeIndex: iter_all_entries in 1.955
BTreeIndex: iter_random_one in 120.980
BTreeIndex: get_components_positions(2000) in 40.829, bloom(144839)
BTreeIndex: search_from_revid in 6.911, bloom(32233)
BTreeIndex: miss torture in 53.916, bloom(413765)
BTreeIndex: -------Done---------

Which is to say - we avoid 100's of thousands of leaf lookups but the
cost of the (sha1 based) bloom lookups exceeds the cost of checking
locally. I think the easiest way to test this is to drop disk caches
before running the test loop, and I'm about to do that.

-Rob




-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080702/744c9d13/attachment.pgp