B+tree discussions

[John Arbash Meinel]

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

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

This is nice to see. It is unfortunate that you are using memrchr which
is a GNU extension to the C standard library. (eg, not available on
Windows, and maybe not on Mac.)

But I think I had written an alternate implementation anyway, so I'll
dig that up.

John
=:->


| 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

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

iEYEARECAAYFAkhs5ggACgkQJdeBCYSNAAMcKgCgj/mcYiegscpe4dNpPlePQci4
sOcAnAyu7NTvX3yeLWebEF3ZhCbmHDDf
=Mqjo
-----END PGP SIGNATURE-----