Re: [bug] "git bisect old v3.0" takes 21 mins on Linux repo

From: Jeff King <peff@peff.net>
Date: Jan 16, 2025, 13:52 UTC
Message-ID: <20250116135227.GA2323616@coredump.intra.peff.net>
In-Reply-To: <20250116125313.GA2301268@coredump.intra.peff.net>

On Thu, Jan 16, 2025 at 07:53:13AM -0500, Jeff King wrote:

Show 6 quoted lines

> I suspect that the whole bisection count algorithm needs to be rewritten
> to all run in a single traversal. I guess if you iterate over the
> commits in reverse-topo order, you should be able to just compute each
> distance as "d(commit) = 1; d(commit) += d(p) for parents(commit)". But
> it's not a problem I've thought a lot about, so I'm probably missing
> some subtlety.

Oh nevermind, that won't work, as it double-counts commits that are reachable from each parent. Still, it feels like there ought to be a way to compute it with a single traversal.

I think this is similar to the reachability bitmap computation, which computes a bitmap for each commit (and then the weight of each commit is the number of set bits, but we've removed the duplicates). We do that in a single traversal these days, but it's pretty complex and heavyweight.

So I think there's room for improvement here, but it sounds non-trivial.

-Peff