Comment by infinity0 | Hacker News Reader

Comment by infinity0 | Hacker News Reader

> You decide to try running with optimizations 1-128 enabled, and 129-256 disabled. That run fails. Now you know that one of the first 128 optimizations is to blame. You try again with 1-64 enabled, and 65-128 disabled, and that run passes. The bad optimization must be between 65 and 128. Continuing in this fashion—a binary search—you're able to locate the faulty optimization in just eight steps.

This doesn't work for the case where the failure(s) might be caused by a combination of a subset of the optimisations. That is,

1000 0100 0010 0001

all succeed, but

0101

fails.

A binary search is not possible for these more complex bugs. We had such cases in the reproducible builds project.

For the case where you can assume (subset A exhibits a failure => any superset of A exhibits a failure), then you can just go through all the options (in the OP's case 256) and switch them on, one at a time. Then the running time is 256, not 8.

For more complex cases where you can't assume even that, then you're stuck indeed with 2^256 test cases.

I think for pairs you can still do a logarithmic search, it’s just not base 2.

A trinary or quaternary search should be able to find two bugs at once (and intuition tells me a quad search should be able to handle three).

Say you have 16 optimizations and 7 and 12 don’t work together. Eliminate the first half, the second half, the odd or the even opts and the build is still green. But if you remove the first third or quarter the tests still fail.

So in a trinary search you might see 1-16 -> 6-16 -> 6-13 -> 6-8,12-13 -> 6,7,8,12 -> 6,7,12 -> 7,12. Including the first and last sanity checks you’re in for about 8-14 test passes for 16 tests, which is a lot better than 2^16.

But there’s still a binary search you can do, and that’s a bisect of the commit history. Before some commit this bug didn’t happen. And that’s going to contain one half of the bug. Now you run a second binary search to find its complement.

Optimization fuel[1] is a neat solution: have the compiler perform only the first n optimization operations, then use binary search to find which operation was bad. You can then break execution at that point to see what is going wrong.

[1] http://blog.ezyang.com/2011/06/debugging-compilers-with-opti...

Reply on news.ycombinator.com