From: Jeff King <peff@peff.net>
Date: Thu, 16 Jan 2025 13:52:27 GMT
Subject: Re: [bug] "git bisect old v3.0" takes 21 mins on Linux repo
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:

> 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