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

From: Junio C Hamano <gitster@pobox.com>
Date: Jan 16, 2025, 16:40 UTC
Message-ID: <xmqqo706u2z0.fsf@gitster.g>
In-Reply-To: <20250116135227.GA2323616@coredump.intra.peff.net>

Jeff King <peff@peff.net> writes:

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

It is somewhat embarrassing and amusing at the same time that the "This is a truly stupid algorithm, but it's only used for bisection, and we just don't care enough." comment Linus wrote long time ago is still with us. Many men tried, they did not die but failed.

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

The original algorithm was done way before any of the recent auxiliary data structures were invented. There may be approaches we haven't tried and can now try to improve bisection, expoliting newer things like reachability bitmaps.