[Python-Dev] Algoritmic Complexity Attack on Python

[Tim Peters]

[Gudio]
> Of course, such programs are already vulnerable to changes in the hash
> implementation between Python versions (which has happened before).

Last Thursday, Jim and I speculated about adding a persistent set type to
Zope, implemented via an IOBTree under the covers, mapping int hash codes to
lists of elements.  I'm sure someone else has already done something "like
that"; I know I have in the past, but only to run monstrously large
hash-function evaluation tests, where I needed to accumulate results across
multiple runs.

It's curious that persistence schemes are fragile in areas Python doesn't
really care about, like how objects of different types compare to each
other, how class instances that don't define __cmp__ compare to each other,
and in exactly which bit pattern hash(whatever) returns.  In Python 3 it may
be nice to define the results of such things more carefully in platform- and
release-independent ways -- or maybe to raise exceptions instead of making
results up, forcing users to confront the issues explicitly.  Lots of
tradeoffs here ...