Caching 'dotted_revnos' and merge_sort

[Ian Clatworthy]

On 08/04/10 12:38, John Arbash Meinel wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
>>> Basically I'm wondering if the benefits of dotted revnos justify the
>>> costs (both in existing runtime, and in developer effort to optimise
>>> that runtime)?

I agree we ought to be asking this question. "Fast" is a large part of 
usable.

> I'm finishing up the 'lazy' merge_sort code in the plugin now. I have
> some basics working, but I think I'm missing some edge cases.
>
> Anyway, I'll let you know in a bit where I get to. I've found some
> decent bounds on all operations. Currently dotted_revnos do have more
> overhead than *just* merge_sort. (There are times when I can compute
> what revisions where merged, and not yet know what numbers to assign
> them.) But often it isn't far off.
>
> Well, I need to finish making it correct, and then run it on more real
> histories to see what bits I'm missing in my understanding... :) But at
> least for cases I've analyzed the bounds are generally "you have to go
> back to the originating revision, but no farther".

That sounds pretty promising. If we do change the numbering scheme for 
non-mainline revisions, let's make sure that the performance impact in 
both directions (revid <-> revno) is well understood and, ideally, as 
low as possible.

Ian C.