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

Martin von Zweigbergk [off-list ref] 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.

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?