[merge] InterKnit.join() doesn't need the complete revision graph

[John Arbash Meinel]

Robert Collins wrote:
> On Fri, 2006-09-08 at 20:27 -0500, John Arbash Meinel wrote:
>> John Arbash Meinel wrote:
> 
>>> Also, would it be reasonable to use merge_sort() since that seems to be
>>> faster than topo_sort?
> 
> It shouldn't be faster! If it is, then topo_sort can be made faster
> still.

It seems to be taking much too long to do 'topo_sort' for 10K revisions.
However, I was basing it mostly on the original implementation of
topo_sort which did a lot of extra handling. I can see that you have
already replaced it.

Maybe it was the interaction with lsprof. I did some direct testing, and
topo_sort() takes 110-140ms for the same graph, versus merge_sort taking
  180-220ms.

And then testing under lsprof it takes topo_sort 970ms versus 1s for
merge_sort.

So I'm surprised to see the difference being 8x slower under lsprof, but
there is something we do which it penalizes more than others.

So we do need to be careful with trusting lsprof results, even though I
think it is frequently very revealing. The above test would show that
under --lsprof merge_sort costs the same as topo_sort, but under
real-world situations, topo_sort is almost 2x faster.

...

> Does this change handle ghosts properly? If it passes tests it should,
> but thats my recollection of the reason to grab the full graph. Perhaps
> this is a race condition with how the knit code came together. Anyhow,
> if its not the full_list anymore, please rename the variable, and look a
> little larger in scope - you may find this is a fully redundant lookup.

Thanks for the pointers, probably there is something else that can be
done. I just saw it as very expensive according to lsprof, but really
that is lsprof making topo_sort more expensive than it really is.

John
=:->




-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 254 bytes
Desc: OpenPGP digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060911/75597e31/attachment.pgp