Il 21/05/2012 19:21, Andrew Jenner ha scritto: > Hi Paolo, > > On 5/21/2012 10:12 AM, Paolo Bonzini wrote: >> That's pretty heavy-weight. Perhaps you can try the usual algorithm of >> looking at x->next and x->next->next? > > That would only detect cycles of length 1 and 2 though. While that would > cover all the testcases we currently know about, I wanted to eliminate > the entire pattern of hangs. Otherwise it's only a question of time > until someone hits a cycle of length >= 3.
Sorry, I meant x = x->next and y = y->next->next. That's the tortoise and hare algorithm you referred to, I think. If you extract the body of the loop into a new function find_comparison_args_1, the code would not be much more complicated. Paolo