[MERGE] btree prefetch

[John Arbash Meinel]

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

This patch adds prefetching to btree indexes.

The algorithm there just follows from what I've posted before, and
should be well documented in 'doc/developers/btree_index_prefetch.txt'.

It adds LRUCache.keys(). I prefer to do it that way rather than calling
.get() and messing up the LRU portion of the cache. (It would attribute
more requests for nodes that we decide not to request.)

In testing, most operations are faster. I feel like I have been able to
come up with a good background for each step and why we do/don't want to
expand the request.

As a best case, 'bzr log --long -r -10..-1' time is cut in half (15s
versus 31s). We actually need to read the whole index for 'bzr log
- --long' anyway. That is compared to 28.3s for the old index format, so
it is nice to be a bit better.

I might recommend that we decrease the recommended page size to 32kB, or
alternatively change the code to make it dynamic based on actual
bandwidth and latency. (I think my specific connection puts it around
16-32kB.)

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

iEYEARECAAYFAkj1EWYACgkQJdeBCYSNAAPMAgCdGdQ/js3fa1ikxdh8zj1rMwCG
Ls0An3R1nPtJ1UV6IC0VdRo4NhmC79iU
=8Oxy
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: btree_buffer.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20081014/02c5ec07/attachment-0001.diff