Martin von Zweigbergk <martin.von.zweigbergk@xxxxxxxxx> 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?
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html