[Python-ideas] set.add() return value

Raymond Hettinger python at rcn.com
Tue Feb 17 10:07:15 CET 2009

[Greg Ewing]
> If I'd had an atomic test-and-add operation for sets,
> I could imagine that part running about twice as fast
> as it did.

Imagining and timing are two different things.

See Object/dictnotes.txt for the results of a month-long
effort to study ways to improve hash table performance.

One result was that two successive accesses for the
same key in a large table did *not* double the time.
Due to cache effects, the second access was nearly free.

Also, I think this performance discussion is over focusing
on the set lookup operation as if it were the dominant part
of typical programs.  Remember, that every time there is
dotted access, there is a hash table lookup.  Just writing
s.add(x) results in a lookup for "add" as well as the
the lookup/insertion of x.

The performance argument is a red-herring.


P.S.  The lookup time does nearly double if there is an
expensive hash function.  But then, it would make sense
to cache the results of that hash just like we do with strings.

More information about the Python-ideas mailing list