Re: [PATCH] rebase: be cleverer with rebased upstream branches

["Santi Béjar" <santi@agolina.net>]

On Sun, Mar 13, 2011 at 11:57 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:
>
>> 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.506s
>
> I 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.

Here the merge-base strategy mean take all the reflog at once. And in this
case the reflog is 1000 entries long, it is only relevant to the u@{1000}
case. For me it is more like: take the solution and check that indeed it is
the solution. In this sense it is the "minimum" time required to find the
solution.

>
> 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.

exp(n,m) is similar to this. But, yes, we could have a merge-base(N)
strategy which checks using the merge-base technique the first N reflog
entries, then the next N entries, and so on. But I think it would scale worst
then the exponential strategy.

>
> 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).

Indeed it is "Is the tip good? tip@{1},tip@{2}? tip@{4},tip{5},...,tip@{8}?
... and the merge-base techinque is used to answer each question.

>
> 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.

But if the answer is the last entry in the reflog (as in the u@{1000} case) it
is a lower limit, see above.

>
> 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.

Maybe I'm wrong, but from the number I see that the exp strategy this
"optimize for the common case and works reasonably work for pathological
histories".

>
> Is it easy to tell in an earlier phase if the history is "force-updated"
> or not?
>

I'm afraid this is a similar question.

HTH,
Santi