4 ms·

I call shenanigans on this. import timeit def test(M,n): values = [i * M for i in range(1, n + 1)] s = set(values) sum(v in s f

I call shenanigans on this. 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 for n in [1000, 2000, 4000, 8000, 16000]: print(f"M=2^61-1, {n=:5d} ->", timeit.timeit(lambda: test(M,n), number=3)) for n in [1000, 2000, 4000, 8000, 16000]: print(f"M=1, {n=:5d} ->", timeit.timeit(lambda: test(1,n), number=3)) Magically, when you stop using BIGINTS as the set members and just use regular ints, there is no such quadratic explosion. M=2^61-1, n= 1000 -> 0.13144792200182565 M=2^61-1, n= 2000 -> 0.48016051898594014 M=2^61-1, n= 4000 -> 2.058760045998497 M=2^61-1, n= 8000 -> 7.843778470996767 M=2^61-1, n=16000 -> 40.01485426299041 M=1, n= 1000 -> 0.000748768012272194 M=1, n= 2000 -> 0.0015750699967611581 M=1, n= 4000 -> 0.003037029004190117 M=1, n= 8000 -> 0.006664915999863297 M=1, n=16000 -> 0.012693285010755062 The runtime is being spent hashing bigints, comparing candidate bigint(s) against reference bigints, and summing bigints. And there's also some set lookups.

nilslindemann 6d ago
Actually, 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)) (1 << 61) - 1 is a Mersenne prime number, which Python uses internally on 64-bit systems for the hash algorithm for big integers. When multiplying numbers with this prime number, hash collisions become common, and this slows down the performance. 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 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.__hash__ https://docs.python.org/3/reference/datamodel.html#object.__...
- brody_hamer 6d ago
  > (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?
mitxela 6d ago
So why is it quadratic? Hashing 1<<61-1 should be a constant factor slower than hashing 1. I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI?
- zahlman 6d ago
  > I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI? That was two different people. The first comment probably comes from finding the 1<<61-1 constant suspicious, running a micro-benchmark, and then not thinking about it too hard.
- amiga386 5d ago
  I wrote the first comment, thinking it's bignums, but no, it is hash collisions. It's quadratic because that's what hash collisions mean for a closed hash. The worst cast scenario is that every item has the same hash value, thus goes in the same bucket, so to insert 40,000 unique items, you have to check against 0, 1, 2, 3, ... 40,000 existing items in a linear list (800,000,000 equality tests) to avoid inserting duplicates. To then do an inclusion test for all those items, you have to scan the list 40,000 times, stopping at element 0, 1, 2, ... 40,000, so another 800,000,000 equality tests. It turns out that Python's hash value for integers is the integer itself, modulo (1<<62)-1, which is why he makes all his values multiples of that number, so they're all unique integers with the same hash value. Other than this very narrow case (or more likely creating unique objects whose __hash__ method deliberately/accidentally returns the same value), you'd find it hard to make this situation happen in normal code.
eviks 5d ago
Why would finding a different reason the model fails be "shenanigans" when the point of the blog is slowing that the model can fail?

nilslindemann 6d ago

Actually, 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)) (1 << 61) - 1 is a Mersenne prime number, which Python uses internally on 64-bit systems for the hash algorithm for big integers. When multiplying numbers with this prime number, hash collisions become common, and this slows down the performance. 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 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.__hash__ https://docs.python.org/3/reference/datamodel.html#object.__...

brody_hamer 6d ago
> (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?

mitxela 6d ago

So why is it quadratic? Hashing 1<<61-1 should be a constant factor slower than hashing 1. I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI?

zahlman 6d ago
> I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI? That was two different people. The first comment probably comes from finding the 1<<61-1 constant suspicious, running a micro-benchmark, and then not thinking about it too hard.
amiga386 5d ago
I wrote the first comment, thinking it's bignums, but no, it is hash collisions. It's quadratic because that's what hash collisions mean for a closed hash. The worst cast scenario is that every item has the same hash value, thus goes in the same bucket, so to insert 40,000 unique items, you have to check against 0, 1, 2, 3, ... 40,000 existing items in a linear list (800,000,000 equality tests) to avoid inserting duplicates. To then do an inclusion test for all those items, you have to scan the list 40,000 times, stopping at element 0, 1, 2, ... 40,000, so another 800,000,000 equality tests. It turns out that Python's hash value for integers is the integer itself, modulo (1<<62)-1, which is why he makes all his values multiples of that number, so they're all unique integers with the same hash value. Other than this very narrow case (or more likely creating unique objects whose __hash__ method deliberately/accidentally returns the same value), you'd find it hard to make this situation happen in normal code.

eviks 5d ago

Why would finding a different reason the model fails be "shenanigans" when the point of the blog is slowing that the model can fail?