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

From: H. Peter Anvin <hpa@zytor.com>
Date: Jun 8, 2009, 15:51 UTC
Message-ID: <4A2D337C.70203@zytor.com>
In-Reply-To: <7vws7n6vcf.fsf@alter.siamese.dyndns.org>

Junio C Hamano wrote:

Show 22 quoted lines

> "H. Peter Anvin" <hpa@zytor.com> 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.