fix bug 625698, speed up some comparisons

[mbrierst]

BPO	693221
Nosy	@tim-one
Files	patchrecursion patchequal

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2004-03-20.21:18:29.000>
created_at = <Date 2003-02-25.21:57:29.000>
labels = ['interpreter-core']
title = 'fix bug 625698, speed up some comparisons'
updated_at = <Date 2004-03-20.21:18:29.000>
user = 'https://bugs.python.org/mbrierst'

bugs.python.org fields:

activity = <Date 2004-03-20.21:18:29.000>
actor = 'tim.peters'
assignee = 'none'
closed = True
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2003-02-25.21:57:29.000>
creator = 'mbrierst'
dependencies = []
files = ['5046', '5047']
hgrepos = []
issue_num = 693221
keywords = ['patch']
message_count = 2.0
messages = ['42899', '42900']
nosy_count = 2.0
nosy_names = ['tim.peters', 'mbrierst']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue693221'
versions = ['Python 2.3']

[mbrierst]

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.

[tim-one]

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
<wink> next time.