Re: first bisection step takes quite a while

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

Uwe Kleine-König <u.kleine-koenig@baylibre.com> writes:

> Hello Junio,
>
> On Thu, Feb 20, 2025 at 05:40:53PM -0800, Junio C Hamano wrote:
>> Comments?
>
> It's long time ago that I looked into the git source code and I guess
> many things have changed since then.

;-)  Apparently not much has changed around this area.  I was amazed
how things haven't changed around the code since I wrote it in 2007
with "the clever trick" to improve what Linus called "truly stupid"
algorithm.  No, I didn't improve the stupid algorithm.  The clever
trick was to reduce the need to call it.

> Anyhow, here comes my thought about how finding a bisection point could
> work.
>
> Pick the middle commit of `git rev-list --topo-order $bad ^$allgood`.
> Lets assume this are 10000 commits. Check the weight of commit[5000].
> Depending on how much the weight is off from 5000 make a bigger or a
> smaller step up or down to find the next commit to check. So a scaled
> bisection on the topo-order commit list. I think that doesn't
> necessarily finds a best bisection point, but I havn't thought about
> that a lot.

Since the name of the game is to find "a" good enough point in the
earlier part of a huge bisection session, that certainly is good way
to think about the problem space.  The commit[] array you have may
not be a linear single-strand-of-pearls history, and a naïve
bisection would not work well in such a case, so we have to be a bit
more careful here.

The code I touched in the illustration needs to either find a merge
commit that is really good enough and leave early, or if there is no
such merge commit, compute how many other commits in the range each
and every merge commit in the range that can be the ancestor of 
the best non-merge commit on a single-strand-of-pearls history.

Thanks.