brisbane: initial cut at a mergeline cache

[Ian Clatworthy]

Robert Collins wrote:

> I appreciate we need to fix it. We've had a great deal of success
> analysing the root cause of performance isues and coming up with a
> design. Look at brisbane-core's disk format for instance - that took a
> bunch of effort to come up with a conceptually simple, elegant, and well
> performing solution.
> 
> So lets look at what is going on and why it needs a cache.

The root cause is well understood. The scheme we use for revision numbering
requires that the whole merge-sorted graph be calculated in order to
assign the y bit (at least) out of the x.y.z number. Numerous proposals
have been put forward about lazily calculating partial graphs - this is
*really* hard to make perform in all cases IIUIC.

Another option suggested is to change the numbering scheme altogether so
that x and y are related to where the branch gets merged into, not where
the branch originated from. I'm strongly against this - the current scheme
makes the most conceptual sense IMNSHO. We *can* make the current scheme
perform well - it just needs a small cache giving fast lookups for
revisions in recently added merges.

In the attached patch, I've made it the responsibility of the BranchFormat
to determine what the cache sizes are. A value of zero disables caching
altogether and that's the default for existing branch formats. I'm
proposing a new branch format where the # number of entries cached are:

* 1000 for local branches
* disabled for remote.

1000 entries requires 23K and takes 0.08secs to save and the same to load.
It is *only* saved the first time branch.iter_merge_sorted_revisions() is
called after a tip change. It is *only* loaded if a non-mainline revno
lookup is required. If we only cached 100 entries, it would take just 2.5K.
But on really active projects, 1000 merges ought to give a time horizon
of several months or hopefully a year. I'm prepared to argue that it's
OK if we're slow when a user is looking up an old, non-mainline revision.
Recently added ones though *must* be fast. If we can't agree on a number,
maybe it ought to be a config setting (with a small default).

<soapbox>
I've tired of hearing Bazaar is slow and hearing about how we're eventually
going to fix it. This fixes something now, giving huge gains on the very
sort of projects we want adopting us. If we have a better solution sometime
in the future, we can adopt that better solution *then*. This also isn't a
new idea - I've been putting forward my thughts about this ever since I first
released bzr-revnocache, including multiple emails to the list on what I
was looking to cache and why. Sorry to sound grumpy but being paranoid
about adding caches because they sometimes have problems is not good
science. Sometimes they work! In my experience over 20+ years of programming
large systems, *no* amount of "make the core code path faster" is ever
going to match a well-designed cache w.r.t. performance. And this cache is
well-enough-designed IMO.
</soapbox>

Anyhow, this code is now good enough to review. It needs plenty of
tests before landing, but I'd to like to get some answers first on how
the core developers think it can break, so I'm not burning time writing
tests for something that can't fly. Alternatively, I want to hear
how and when we think the problem can be fixed another way, and why
the other way will perform better.

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