New toy for bzr developers: B+Tree index sketch

[Robert Collins]

On Wed, 2008-07-02 at 22:49 +1000, Ian Clatworthy wrote:
> Robert Collins wrote:
> > On Wed, 2008-07-02 at 22:28 +1000, Ian Clatworthy wrote:
> > 
> > 
> >> Here are the performance figures from indexbench.py. OOo ...
> > 
> > These paint a very interesting picture. 
> > 
> > In summary:
> > pack reading - massively faster at scanning indices which we do to
> > combine two packs.
> > 
> > Fully random access: consistently slower. We yet to determine the cause.
> > 
> > Text extraction planning - consistently faster - 2 to 4 times faster.
> > 
> > Getting a revision history, from ~ the same to 4 times faster.
> > 
> > Writing - from 1/2 the speed (59725 keys) to about the same (1149504)
> > - which suggests that for millions of keys the version you tested will
> > be faster.
> 
> And writing has two aspects: everything and incremental. I'm guessing
> commit is incremental (or ought to be). If so, the incremental write
> speed is one we need more information about, yes?

there are really three sizes of writes we do:
 - initial commit (size of tree)
 - varying packs (up to size of history, but amortised over time)
 - incremental commits (size of delta)

For the very small the time to write the index is so small it hardly
matters compared to other inefficiencies in commit etc.
For the very large this format appears better than what we have today.
For the range in the middle (e.g. initial commit) its slower (on the
order of 10's of seconds slower).

> What commands does Fully Random Access speed impact?

I'm not entirely sure :). But its a useful thing to know - its roughly
sum(time to access every key), but done to exercise the caching
facilities heavily. 'info' is likely to use this, and other history
analysing things like reconcile.

-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/20080702/9d0d36ae/attachment.pgp