Issue 693221: fix bug 625698, speed up some comparisons (original) (raw)

This patch, patchrecursion GREATLY speeds up comparisons of recursive objects, fixing bug 625698.

It works by throwing a new exception, a RecursionError, to break out of the current deeply nested comparison, and then redoing the comparison by the already established technique for recursive objects.

I believe the only costs to normal non-recursive comparisons is two additional C comparisons.

Backwards compatibility problems will occur only in code that attempts to handle ALL exceptions while doing comparisons. Of course, this is always a bad practice, so hopefully not much code does this. Also, most code probably doesn't attempt to handle exceptions within the actual comparison routines, instead catching them elsewhere, which will be fine.

Another patch is also attached, patchequal, to handle some of the common cases where this comes up even faster.

While it is true that python wants to have an == operator that does not define an equality relation, I believe that when == is not an equality relation python has few obligations to be nice to it. In particular, suppose we have an object NaN != NaN. I would say that (NaN,) == (NaN,) [NaN] == [NaN] {NaN:1} == {NaN:1} all intuitively still seem true. Isn't it obvious that if two lists contain the SAME objects, they are equal? That is, even though NaN does not equal itself, lists, tuples, and dicts have no obligation to respect the underlying == operator.
I don't see any documentation saying they will respect it (though maybe I'm just missing it). patchequal assumes, ONLY for purposes of list tuple dict comparisons and dict lookups, that if id(a) == id(b), then a == b. Note there is some precedence for this patch, d = {NaN:1} NaN in d => True cmp(NaN, NaN) is 0 (though I suspect this is a mistake).

This will cause backwards compatibility problems only for people using non-equality relation =='s, and probably not even for them, as they already probably use a trick to emulate this patch when they compare lists and such containing these weird objects.

Logged In: YES user_id=31435

Python 2.4 was changed so that recursive comparisons (all recursive comparisons) raise

RuntimeError: maximum recursion depth exceeded in cmp

so rejecting the patch (Python doesn't want to guess the intended meaning of a recursive compare, regardless of the speed at which it could make such a guess).

Thanks for playing, though! Just find something useful next time.