Re: [PATCH] rebase: be cleverer with rebased upstream branches
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Mar 13, 2011, 22:57 UTC
- Message-ID
- <7vd3luhbmt.fsf@alter.siamese.dyndns.org>
- In-Reply-To
- <alpine.DEB.2.00.1103122159300.15442@debian>
Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:
Show 20 quoted lines
> So here are the updated figures for the force-updated history
> (pu-like):
>
> u@{10} u@{100} u@{1000}
> manual 0m0.535s 0m1.164s 0m1.415s
> linear 0m1.245s 0m37.367s 5m10.068s
> merge-base 0m14.490s 0m15.409s 0m15.508s
> exp(1,2) 0m1.056s 0m6.175s 0m27.221s
> exp(10,10) 0m1.950s 0m20.031s 0m18.215s
> exp(7,7) 0m1.310s 0m6.851s 0m16.757s
>
> and for the non-force-updated history (master-like):
>
> u@{10} u@{100} u@{1000}
> manual 0m0.885s 0m6.126s 0m52.248s
> linear 0m1.349s 0m39.688s 5m28.753s
> merge-base 0m1.160s 0m1.699s 0m1.901s
> exp(1,2) 0m0.769s 0m4.342s 0m7.360s
> exp(10,10) 0m0.700s 0m2.535s 0m3.110s
> exp(7,7) 0m0.653s 0m2.332s 0m3.506sI have a suspicion that merge-base shouldn't be taken as "one of the candidates among others".
It is merely a technique to check multiple heads simultaneously and cheaply, instead of checking things one by one, and should be applicable regardless of these "multiple heads" come from. It may come from a linear walk of reflog, or it may come from a leaky exponential or fibonacci walk.
Instead of "linear" that checks "Is the tip good? Is the tip@{1} good? Is the tip@{2} good? How about tip@{3}?" repeatedly, we can check "is the tip through tip@{N} good?" with a single invocation using the merge-base technique.
Similarly if your exp(i,j) checks "Is the tip good? tip@{1}? tip@{2}? tip@{4}? tip@{8}? ..." iteratively, you can grab these commit object names out of reflog and still use the merge-base optimization, effectively making "one at a time" check into "N at a time" check (perhaps checking a dozen or two at a time).
If you generate list of reglog entries way beyond what matters to the end result, and feed all of them to the machinery, it is not surprising that it would spend more time than linear that can stop early upon the first success.
We should optimize for common case by picking the default that performs well for history that is never rewound. If the the default algorithm on pathological histories performs badly, it is Ok to have an alternative heuristics that is only triggered on such a history, but if we are going to do so, we need to make sure that we can cheaply detect if we need to use the alternative heuristics in the first place.
Is it easy to tell in an earlier phase if the history is "force-updated" or not?