B+tree discussions

[Robert Collins]

iter_random_one was spectularly slow. 60% of it was in split-lines - so
here with figures from using a C parser.
C parser:
Baseline overhead: Read 92994 keys in 7.648
BTreeIndex: Wrote 4313232 bytes in 22.536
BTreeIndex: iter_all_entries in 1.067
BTreeIndex: iter_random_one in 78.722,
BTreeIndex: get_components_positions(2000) in 41.621,
BTreeIndex: search_from_revid in 3.531 found 18130,
BTreeIndex: miss torture in 22.631,
BTreeIndex: -------Done---------
Baseline overhead: Read 92994 keys in 8.267
GraphIndex: Wrote 10147567 bytes in 11.335
GraphIndex: iter_all_entries in 11.434
GraphIndex: iter_random_one in 11.972,
GraphIndex: get_components_positions(2000) in 24.518,
GraphIndex: search_from_revid in 7.872 found 18130,
GraphIndex: miss torture in 380.569,
GraphIndex: -------Done---------

With the python parser:
Baseline overhead: Read 92994 keys in 11.097
BTreeIndex: Wrote 4313232 bytes in 23.224
BTreeIndex: iter_all_entries in 1.860
BTreeIndex: iter_random_one in 116.968,
    bloom(0) leaf_value(0,0) miss(0), internal(39710,5),
    leaf_node(50025,41865) bisect(131605,0)
BTreeIndex: get_components_positions(2000) in 49.052,
    bloom(0) leaf_value(0,0) miss(559318), internal(376,5),
    leaf_node(8490,5782) bisect(49,261139)
BTreeIndex: search_from_revid in 3.666 found 18130,
    bloom(0) leaf_value(0,0) miss(416678), internal(0,0),
    leaf_node(15735,197) bisect(3793,81195)
BTreeIndex: miss torture in 22.691,
    bloom(0) leaf_value(0,0) miss(2326050), internal(0,5),
    leaf_node(0,560) bisect(0,639998)
BTreeIndex: -------Done---------

(this is pushed up naturally).

-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/20080703/c659ec05/attachment.pgp