31–40 of 48 posts
Earlier quoted context omitted.
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)
And there is a script bisecting functions when given assembly produced by working baseline and “bad” compiler to compare: https://github.com/llvm/llvm-project/blob/main/llvm/utils/ab...
LLVM can bisect down to individual transformation steps within a pass (for passes that implement the interface): https://llvm.org/docs/OptBisect.html And there is a script bisecting functions when given assembly produced by working baseline and “bad” compiler to compare: https://github.com/llvm/llvm-project/blob/main/llvm/utils/ab...
Also, hi Matthias!
I went so far as to find the commit where David Chase added for loopvar on Mar 6, 2023 (github: golang/go/commit/c20d959) to try to design my own hello world with x/tools/cmd/bisect, but I'm out of my depth.
The hash tree is a great visualization. I wouldn't have grasped the importance of the hash suffix until I saw the tree. Awesome stuff.
In the event that this is added to the standard library, I'm going to be really curious to see what a "hello world" project/example would look like. I went so far as to find the commit where David Chase added for loopvar on Mar 6, 2023 (github: golang/go/commit/c20d959) to try to design my own hello world with x/tools/cmd/bisect, but I'm out of my depth. The hash tree is a great visualization. I wouldn't have grasped…
You just call x509sha1.Value() and make a decision about old or new behavior based on that. Bisect can then toggle that result based on the hash of the call stack to narrow down the exact path that leads to the critical decision.
You can ignore the IncNonDefault call a few lines later. That's about providing monitoring for whether any non-default (old) behaviors are being executed in a program, so that people can hook it up to something like prometheus and see whether they would be affected by changing to "always default behavior".
this is a wonderful post! the algorithms for using binary search to efficiently reduce a set satisfying some predicate to a locally minimal satisfying subset* are new to me (though cox says zeller published a slightly buggy version in 01999! and meta's cinder a correct one in 02021), and seem brilliant; their applications are not limited to debugging. i wonder how it relates to hypothesis's test-case reduction algori…
For the hash table case, deciding the function per-table as you suggest is probably good enough. In a large program there are going to be tons of hash tables, and if bisect gets you to "it's this specific hash table allocated by this call stack that matters", that's a huge win.
The timer change is much like the hash table one, in that we toggle the "timer kind" at creation time, but it's only later operations that actually change behavior. Still, identifying the specific timer and call stack that created it turned out to be good enough in all cases.
this is a wonderful post! the algorithms for using binary search to efficiently reduce a set satisfying some predicate to a locally minimal satisfying subset* are new to me (though cox says zeller published a slightly buggy version in 01999! and meta's cinder a correct one in 02021), and seem brilliant; their applications are not limited to debugging. i wonder how it relates to hypothesis's test-case reduction algori…
One small correction: we were doing bisect over compiler optimizations a decade ago, but bisect over call trees only happened in the past year or so. For the hash table case, deciding the function per-table as you suggest is probably good enough. In a large program there are going to be tons of hash tables, and if bisect gets you to "it's this specific hash table allocated by this call stack that matters", that's a h…
does the list of callsite return counters being hashed get truncated at some point for stability? i'd think that hashing the call stack f→g→j→k→m→n→o→p to a hash unrelated to f→g→h→j→k→m→n→o→p would tend to interfere with the 'forced' set, but maybe this is only being used for things where the behavior is so closely equivalent that this problem doesn't arise
Are there any non-compiler use cases for this technique?
You can use this for any codebase of sufficient complexity where you want to identify which change is causing the effect you're observing.
Earlier quoted context omitted.
You can use this for any codebase of sufficient complexity where you want to identify which change is causing the effect you're observing.
Not really, it's only suitable where your code is processing some other large input that you don't understand, and when your changes are usually easily toggleable at runtime and can be applied to only part of the input.