Re: [PATCH] bisect: loosen halfway() check for a large number of commits

[Junio C Hamano <gitster@pobox.com>]

SZEDER Gábor <szeder.dev@gmail.com> writes:

> However, when we have thousands of commits it's not all that important
> to find the _exact_ halfway point, a few commits more or less doesn't
> make any real difference for the bisection.

Cute idea.

> So I ran some tests to see how often that happens: picked random good
> and bad starting revisions at least 50k commits apart and a random
> first bad commit in between in git.git, and used 'git bisect run git
> merge-base --is-ancestor HEAD $first_bad_commit' to check the number
> of necessary bisection steps.  After repeating all this 1000 times
> both with and without this patch I found that:
>
>   - 146 cases needed one more bisection step than before, 149 cases
>     needed one less step, while in the remaining 705 cases the number
>     of steps didn't change.  So the number of bisection steps does
>     indeed change in a non-negligible number of cases, but it seems
>     that the average number of steps doesn't change in the long run.

It somehow is a bit surprising that there are cases that need fewer
steps, but I guess that is how rounding-error cuts both ways?

>   - The first 'git bisect start' command got over 3x faster in 456
>     cases, so this "no commit at the exact halfway point" case seems
>     to be common enough to care about.

In any case, I like the re-realization that the counting reachable
commits in a mergy history is costly (see comments before the
count_distance() function that we already knew it from the
beginning, though), and the general idea of speeding up the entire
thing by avoiding the cost we need to pay in the count_distance()
function, which my earlier 1c4fea3a (git-rev-list --bisect:
optimization, 2007-03-21) also did.

    Side note.  I've been waiting for all these years to see
    somebody new comes up and makes a fundamental change to
    count_distance() such that it no longer is costly---alas,
    that hasn't happened yet.

Mildly (only because such a bisection session over a long span is
rarer) excited to see this RFC completed ;-)