[issue23282] Slightly faster set lookup

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Good point Josh. Yes, it may slow down other cases, and there is a difference between sets and dicts.

1. If the key is not contained in the set, then if the first tested entry table[hash & mask] is empty, then the lookup is slowed down by one pointer comparison (2 comparisons instead of 1). If the entry is used then the lookup is not slow downed or even speed up (if need to test more than one additional entries).

2. If the same case is in the set, then if the first tested entry is the set then the lookup will use one comparison instead of 4. In other cases (the key is placed in other entry) the lookup will use at least one comparison less.

3. If the set contains key equal but not identical to tested key, then the lookup will use at least one comparison less.

Only first case can cause slowdown. If we test a lot of keys not existing in the set with small ratio between used and allocated entries numbers. May be the worst case is creating a copy of the set. For other operations I did not find significant difference.

$ ./python -m timeit -s "s = set(range(10**4))" -- "frozenset(s)"
Unpatched: 1000 loops, best of 3: 658 usec per loop
Patched: 1000 loops, best of 3: 668 usec per loop

But issue23290 prevents this regression.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue23282>
_______________________________________