Re: [PATCH v3 0/3] automatically skip away from broken commits

["H. Peter Anvin" <hpa@zytor.com>]

Jakub Narebski wrote:
> 
> Let us also assume that we have some model of probability that a commit
> is untestable. In the example below numbers are ad hoc, and unrealistic.
> 

What I mostly meant was that there simply is no such model that will be
ideal (since we simply don't have that information, almost by
definition), so therefore the overall algorithm can't be ideal, either.

However, Christian and you do make a very good point that instead of a
linear-probability random selection, it probably makes sense to bias the
randomness in favor of the commits that are more likely to provide
higher information gain.  This is effectively what Christian's patch
does in a somewhat clumsy way.

One of the nice things about combining a random algorithm with bias is
that the bias doesn't have to be perfect, it just have to be good
enough.  For example, we can take dramatic shortcuts like not taking
topology into accounts.

A logical bias function would indeed be an estimate of the information
gain.  One way we can calculate the effective information gain is by
take the list in "goodness order" that we already have, and treat it as
if it had originally been a linear history -- this will usually not be
the case, but we're probabilistically getting away with murder here.

The sorting in "goodness order" of a linear history means sorting
middlemost first, so the modified information density function with x
being the position in the list (x = 0 for best, x = 1 for worst) looks like:

- 1/(2 ln 2) * [ (1-x) ln (1-x) + (1+x) ln (1+x) - 2 ln 2 ]

I'd have to brush up some more of my calculus in order to remember how
to come up with a transformation function which would take a random
number and give us this exact probability distribution, but again, I
don't think it's hugely important; I suspect any function which gives us
a probability distribution that's even in the right neighborhood would
give us excellent results.

	-hpa