Hacker News Reader

Comment by LegionMammal978 | Hacker News Reader

I've always wished for a "git trisect", or a "git n-sect" in general, that can try multiple commits in parallel. The use case would be for testing changes in software that has a long, single-threaded component in the build process (e.g., a heavily overloaded configure script). For long-running projects where each bisect takes over a dozen steps, those components lead to lots of thumb-twiddling.

View on HN

The magic of bisect is that you rule out half of your remaining commits every time you run it. So even if you have 1000 commits, it takes at most 10 runs. An n-bisect wouldn't be that much faster, it could be slower because you will not always be able to rule out half your commits.

Yes, but I could also see the case where you have 10 commits to check, each bisect takes 20 minutes and it takes 40 minutes to find the problem.

Or 20 minutes if you had 10-'sect.

The idea is, suppose I did a trisect, splitting the range [start,end) into [start,A), [A,B), and [B,end). At each step, I test commits A and B in parallel. If both A and B are bad, I continue with [start,A). If A is good and B is bad, I continue with [A,B). If both A and B are good, I continue with [B,end).

This lets me rule out two thirds of the commits, in the same time that an ordinary bisect would have ruled out half. (I'm assuming that the tests don't benefit from having additional cores available.) In general, for an n-sect, you'd test n - 1 commits in parallel, and divide the number of remaining commits by n each time.

have you ever seen this implemented somewhere ? interesting idea

No, unfortunately not. If your history is strictly linear, you could probably hack together something relatively simple on top of git rev-list. But git bisect does all sorts of magic to deal with merge commits and other funny situations, and generalizing that to an n-sect would take a fair bit of work.

Yes, you'd need 4x parallelism for a 2x speedup (16x for 4x, etc). But there's plenty of situations where that would be practical and worthwhile (think a build and test cycle that takes ~1 hour each and can't be meaningfully parallelised further).

I think you'd have to hack it together on a per-project basis, but could you do it with containers? You'd have to identify the point where the build process diverges, make n copies of the container...

(If I'm understanding you correctly).

But there's not much that's faster than a binary search.

The problem isn't actually running the builds, so much as selecting the commits. Ordinary bisect gives you one commit to test at each step, and one result to report. But I want to be given n - 1 commits at each step, evenly spread out along the search range, and I want to report all n - 1 results at once, to cut the range by a factor of 1/n. If the testing process doesn't utilize all available cores, this will be faster than just testing commits one at a time.

Reply on news.ycombinator.com