Re: merge-base: update the clean-up postprocessing

[Junio C Hamano <junkio@cox.net>]

Junio C Hamano <junkio@cox.net> writes:

> A fixed up version of this patch, along with your updated test,
> is at the tip of "pu".
>
> It does affect the processing time for cases where there are
> more than one merge bases negatively.  To compute all merge-base
> for the 23 merges in the kernel reporitory, the old code with
> the "contaminate the well a bit more" clean-up phase takes 2.5
> seconds, while the new code takes 3.9 seconds.
>
> Processing all 2215 merges in the kernel repository (the other
> 2192 merges have one merge-base between the parents) takes 160
> seconds either way.  In other words, multi merge-base merges are
> relatively rare and a bit more time spent to clean-up with the
> new code is lost in the noise.
>
> The numbers are taken from /usr/bin/time on an Athron 64X2 3800.

I did a similar test on git.git repository.  Numbers are
interesting.

 * I have 941 two-head merges.  89 of them are multi-base
   merges.  This is unproportionally higher compared to the
   kernel repository.

 * Both the version in "master" (i.e. the one with the horizon
   effect) and this version with updated clean-up code produces
   identical set of merge bases for all 941 two-head merges.

 * The difference in processing time for 941 two-head merges
   with both versions is lost within margin of error.