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

From: "H. Peter Anvin" <[email-masked]>
Date: Mon, 08 Jun 2009 08:51:24 -0700

Junio C Hamano wrote:
> "H. Peter Anvin" <[email-masked]> writes:
> 
>> It's not entirely clear to me that this is any better than simply
>> randomly picking a commit from the list of plausible commits -- in other
>> words, eliminate the commits we can totally rule out, and then just pick
>> a random commit among the list of plausible commits.  This is not
>> *quite* as crazy as it sounds; it has the advantage of being an
>> extremely simple algorithm which shouldn't have any pathological behaviours.
> 
> That is essentially what Christian's patch does.  It does not try to go
> away from untestable commits in topological space.  Instead, when we find
> that the commit with the best "goodness" value is known to be untestable,
> we step away from that commit by some alternating distance _in the
> goodness value space_ (which does not have much to do with how commit
> ancestry topology is laid out).  Viewed in the topology space, it is quite
> similar to picking a different commit randomly, except for a very special
> case where the remaining history is completely linear, in which case the
> goodness value space and ancestry topology have a direct correlation.
> 
> That special case, and the deterministic hence repeatable nature of the
> algorithm, are the two main advantages over picking a completely random
> commit among the list of plausible commits.

Well, the cyclic "stepping distance" is pretty much a really lame PRNG
in this case.  In the linear case I think the distances are rather
arbitrary (and suboptimal), and I'm not sure it wouldn't simply be
better to actually use a PRNG (which can be unseeded and therefore
repeateable, or perhaps even better seeded with some combination of the
hash values involved.)

The advantage of that -- and I have to admit I don't know if it will
ever matter in practice -- is that using an actual PRNG:

a) is less likely to get into pathological capture behaviors.
b) doesn't make people think later that there is something magic to the
   arbitrary chosen numbers.

	-hpa

-- 
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.