[pypy-dev] x is y <=> id(x)==id(y)

Armin Rigo arigo at tunes.org
Mon May 6 09:38:24 CEST 2013


Hi Ilya,

On Sun, May 5, 2013 at 10:11 PM, Ilya Osadchiy <osadchiy.ilya at gmail.com> wrote:
> If the "id(x)==id(y)" requirement is removed, does it mean that "x is y" for
> immutable types is simply "x==y"?
> So if we have ``a = (); for i in range(100): a = (a, a); b = (a, a)`` then
> "a is b" will be computationally expensive?

It's not exactly ``x==y``: for tuples it means recursively checking
that items are ``is``-identical.  It's possible to avoid the
computational explosion, like CPython did for equality a long time ago
(up to maybe 2.3?) before it was removed.  You basically want to check
if the a and b objects are "in a bisimulation" or not, which can be
done without visiting the same object more than once, for any
connexion graph.

The reason I think it's a good idea (or at least not a bad idea) to
reintroduce the complexity of bisimulation where CPython removed it,
is that the purpose is slightly different and not visible to the user
at all.  If I remember correctly it was removed because it had
hard-to-explain effects on when and how many times the user's
``__eq__()`` methods were called; but there is no user-overridable
code involved here, merely an "implementation detail".  It could
equivalently be solved by aggressively caching all tuple creation.


A bientôt,

Armin.


More information about the pypy-dev mailing list