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

From: Jeff King <peff@peff.net>
Date: Jan 16, 2025, 10:52 UTC
Message-ID: <20250116105246.GF773990@coredump.intra.peff.net>
In-Reply-To: <CALnO6CAzN1oeT4tMjJ1Qm4dW0xdVkVKHJ39oJTX8R8E614FH6g@mail.gmail.com>

On Tue, Jan 14, 2025 at 05:21:20PM -0500, D. Ben Knoble wrote:

Show 8 quoted lines

> FWIW:
> 
> $ time git rev-list --count v3.0...v6.13-rc7
> 1070175
> git rev-list --count v3.0...v6.13-rc7  13,57s user 1,41s system 96%
> cpu 15,466 total
> 
> That's a large number of revisions to bisect. Further,

Yeah. I'm not very familiar with the bisect code, but it looks like it's quadratic. In do_find_bisection(), we have a big list of commits, and we iterate like this:

        for (p = list; p; p = p->next) {
                if (p->item->object.flags & UNINTERESTING)
                        continue;
                if (weight(p) != -2)
                        continue;
                if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)
                        BUG("shouldn't be calling count-distance in fp mode");
                weight_set(p, count_distance(p));
                clear_distance(list);

                /* Does it happen to be at half-way? */
                if (!(bisect_flags & FIND_BISECTION_ALL) &&
                      approx_halfway(p, nr))
                        return p;
                counted++;
        }

That clear_distance() call likewise iterates through the list to clear the COUNTED flags from each. I guess we might be able to traverse down from the tip of the commit we're operating on, clearing flags there. Since that's how the flags are set in count_distance().

I suspect it's still quadratic, though, because count_distance() is traversing separately for each (and in the worst case everything is reachable from it). But it might still improve things in practice.

-Peff