alt Hacker NewsActually, as the Google AI just taught me [1], the bad performance results from hash _collisions_, not from using bigints (which the author also mentions):
import timeit
def test(M, n):
values = [i * M for i in range(1, n + 1)]
s = set(values)
sum(v in s for v in values)
M = (1 << 61) - 1 # This is a bigint and also a Mersenne prime number
N = (1 << 61) + 42 # This is a bigint, but not a Mersenne prime number
# This runs slow
for n in [1000, 2000, 4000, 8000, 16000]:
print(f"M=2^61-1, {n=:5d} ->", timeit.timeit(lambda: test(M,n), number=3))
# This runs with normal performance
for n in [1000, 2000, 4000, 8000, 16000]:
print(f"N=2^61+42, {n=:5d} ->", timeit.timeit(lambda: test(N,n), number=3))
This is not completely theoretical; hash-DoS attacks make use of that. For this reason, there is hash salting since Python 3.3 for strings, bytes, and datetime objects [2], but not for integers, because the most common attack surface is JSON, but JSON keys are strings, and hash salting would slow down the performance of math operations.
[1] https://share.google/aimode/cXQyw0SDPr5FnhBc5, available for seven days
[2] See the grey info box here: https://docs.python.org/3/reference/datamodel.html#object.__...
> (1 << 61) - 1 is a Mersenne prime number, which Python uses internally on 64-bit systems for the hash algorithm for big integers.
So this hinges on a contrived set of integer keys, which python's hashing algorithm is susceptible to?
It's not super clear from the article that the choice of key was specifically chosen to generate these hash collisions (though it is more evident on a re-read). The article leads one to believe that the likelihood of this collision is common:
> "I can ‘easily’ make my version of Python crumble"
> "To put it differently, saying that a hash table is O(1) or constant time is a model. It can be true, maybe even often, but it is not reality."
It feels very misleading to say that "Python sets and dictionaries can have quadratic-time performance", as though this may be a common occurrence in the wild. Perhaps if this behaviour had been accidentally discovered in the wild, that would make for an interesting anecdote? It feels like the lesson is more accurately put: "hash tables are susceptible to hash collisions".
I guess ultimately I come to a different conclusion than the original blog post. They say: "Some models are useful but none of them is reality. Be mindful of cognitive biases." It reads to me as having an air of "you can't trust anything." I think I would describe this conclusion more like "abstractions are leaky, and it is helpful to have a basic understanding of what's happening under the hood. Even for something as elemental as a dict."
And in that sense, if I were making this point with regards to computer science I might lean on a more common false assumption like "the network is reliable". (Or establish early-on in the article that we're identifying a similar false assumption about dicts.)
Anyway, I think I'm sensitive to articles picking on python.. but perhaps the title was clickbait. Is there another language with a clearly superior approach that python should emulate?