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

On Fri, Jan 17, 2025 at 09:31:56AM +0400, Askar Safin wrote:

Me too. But that doesn't make it any easier to figure out a more optimized algorithm. ;)

In the meantime, here are some other options:

  1. You can manually pick a commit that is around the midpoint of
     history and try it. That will quickly reduce the search space to
     something more manageable. E.g., maybe try v4.0 and v5.0 and use
     those as your initial good/bad starting points (depending on the
     result). Those might not be the exact halfway point, but it's good
     enough to get started.

  2. In a branchy history like linux.git, you can make the problem space
     much smaller by looking only at the history along the first parent.
     E.g.:

       git bisect start --first-parent
       git bisect good v3.0
       git bisect bad v6.13-rc7

     That runs in about 7 seconds for me. It will probably give you a
     merge commit rather than the exact culprit along the second-parent
     history. But with that merge commit, you can start a new, much
     smaller bisection with it as the "bad" and its first-parent as the
     "good".

Both of those are trading a bit of accuracy in finding the exact midpoint in the early steps. It's perhaps another possible option for git-bisect itself: if we see a very large number of commits, we could try to approximate rather than finding the exact answer. In most histories I'd expect that taking the midpoint of a linearized topo-order would get you a pretty reasonable outcome. E.g.:

  total=$(git rev-list --count v3.0..v6.13-rc7)
  git rev-list --topo-order v3.0..v6.13-rc7 |
  tail -n +$((total / 2)) | head -n 1

runs in about 2s on my machine. The commit it finds, ed194d136769, is pretty close to the middle:

  $ git rev-list --count v3.0..ed194d136769
  526863
  $ git rev-list --count ed194d136769..v6.13-rc7
  543312

-Peff