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

41–48 of 48 posts

Re: Hash-based bisect debugging in compilers and runtimes

#41

Post by rsc »

kragen wrote: post #38
rsc wrote: post #36

Earlier quoted context omitted.

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…

thank you very much for the correction and the clarifications—and for the excellent post 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 th…

The assumption is that for a given test program, the call stack used at the specific moment where the failure begins is the same each run. If that's not true, there will be problems.

If there are two different call stacks that get to the function in question, but only one of them is where the failure begins, you absolutely want to distinguish those.

In practice we do cut off the stacks, using just 16 frames, but that's to avoid O(stack depth) overhead, not to coalesce different things.

Re: Hash-based bisect debugging in compilers and runtimes

#42

Post by rsc »

IshKebab wrote: post #39
saagarjha wrote: post #15

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.

I would frame it differently: stack hash bisect is only suitable where your code is linked into some other large program that you don't understand, and when your changes can be toggled on a per-invocation basis. Then you can use it to identify the exact stack through the larger program that leads to your code and works with the old behavior but breaks with the new behavior.

(saagarjha seems to be talking about 'git bisect', which is not really what the post is about.)

Re: Hash-based bisect debugging in compilers and runtimes

#43

Post by kragen »

rsc wrote: post #41
kragen wrote: post #38

Earlier quoted context omitted.

thank you very much for the correction and the clarifications—and for the excellent post 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 th…

The assumption is that for a given test program, the call stack used at the specific moment where the failure begins is the same each run. If that's not true, there will be problems. If there are two different call stacks that get to the function in question, but only one of them is where the failure begins, you absolutely want to distinguish those. In practice we do cut off the stacks, using just 16 frames, but that…

i see, thanks!

Re: Hash-based bisect debugging in compilers and runtimes

#44

Post by dwattttt »

eru wrote: post #22
dwattttt wrote: post #20

Earlier quoted context omitted.

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

That just explains Bayesian inference in general, which is useful, but not what I'm after. I was specifically interested in the application to binary search / bisection in the presence of flaky tests.

You apply the same process, but your hypotheses are "bug is before/after this bisection point". Your "probability of evidence given hypothesis before/after" are where you incorporate your guess about the tests flakiness. Still works even if you don't have "true" numbers for the tests flakiness, just won't converge as quickly

Re: Hash-based bisect debugging in compilers and runtimes

#45

Post by saagarjha »

saagarjha wrote: post #14

I'm running one of these now, interestingly enough. Apparently something's broken in OpenJDK if you build with the new Xcode. So I'm bisecting on all the files (choosing either the old or new compiler) trying to see which one is breaking things.

For those following along, I ended up doing four levels of bisects to find the actual problem. First the bisect I described above to identify the problematic file–stackMapTable.cpp. Then another on the functions inside of the file with optimizations and without to find the function that was broken: StackMapReader::next(StackMapFrame, bool, unsigned short, unsigned short, JavaThread). With that I manually inspected the code generated, found that it was wrong, and then did a bisect on optimization passes to see which one broke it (ConstraintEliminationPass). Finally one last bisect to see the history of where this came from (seems to be fixed in a change Xcode hasn't pulled yet).

Re: Hash-based bisect debugging in compilers and runtimes

#46

Post by IshKebab »

saagarjha wrote: post #40
IshKebab wrote: post #39

Earlier quoted context omitted.

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.

It works just fine for me what that wasn't the case.

Yeah I think you didn't get through the (admittedly very long) article. We aren't talking about git bisect.

Re: Hash-based bisect debugging in compilers and runtimes

#47

Post by saagarjha »

IshKebab wrote: post #46
saagarjha wrote: post #40

Earlier quoted context omitted.

It works just fine for me what that wasn't the case.

Yeah I think you didn't get through the (admittedly very long) article. We aren't talking about git bisect.

I assume you were talking about using hashes to encode some property of the program that you use for bisection. git bisect is still bisection but somewhat different IMO

Re: Hash-based bisect debugging in compilers and runtimes

#48

Post by kragen »

rsc wrote: post #41
kragen wrote: post #38

Earlier quoted context omitted.

thank you very much for the correction and the clarifications—and for the excellent post 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 th…

The assumption is that for a given test program, the call stack used at the specific moment where the failure begins is the same each run. If that's not true, there will be problems. If there are two different call stacks that get to the function in question, but only one of them is where the failure begins, you absolutely want to distinguish those. In practice we do cut off the stacks, using just 16 frames, but that…

i was reading zeller's book today and came to his example of delta-debugging minimization, which his ddmin algorithm solves in 48 tests, and it seemed like your 'easy' algorithm would be more efficient, so i hacked together a test program. your algorithm only takes 29 tests on this case. but because i couldn't remember your algorithm clearly, i first accidentally implemented a different variant that also works, but only takes 21 tests. it's not more efficient in the general case. still, it seems interesting, because it is arguably simpler than your 'easy' version (at least if we sweep the call to first_satisfying_bisect under the standard library) but still preserves logarithmic performance when the satisfying set it finds is of bounded size:

    def bisect_dumb(p, s):
        end, need = len(s), []

        while True:
            need.sort()
            needed = [s[j] for j in need]
            last = first_satisfying_bisect(lambda i: p(s[:i] + needed), 0, end)
            if last == 0:
                return need

            end = last - 1
            need.append(end)
the full program, with comments, is at http://canonical.org/~kragen/sw/dev3/bisectreduce.py. the corresponding version of bisect_easy would be

    def bisect_easy(p, s, targets=None, need=[]):
        if targets is None:
            targets = list(range(len(s)))
        if not targets or p([s[i] for i in sorted(need)]):
            return []
        if len(targets) == 1:
            return [targets[0]]

        m = len(targets)//2
        left, right = targets[:m], targets[m:]

        left_reduced = bisect_easy(p, s, left, right + need)
        right_reduced = bisect_easy(p, s, right, left_reduced + need)

        return left_reduced + right_reduced
bisect_easy is much faster if the minimal set it finds, of some size m, is a long substring a long way from the beginning of the input; i think it takes time proportional to log m + log n in that case, while bisect_dumb takes m log n

however, in cases where hashing scatters the size-m minimal set all over the search space, instead of compacting it into a little lump, i think it also ends up with m log n performance

i may get to implementing the easy/hard algorithm and zeller's ddmin. also, i have the intuition that, as with quicksort, trisection will have consistently but not overwhelmingly better performance than bisection for this purpose (though not in bisect_dumb)

Post reply on HN