B-Tree performance analysis

[John Arbash Meinel]

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

I've been poking around with the b-tree *creation* performance, and thought I
would mention a few things.

1) If we don't compress at all, my mostly bzr repository indices become 24.7MB
in size. That is actually significantly large than GraphIndex at 12MB. I
assume this is because GraphIndex does an offset-compression (keys are
referenced by their offset in the index, rather than the raw tuple.)
It still takes around 5.5s to do so.

2) I played around a bit with a compression scheme that doesn't involve
"repack". Basically, after you've done X amount of ZSYNC_FLUSH calls, you just
stop trying any harder to fit more onto the page. This is the only way to get
a single-compression pass over the data. Otherwise when the last key doesn't
fit, you have to recompress.

I tried using .copy() and just saving the last one. But it turns out that
.copy() really is a slow function. Calling it 12-ish times (for all the ZSYNC
calls) is slower than just recompressing again. Looking at the function, it
involves 5+ ZALLOC calls, and some memcpys.

Anyway, the fastest (reasonable) 1-pass compression gives:
6.5s to compress, 5.8 MB result. A minor tweak for 6.6s gives 5.5 MB. You can
scale this up so it starts having to repack, as a 2-pass compression which is
7.5s and 4.6MB. Or 3-pass compression for 8.4s 4.2MB.

nocomp	5.5s	24.7MB
1-pass	6.5s	 5.8MB
1.5-pa	6.8s	 4.9MB
2-pass  7.5s	 4.6MB
3-pass  8.4s	 4.2MB
N-pass 11.1s	 4.1MB

Obviously I think at least 1-pass compression is important, because the btree
code was written to use a bit of compression rather than doing the
offset-compression GraphIndex uses.

3) I was surprised that with no-compression we still took 5.5s to build all
the indexes. It turns out that we spend a moderate amount of time in the
GraphIndex.add_node code.

  With no compression we have:
    a) 3.8s GraphIndex.add_node
        1. 1.0s spent _check_key necessary? perhaps just optim it
        2. 1.6s updating _nodes_by_key, necessary?
        3. 1.3s other

    b) 1.7s Builder.finish
	probably mostly in the iter(sorted(_iter_memory_nodes())), which
        basically has to re-sort the keys because they are in an in-memory
        dict _nodes. lsprof put the sorted() call at about 0.88s.

So with 1-pass compression, we only spend 1s in the ChunkWriter.write() code.
And there are other places that need to be tuned to be faster. For example, do
we really need to maintain the _nodes_by_key map? It is only used when we
"iter_entries_by_prefix". I couldn't find any other uses. I begin to think it
really should be generated "on-demand". It can be kept cached on the
GraphIndex, but it doesn't need to be updated during Builder time.

_check_key() I'm pretty hesitant to get rid of this, but we do spend a
significant amount of time there.

Anyway, we might want to consider tuning the system to be extra fast during
normal operation, and then go to N-pass system for 'bzr pack'.

What do you think abut stuff like "updating _nodes_by_key"?

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFIsJrOJdeBCYSNAAMRAvJxAJ0dwbhPnj+Z+zd3ugvMOyEd8BPT6ACfcork
9X0VmLSF0xEUwQA5Ex2bXz8=
=P7Zs
-----END PGP SIGNATURE-----