brisbane: initial cut at a mergeline cache

[Ian Clatworthy]

When I was tuning log during 1.12, there were 2 things I
couldn't fix at the time:

* the speed of log -v
* the speed of log -rx.y.z

The first is addressed by brisbane-core's new repo format.
The second is slow because the lookup of a dotted revno
builds the *full* revno-to-rev-id-map(). For Emacs on
my desktop, that would mean 18 seconds to log a *single*
non-mainline revision. On my laptop, the speed was twice as
slow. IIUIC, on OOo, the time is around 100 seconds. :-( :-(

The attached patch largely fixes this problem. Instead of
building the full map each time, it builds it once and then
keeps the length and last-rev-id of each "mergeline". That
means the lookup of x.y.z is now the time to find the record
for x.y and walk backwards from the tip of that until z is
found (just like we do on the mainline).

Quick testing on a bzr branch shows that the time drops from
6.5 secs to less than a second. And bzr has 3300+ mergelines!
FWIW, the overhead of calculating the mergeline data to save
and writing it to disk is 0.1 secs, so that's peanuts compared
to the time to build the full merge-sorted graph.

Some other things to note:

1. I keep the branch last-rev-id at the time the data is saved and
   throw away the cache if the tip has changed. By doing this at
   lookup time, I avoid any overhead in write operations like commit.

2. The size of the mergeline-store file for bzr is 211K, about
   the same as dirstate. We could compress this easily to save
   space. We could also use a btree or chk store I guess.
   Someone tell me the best option here please!

3. Updating a cache in the middle of a 'read' operation causes
   grief I don't know how to fix. How does one go about promoting
   a read-lock to a write-lock in bzrlib?

4. This works for me but isn't ready for landing yet. I need answers
   to the above issues first and plenty of tests, of course.

Anyhow, I'm really pleased with this. I expected it to take me a
week to sort out (and it still might) but this is great progress
for an afternoon/evening's work.

Thoughts?

Ian C.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mergeline-cache.patch
Type: text/x-diff
Size: 18599 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20090330/6caab590/attachment.bin