Junio C Hamano wrote: > "H. Peter Anvin" <hpa@xxxxxxxxx> 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. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html