Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Hash-based bisect debugging in compilers and runtimes

research.swtch.com

Post reply on HN
Print view View original

11–20 of 48 posts

Re: Hash-based bisect debugging in compilers and runtimes

#11

Post by rsc »

carry_bit wrote: post #6

A closely related technique for debugging optimization passes is that of "optimization fuel". Each rewrite decreases the fuel by one, and when the fuel is gone no more rewrites happen. You can then perform binary search on the optimization fuel to find a specific rewrite instance that breaks things.

Yes, I believe LLVM has a flag for "run only the first N optimization passes" that gets used with binary search this way.

A global optimization fuel that worked at finer granularity would be even more precise but you'd have to have the compiler run single-threaded to make sure the numbering always matches. At least in the Go compiler, we compile different functions in different threads, so that fouls up any global numbering.

Re: Hash-based bisect debugging in compilers and runtimes

#12

Post by drivebycomment »

In my former life, I used to maintain a script that can be given two sets of objects files, one compiled with optimization, and one without, and the script will effectively do a binary search by choosing which object files you link and run the executable to determine success/fail. Each iteration is quick, since linking step is usually fast. This was useful when troubleshooting a big binary, since optimized build back then was often quite slow for a large executable.

Re: Hash-based bisect debugging in compilers and runtimes

#16

Post by eru »

Scaevolus wrote: post #9

Aside: bisecting flakes doesn't have to involve repeated runs. You can reformulate bisection as an information probing operation, expanding the scope to support noisy benchmarks or low-probability flakes. Bayesian inference narrows down the probable range of the failure for each new observation, and you can choose new probes to maximize information gain-- or even run them in parallel to minimize the total time. You d…

Could you briefly sketch out the math (or point to a sketch) so that other people can pick it up? I'm quite interested!

(I suspect you could get pretty far with a Monte Carlo simulation, and that would let you bypass most of the math anyway.)

Re: Hash-based bisect debugging in compilers and runtimes

#17

Post by ajb »

eru wrote: post #16
Scaevolus wrote: post #9

Aside: bisecting flakes doesn't have to involve repeated runs. You can reformulate bisection as an information probing operation, expanding the scope to support noisy benchmarks or low-probability flakes. Bayesian inference narrows down the probable range of the failure for each new observation, and you can choose new probes to maximize information gain-- or even run them in parallel to minimize the total time. You d…

Could you briefly sketch out the math (or point to a sketch) so that other people can pick it up? I'm quite interested! (I suspect you could get pretty far with a Monte Carlo simulation, and that would let you bypass most of the math anyway.)

Here is a doc explaining a Bayesian search algorithm; not sure if it's precisely what GP has in mind.

https://github.com/Ealdwulf/BBChop/blob/master/BBChop/doc/Ba...

(Edit- had wrong link originally)

Re: Hash-based bisect debugging in compilers and runtimes

#18

Post by rsc »

millipede wrote: post #13

Are there any non-compiler use cases for this technique?

Anyone working on libraries that are used by large programs can use them, like in the sort and timer cases described toward the end of the paper. When you work on libraries used by other larger programs you inevitably break them accidentally. This technique pinpoints the exact context of the breakage.

Re: Hash-based bisect debugging in compilers and runtimes

#19

Post by Twirrim »

millipede wrote: post #13

Are there any non-compiler use cases for this technique?

All sorts of stuff, I git bisect reasonably regularly.

You can even do things like automatically git bisect the linux kernel, with a little care. I wrote this up a few years ago https://paulgraydon.co.uk/posts/2020-12-27-automated-kernel-....

I can't talk about the actual case that lead me to ever need to git bisect a kernel in the first place, but at the same time I also learned how to make a minimalist one-C-file initrd, because what I needed to catch was visible under a /sys or /dev mount, or something like that. I later realised it's possible to do the same thing with Go in slightly easier syntax, if you cajole it in to producing a statically compiled binary!

Re: Hash-based bisect debugging in compilers and runtimes

#20

Post by dwattttt »

eru wrote: post #16
Scaevolus wrote: post #9

Aside: bisecting flakes doesn't have to involve repeated runs. You can reformulate bisection as an information probing operation, expanding the scope to support noisy benchmarks or low-probability flakes. Bayesian inference narrows down the probable range of the failure for each new observation, and you can choose new probes to maximize information gain-- or even run them in parallel to minimize the total time. You d…

Could you briefly sketch out the math (or point to a sketch) so that other people can pick it up? I'm quite interested! (I suspect you could get pretty far with a Monte Carlo simulation, and that would let you bypass most of the math anyway.)

For Bayesian Inference, the example in the Wikipedia article is good (who doesn't like cookies?): https://en.m.wikipedia.org/wiki/Bayesian_inference#Examples

When gathering more evidence, you'd use your new belief about which cookie bowl Fred has as P(H1)=0.6 and P(H2)=0.4

Post reply on HN