Re: first bisection step takes quite a while

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 21, 2025, 17:29 UTC
Message-ID: <xmqqo6yvb40a.fsf@gitster.g>
In-Reply-To: <4hx5uvjy7mzntb5zp6o4dg3ut44i46bthyfuera3lnbpbcvrey@kbo3ejype7ae>

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

Show 7 quoted lines

> 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.

Show 10 quoted lines

> 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.