"H. Peter Anvin" [off-list ref] 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.
Junio C Hamano wrote:
"H. Peter Anvin" [off-list ref] writes:
quoted
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.