B+Tree indices: ongoing progress

[Robert Collins]

So, with the sketch showing promise, I think this is worth doing a
spike/mini sprint on - if we can drop this in with the stackable format,
it could take us a step towards addressing some of our intrinsic
performance issues. Or not. Either way, I'm going to keep at it for at
least a bit more.

I am writing a script to test the performance of the new index, by
comparing it to the indices from an arbitrary repository. I'm
refactoring my adhoc stuff to be more repeatable.

The first thing is that jam's new tighter compression _really_ affects
index creation time. The following is using my copy of bzr.dev's
indices:

Baseline overhead: Read 92994 keys in 7.583
GraphIndex: Wrote 10147567 bytes in 11.921
BTreeIndex: Wrote 5722256 bytes in 13.481

Baseline overhead: Read 92994 keys in 7.531
GraphIndex: Wrote 10147567 bytes in 11.870
BTreeIndex: Wrote 4104336 bytes in 21.608


The first set of figures are with index2 rev 7; the second with index2
rev 8. So rev 8 is a huge increase over the current GraphIndex for
writes, and 50% increase in time over rev 7, for a 28% reduction in size
vs rev 7, and 60% reduction vs GraphIndex.


Also, regarding zlib object copying:
>>> import zlib
>>> c = zlib.compressobj()
>>> c.copy()
<zlib.Compress object at 0x7f21b6ee2dd8>

so my python has it - if yours doesn't, then that backs up my theory
that it would be a hassle to use it :). Though we could try and
fallback...

-Rob


-------------- next part --------------
A non-text attachment was scrubbed...
Name: indexbench.py
Type: text/x-python
Size: 2374 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080702/f5d4cf12/attachment-0001.py 
-------------- 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/f5d4cf12/attachment-0001.pgp