On Tue, Jan 14, 2025 at 05:21:20PM -0500, D. Ben Knoble wrote:
> 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
