Rendered at 06:12:56 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
amiga386 8 hours ago [-]
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.
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 5 hours 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 << 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 58 minutes 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?
juancn 13 hours ago [-]
That's usually true of all common hash table implementations (when objects don't have a defined order, if they have you can get O(1) average and O(log N) worst case), regardless of language.
The O(1) is the expected average case, which usually holds.
Yeah, O(N^2) is theoretically possible, but unless you're defending against some sort of denial of service attack, in practice it rarely matters.
Still, if you can guess a sensible initial size for a hash table you can avoid a lot of the overhead of rehashing.
taeric 10 hours ago [-]
I used to think of it more as O(1) being the expected average of the cases. My guess is I'm probably thinking of it more as an amortized cost, in that framing? (That is, not that it is the average case. Is the average of all cases.)
To your point on the worst case being something you may worry about in denial of service, I think it is often the case that people should set bounds on what size N they will deal with in a program. And then decide from there on whether you are worried about some of the more esoteric growth patterns.
afdbcreid 9 hours ago [-]
It is both amortized and average, because the map may need to grow. But the complexity without growing is average, not amortized (it's possible to build hash functions for which the probability will mean O(1) for all accesses, and hash functions which will be O(N) for all accesses).
northisup 12 hours ago [-]
Raymond Hettinger has a great talk about how much python's dict has improved over the years. So this is super interesting and will probably just make the builtin dict better eventually.
The lesson of the talk is that if you are idiomatic then you will benefit as the language improves.
But could we create a hash table that would be truly constant-time? No. As the size of your data structure grows, it requires progressively slower memory.
At a large enough size to be interesting, everything is dominated by IO and because IO is slow, at any interesting size performance is a matter of tailoring the implementation to the details of the data {0}.
Engineering is hard work, not naive math.
[0] Data might be arbitrary but it is never random. Not being random is what makes it data.
streetfighter64 10 hours ago [-]
> Data might be arbitrary but it is never random. Not being random is what makes it data.
Most algorithm analyses don't incorporate memory hierarchies. I'm not sure what the point of this post was.
If you are really concerned about it, compute the empirical roofline for your machine.
Also, if the point is to point out memory hierarchies, it's not 'quadratic performance.' The algorithm doesn't behave differently once it spills over. The costs just get bigger.
afdbcreid 9 hours ago [-]
Because complexity models that involve memory hierarchy are an active research area and are super complex. Also, "plain" complexity is still useful: despite the constant factor, at large N (and this is sometimes a real possibility) the complexity will still win. For example, despite binary search being less cache-friendly (it can be made more with some tricks but not the same), it still defeats linear search most of the time.
mitxela 56 minutes ago [-]
Moat of the time if you have at least several hundred elements. Benchmark it and see.
koala_man 10 hours ago [-]
> The costs just get bigger.
By a constant factor no less (until we get into theoretical physics)
That is why I like to use __slots__ when defining a class. Unlike dicts, using __slots__ is a tuple so using it to store class attributes is much faster.
TristanDaCunha 13 hours ago [-]
Which statement in this article applies only to Python?
robrenaud 11 hours ago [-]
The part where he chooses his inputs to hit worst case behavior in Python's hash function.
progval 9 hours ago [-]
He doesn't. Inputs are:
M = (1 << 61) - 1
values = [i * M for i in range(1, n + 1)]
which are effectively random from the hash function's point of view, especially with a randomized seed (the default on current versions).
minitech 8 hours ago [-]
CPython has the unfortunate property that ints aren’t covered by hash randomization, and `hash(x) == x % ((1 << 61) - 1)` always.
progval 2 hours ago [-]
Ouch, that's a big footgun. Why was the lack of randomization considered a vulnerability, but not this?
amiga386 8 hours ago [-]
His inputs are large numbers that don't fit in a standard integer. Bigints. The set inclusion test not only has a hash lookup but an equality test, which will be a bigint comparision rather than integer comparison, and bitint comparison is itself O(n) based on the size of the bignum. And the code that tests each bignum is in the set also _sums_ those bignums, which itself is an O(n) operation based on the size of the bignums being summed.
So he's not testing dict/set performance, he's testing bignum performance, because of the inputs he deliberately chose
> To put it differently, saying that a hash table is O(1) or constant time is a model
Nobody really says that, nor is it a model. It is the expected time complexity.
t-writescode 12 hours ago [-]
People … say that all the time. *I* say that all the time. It’s true enough to be accurate in 99.9% of the cases; and we put barriers in place when implementing code (like configuring the hashing algorithm) to keep it that way.
robertlagrant 13 hours ago [-]
I think people do say a hash table is O(1). It's the average time complexity (for some value of average) though, not the worst case.
lou1306 12 hours ago [-]
O(1) insertion is the amortized worst-case time complexity, actually. (Amortized in the sense that the O(n) cost of copying is paid only during the n-th insertion). Average complexity is a slightly different thing.
jpitz 12 hours ago [-]
Yeah but there's a formal term for average time complexity, Theta
emil-lp 12 hours ago [-]
Θ does not usually mean average, but simultaneously upper and lower asymptotic bounds.
xdavidliu 12 hours ago [-]
you might want to read that chapter of CLRS again
jpitz 10 hours ago [-]
You're right.
It isn't the average bound, it is the upper and lower bound stated together ( as long as thats the same function )
done_lurking 13 hours ago [-]
Time complexity is something that applies to algorithms, and is determined analytically. I don't think it's useful to equivocate the definition with performance of implementations of algorithms determined through real world data. Both of these things are important, but they are not the same. The fact that they differ is not very surprising and does not necessarily mean that a misunderstanding has occurred.
Drupon 9 hours ago [-]
Real big brain moment in the comments
>Can we say that since every real-life data structure size is bounded by some constant, it is O(1)? If not, why?
>>You may, yes.
Very powerful thinking coming from someone who is "a software performance expert. He ranks among the top 2% of scientists globally (Stanford/Elsevier 2025) and is one of GitHub's top 1000 most followed developers"
anewhnaccount2 9 hours ago [-]
It's true you can. Just as you can say that you can enumerate all memory states in a real computer so it can be modelled as a finite state machine. These asymptotic models aren't real (our world as we experience it is finite and bounded) and exist as models from which to gain insights which we can transfer back. I love this argument BTW a classic that usually comes up in these discussions.
Drupon 9 hours ago [-]
Asymptotic models are not a statement of how long it will take; they are classes of functions modeling the relationship between some performance outcome (run time most often, but sometimes memory or other things) and data coming in. These mappings from input to performance characteristics are not conditioned on physical limitations but are rather abstract tools for measuring that relationship.
Archer6621 9 hours ago [-]
If you have an instance (which is what I assume is implied by "real-life data structure") bounded by a particular size, then you could say that the runtime complexity is constant with respect to that bound. Whether that is a useful statement to make is another discussion entirely. On its own probably not. It can potentially be useful for analyzing the runtime complexity of operations in more complex algorithms that use this data structure up to a certain fixed size, e.g. as a buffer/cache of some sort.
Drupon 9 hours ago [-]
The "runtime complexity" we're talking about is big-O. In computer science, which includes this discussion of it, that typically refers to a class of functions. Saying "this algorithm is O(...)" is the same as saying "this algorithm's performance can be modeled by a function belonging to the class of functions O(...), meaning that the size of some characteristic such as runtime, relative to its domain, is bounded asymptotically by another function g(x) = ..."
There's another level of imprecision here in common usage, which is that big-O is strictly an upper bound, meaning that Merge Sort is O(N!). What they really mean is big-Theta, a "tight" bound, in which Merge Sort would be θ(n log n).
But for simplicity's sake, let's use big-O to mean "tightly bound" like people do in casual discussion, and further let's say we're talking about runtime as the size of the function based on its domain:
There is no such thing as big-O performance bounded by a "real-life data structure". The entire point of big-O is that it is asymptotic analysis. You could define a number H, where H is the time to the heat death of the universe, and Python's sets and dictionaries would never be O(H). Because you could for your set/dict runtimes of f(n) still find a constant C and k such that f(n) > C*H for n > k. One example would be setting k to H*C + 1, and that works for either f(n) ∈ O(1) or f(n) ∈ O(n^2).
You can analyze algorithms with respect to real physical limitations, but at that point you are not talking about their "big-O" performance. So the author, despite being "top 2% of scientists" in his field, which is "software performance", seems to still be lagging behind your average freshman compsci student who crammed for their complexity analysis exam.
lenerdenator 9 hours ago [-]
> Stanford
Mmmmm. Yep. There's yer trouble.
3 days ago [-]
javcasas 2 days ago [-]
Java's HashMap also has O(log(N)) complexity on hash collision, and that is before memory/cache details.
In fact, some studying on data structures probably leads to the conclusion that it is impossible to guarantee that an unbounded set/map to have access performance under O(log(N)).
pfdietz 11 hours ago [-]
One get can O(1) expected time on any set of keys if one uses "universal hashing": choosing the hash function at random from a universal set of hash functions. The expectation is now over this random choice, not over some random distribution of key inputs. So even if an adversary gets to choose the keys the expected behavior is good.
For hashing with chaining, the hash function just has to make the hash values of keys pairwise independent to achieve O(1) expected time per operation; higher order independence is not needed.
aw1621107 13 hours ago [-]
> Java's HashMap also has O(log(N)) complexity on hash collision
Only for keys that implement Comparable.
emil-lp 14 hours ago [-]
Expected
marcosdumay 13 hours ago [-]
Nowadays I expected an opaque dictionary to be amortized O(1).
Granted, one can technically call that O(log(n)), but that's not a helpful categorization.
emil-lp 12 hours ago [-]
You cannot guarantee that from a hash map since an adversary who knows the hash function (unless it's cryptographic) could game the data structure to their advantage.
stkdump 13 hours ago [-]
Once a hash table has outgrown all caches, it should have linear performance. It's just that caches accelerate it at sufficiently small sizes.
jldugger 12 hours ago [-]
Uh, what is going on with this benchmark?
Why is M so big? Why does it cross the maxint boundary? Why is constructing the list comprehension part of the benchmark? Why are we summing the set? Why are we only measuring 5 values for n?
brody_hamer 8 hours ago [-]
Yea if I cast the large calculated integers to strings, performance is O(1)
`values = [str(i * M) for i in range(1, n + 1)]`
or
`values = [i * M % 1_000_000_000_000_000 for i in range(1, n + 1)]`
jldugger 7 hours ago [-]
Part of the secret explained elsewhere on this HN post is that the OP is selecting values that all collide. Most hash tables handle collisions with linked lists that would be linear insert. It's O(1) average case but O(n) if you pull an "oops all collisions on the same bucket" stunt.
oefrha 13 hours ago [-]
This "quadratic-time performance" is incredibly disingenuous. First, it's doing n operations that are each O(n), so it's more like "can have linear time performance, but done n times so I can give you a scary title".
Edit: A charitable take is constructing a set/dict from a list is indeed a common operation so it's worthwhile to think about its complexity, but it's not really one of the standard operations when discussing the performance of a hashset/hashmap, so really shouldn't be this handwavy.
And instead of attacking some straw man "It is indeed widely believed that ..." claim (widely believed by who?), why not attack what's literally on docs.python.org? https://docs.python.org/3/library/time-complexity.html:
> dict
> The times listed for dict objects are average-case times, as they assume the hash function for the objects is sufficiently robust to make collisions uncommon. They also assume the keys are well-distributed among the set of possible keys. In the worst case, when every key hashes to the same value, each of the O(1) operations below instead takes O(n) time. They also assume that hashing and comparing a key is O(1). For more detail on the implementation, see How are dictionaries implemented in CPython?.
> ...
> set, frozenset
> See dict as the set and frozenset implementations are similar, and the same caveats apply. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element degrade accordingly.
You explicitly construct a list of ints that are all multiples of sys.hash_info.modulus and hence all hash to 0, no shit you get that well documented O(n) behavior.
The discussion of CPU cache is good though, so why hide that behind this clickbait.
0xa2 3 days ago [-]
The map is not the territory.
coolThingsFirst 11 hours ago [-]
Lemire back again with CS101 insights.
Next, he will teach us doubles have finite precision.
jaydeepg 11 hours ago [-]
[flagged]
hillbillyDev676 2 hours ago [-]
[flagged]
2 hours ago [-]
vyftec_wpsec 11 hours ago [-]
[flagged]
Insanity 10 hours ago [-]
Generally for performance, the rule is you _measure_ it, you don't rely on big-O. So if you're really concerned, please just use a profiler.
Also hashmaps (python Dicts) have amortized O(1) and not O(1) big-O.
afdbcreid 9 hours ago [-]
Measurement is for micro-optimizations, and it's definitely important. But you should also know the complexity.
ot 11 hours ago [-]
O(1) doesn't mean constant, it means bounded by a constant. An algorithm can be faster with small n and converge to a horizontal asymptote as n goes to infinity, and it would still be O(1).
In a real machine there is no infinity, but hundreds of GBs of memory are "infinity enough" compared to the cache size [1]. So asymptotic analysis is still a decent model.
I'm surprised that even a CS professor confuses this.
[1] Ok if we want to be pedantic memory access is logarithmic due to the traversal of page tables, but you can use huge pages.
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.__...
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?
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?
The O(1) is the expected average case, which usually holds.
Yeah, O(N^2) is theoretically possible, but unless you're defending against some sort of denial of service attack, in practice it rarely matters.
Still, if you can guess a sensible initial size for a hash table you can avoid a lot of the overhead of rehashing.
To your point on the worst case being something you may worry about in denial of service, I think it is often the case that people should set bounds on what size N they will deal with in a program. And then decide from there on whether you are worried about some of the more esoteric growth patterns.
The lesson of the talk is that if you are idiomatic then you will benefit as the language improves.
https://www.youtube.com/watch?v=npw4s1QTmPg
Def worth a watch as he is funny but also super cool to see someone use a REPL this way:
https://www.youtube.com/watch?v=lyDLAutA88s
At a large enough size to be interesting, everything is dominated by IO and because IO is slow, at any interesting size performance is a matter of tailoring the implementation to the details of the data {0}.
Engineering is hard work, not naive math.
[0] Data might be arbitrary but it is never random. Not being random is what makes it data.
Counterexamples: crypto keys, stock price history, weather observations, radio telescope recordings
If you are really concerned about it, compute the empirical roofline for your machine.
Also, if the point is to point out memory hierarchies, it's not 'quadratic performance.' The algorithm doesn't behave differently once it spills over. The costs just get bigger.
By a constant factor no less (until we get into theoretical physics)
So he's not testing dict/set performance, he's testing bignum performance, because of the inputs he deliberately chose
https://news.ycombinator.com/item?id=49650737
Nobody really says that, nor is it a model. It is the expected time complexity.
It isn't the average bound, it is the upper and lower bound stated together ( as long as thats the same function )
>Can we say that since every real-life data structure size is bounded by some constant, it is O(1)? If not, why?
>>You may, yes.
Very powerful thinking coming from someone who is "a software performance expert. He ranks among the top 2% of scientists globally (Stanford/Elsevier 2025) and is one of GitHub's top 1000 most followed developers"
There's another level of imprecision here in common usage, which is that big-O is strictly an upper bound, meaning that Merge Sort is O(N!). What they really mean is big-Theta, a "tight" bound, in which Merge Sort would be θ(n log n).
But for simplicity's sake, let's use big-O to mean "tightly bound" like people do in casual discussion, and further let's say we're talking about runtime as the size of the function based on its domain:
There is no such thing as big-O performance bounded by a "real-life data structure". The entire point of big-O is that it is asymptotic analysis. You could define a number H, where H is the time to the heat death of the universe, and Python's sets and dictionaries would never be O(H). Because you could for your set/dict runtimes of f(n) still find a constant C and k such that f(n) > C*H for n > k. One example would be setting k to H*C + 1, and that works for either f(n) ∈ O(1) or f(n) ∈ O(n^2).
You can analyze algorithms with respect to real physical limitations, but at that point you are not talking about their "big-O" performance. So the author, despite being "top 2% of scientists" in his field, which is "software performance", seems to still be lagging behind your average freshman compsci student who crammed for their complexity analysis exam.
Mmmmm. Yep. There's yer trouble.
https://docs.oracle.com/javase/8/docs/api/java/util/HashMap....
In fact, some studying on data structures probably leads to the conclusion that it is impossible to guarantee that an unbounded set/map to have access performance under O(log(N)).
https://en.wikipedia.org/wiki/Universal_hashing
For hashing with chaining, the hash function just has to make the hash values of keys pairwise independent to achieve O(1) expected time per operation; higher order independence is not needed.
Only for keys that implement Comparable.
Granted, one can technically call that O(log(n)), but that's not a helpful categorization.
Why is M so big? Why does it cross the maxint boundary? Why is constructing the list comprehension part of the benchmark? Why are we summing the set? Why are we only measuring 5 values for n?
`values = [str(i * M) for i in range(1, n + 1)]`
or
`values = [i * M % 1_000_000_000_000_000 for i in range(1, n + 1)]`
Edit: A charitable take is constructing a set/dict from a list is indeed a common operation so it's worthwhile to think about its complexity, but it's not really one of the standard operations when discussing the performance of a hashset/hashmap, so really shouldn't be this handwavy.
And instead of attacking some straw man "It is indeed widely believed that ..." claim (widely believed by who?), why not attack what's literally on docs.python.org? https://docs.python.org/3/library/time-complexity.html:
> dict
> The times listed for dict objects are average-case times, as they assume the hash function for the objects is sufficiently robust to make collisions uncommon. They also assume the keys are well-distributed among the set of possible keys. In the worst case, when every key hashes to the same value, each of the O(1) operations below instead takes O(n) time. They also assume that hashing and comparing a key is O(1). For more detail on the implementation, see How are dictionaries implemented in CPython?.
> ...
> set, frozenset
> See dict as the set and frozenset implementations are similar, and the same caveats apply. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element degrade accordingly.
You explicitly construct a list of ints that are all multiples of sys.hash_info.modulus and hence all hash to 0, no shit you get that well documented O(n) behavior.The discussion of CPU cache is good though, so why hide that behind this clickbait.
Next, he will teach us doubles have finite precision.
Also hashmaps (python Dicts) have amortized O(1) and not O(1) big-O.
In a real machine there is no infinity, but hundreds of GBs of memory are "infinity enough" compared to the cache size [1]. So asymptotic analysis is still a decent model.
I'm surprised that even a CS professor confuses this.
[1] Ok if we want to be pedantic memory access is logarithmic due to the traversal of page tables, but you can use huge pages.