3 ms·
git literally has built-in tooling for this. It's called bisect (and they literally mention "bisection" in the next sentence).
by xfmpXIe76lF4GfR 4y ago
git literally has built-in tooling for this. It's called bisect (and they literally mention "bisection" in the next sentence).
- howinteresting 4y agoThe builtin tooling is insufficient for many purposes, including if your bisect algorithm requires you to run tests across many machines. Many large projects write their own bisect framework because of this.
- Too 4y agoIt is intuitively a bit hard to believe, but bisecting in parallel is actually not much faster than serial. In my experience you just save the final one or two steps in the bisection - regardless of how long the range is! Imagine bisecting builds with parallelism of two, when one of them completes, there is a 50% chance that the build on the other side of the range is now uninteresting. If you are lucky and it is interesting, you’ve only saved yourself half a step in the bisection, because when running in parallel you sliced the range in 3 rather than 2. Adding even more parallelism just makes this effect even worse. Someone can probably work out the math better than me but you can quickly see that for 2x build power you instantly waste half the results for very marginal gain. Just comparing the big O should also tell you this, parallelism only buys you O(N) while bisecting is O(log N).