Re: Article about "git bisect run" on LWN

[Ingo Molnar <mingo@elte.hu>]

* david@lang.hm <david@lang.hm> wrote:

> On Thu, 5 Feb 2009, Ingo Molnar wrote:
>
>> * Christian Couder <chriscool@tuxfamily.org> wrote:
>>
>>> Hi,
>>>
>>> For information, an article from me, 'Fully automated bisecting with "git
>>> bisect run"' has been published in today's edition of LWN on the
>>> development page:
>>>
>>> http://lwn.net/Articles/317154/
>>
>> Nice article!
>>
>> In terms of possible future enhancements of git bisect, here's a couple of
>> random ideas that would help my auto-bisection efforts:
>>
>> - Feature: support "Bisection Redundancy"
>>
>>   This feature helps developers realize if a bug is sporadic. This happens
>>   quite often in the kernel space: a bug looks deterministic, but down the
>>   line it becomes sporadic. Sometimes a boot crash only occurs with a 75%
>>   probability - and if one is unlucky it can cause a _lot_ of wasted
>>   bisection time. The wrong commit gets blamed and the wrong set of
>>   developers start scratching their heads. It's a reoccuring theme on lkml.
>>
>>   What git could do here is to allow testers to inject a bit of extra
>>   "redundancy" automatically, and use the redundant test-points to detect
>>   conflicts in good/bad constraints.
>>
>>   It would work like this:
>>
>>      git bisect start --redundancy=33%
>>
>>   It would mean that for every third bisection points, Git would
>>   _not_ chose the ideal (estimated) 'middle point' from the set of "unknown
>>   quality" changes that are still outstanding - but would intentionally
>>   "weer outside" and select one commit from the _known_ set of commits.
>>
>>   If such a redundant re-test of the known-good or known-bad set yields a
>>   nonsensical result then Git aborts the bisection with a "logic
>>   inconsistency detected" kind of message - and people could at this point
>>   realize the non-determinism of the test.
>>
>>   ( Git can do this when a "redundant" test point is marked as 'bad' -
>>     despite an earlier bisection already categorizing that test point as
>>     'good' - or if it's the other way around. Git will only continue with
>>     the bisection if the test point has the expected quality. )
>>
>>   This essentially means an automated re-test - but it's much better than
>>   just a repeated bisection - i've often met non-deterministic bugs that
>>   yield the _exact same_ nonsensical commit even on repeat bisections. That
>>   happens when a timing bug depends on the exact kernel layout, or a
>>   miscompilation or linker bug depends on the exact kernel layout, etc.
>>
>>   It's also faster than a re-done bisection: 33% more testpoints is better
>>   than twice as many test-points. Also, auto-bisection can deal with
>>   redundancy just fine - it does not really matter whether i have to wait
>>   20 or 30 minutes for a test result since there's no manual intervention
>>   needed - but it _very_ much matters whether i can trust the validity of
>>   the bisection result.
>
> when you gave this the title of redundnancy and described the problem I  
> assumed that you would then propose running the test multiple times (so  
> "git bisect run X --redundancy 5" would run each test 5 times, it would  
> pass IFF it passed the test all 5 times. that would seem to be a better  
> match for the name, as well as being a better test

Yeah, but using 100%, 200%, 300%, etc. redundancy is a bit wasteful and not 
granular enough for my purposes.

Here's the math:

A typical kernel bisection takes 15 test steps. 30% of redundancy means that 
it takes only 30% longer, but for that we get +5 tests. Five extra test 
points are usually enough to establish whether a test method shows sporadic 
tendencies or not, with an ~90% confidence factor.

Repeating the test 5 times would bring a 15-steps kernel bisection from 30 
minutes [it's about 60 seconds to build a kernel, 60 seconds to boot it] to 
about 2.5 hours - that's very long. The confidence factor only goes from 
~90% to 99% - that extra 9% is not worth the cost.

The idea would be to insert 30% redunancy into my bisections automatically - 
so that i could trust _all_ bisections more - not just the ones i suspect to 
be non-deterministic. Hence the suggestion to enable lower levels of 
redundancy like 30%. (but even 10% or 20% might be enough to weed out the 
most obvious cases)

	Ingo