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

Jakub Narebski wrote:

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