Python sets and dictionaries can have quadratic-time performance | Hacker News Reader

Python sets and dictionaries can have quadratic-time performance

lemire.me

114 pointsibobev66 comments

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.

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, 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?

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?

> 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.

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.

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

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.

https://www.youtube.com/watch?v=npw4s1QTmPg

Very cool presentation. I loved how he says that they improved dict so much that they basically rediscovered database tables with indices.

Dave Beazley has a great talk about using Python built ins.

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

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.

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.

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).

Amortized is a bit different, though? It largely implies that there is a heavy cost periodically. Average just implies that it varies. Which, fair that "massive cost periodically" is compatible with that. Just seems to have a very different context, to me.

With hashtables, it was more that it was not guaranteed to be the minimal cost. Just, depending on statistics of the data that you feed to it, it shouldn't be the worst case.

> but unless you're defending against some sort of denial of service attack, in practice it rarely matters.

That "rarely" contains most sites/webservices. Before programming languages started defending against it by applying randomization (and sometimes replacing degraded maps/buckets with treemaps) it was a real threat. I remember people were able to trigger DoS either by specially crafted query string params or HTTP headers. After all both are shoved into some kind of map by frameworks, before request is even passed to application code.

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.

> 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

I think the point is that once it becomes a crypto key, stock price, weather observation, whatever, the datum ceases to be random and becomes arbitrary.

That is a nonsensical definition of random. If I roll a dice it's random, but if I write down the result it's not?

Arbitrary is also quite different from random. Bad passwords are arbitrary, good passwords are random.

If you ask a human to give an arbitrary number between 1 and 10, the answer will be 7 way more often than a random number between 1 and 10.

Note: weather observations being truly random data has been proved just recently (Navier-Stokes equations)

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.

> The costs just get bigger.

By a constant factor no less (until we get into theoretical physics)

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.

Moat of the time if you have at least several hundred elements. Benchmark it and see.

Reminds me of the article about random memory access being O(√N): https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

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.

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.

Which statement in this article applies only to Python?

The part where he chooses his inputs to hit worst case behavior in Python's hash function.

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).

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

https://news.ycombinator.com/item?id=49650737

CPython has the unfortunate property that ints aren’t covered by hash randomization, and `hash(x) == x % ((1 << 61) - 1)` always.

Ouch, that's a big footgun. Why was the lack of randomization considered a vulnerability, but not this?

I haven’t looked into the history, but my understanding from the comments is that it exists to preserve `x == y -> hash(x) == hash(y)` for `x` and `y` with different numeric types (int, float, decimal) – which seems like it should be solvable, but isn’t a constraint I’d want to be working under, so I sympathize.

> 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.

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.

Yeah but there's a formal term for average time complexity, Theta

Θ does not usually mean average, but simultaneously upper and lower asymptotic bounds.

you might want to read that chapter of CLRS again

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 )

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.

It is not “worst-case” (as the post demonstrates, you can get worse results by using specifically crafted data that exploits hash collisions). There are algorithms that can get you O(logN) instead of O(N) even on such data.

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.

Java's HashMap also has O(log(N)) complexity on hash collision, and that is before memory/cache details.

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)).

Expected

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.

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.

> Java's HashMap also has O(log(N)) complexity on hash collision

Only for keys that implement Comparable.

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.

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.

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"

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.

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.

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.

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.

> Stanford

Mmmmm. Yep. There's yer trouble.

It feels like I keep ending up leaving a comment on the unpopular version of a submission that ends up being reposted and getting traction later.

https://news.ycombinator.com/item?id=49553744

Once a hash table has outgrown all caches, it should have linear performance. It's just that caches accelerate it at sufficiently small sizes.

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.

  +--------------------------------------+------------+
  | Operation                            | Complexity |
  +--------------------------------------+------------+
  | x in s                               | O(1)       |
  | Copy (s.copy()) [6] [7]              | O(n)       |
  | Add (s.add(x)) [1]                   | O(1)       |
  | Discard (s.discard(x), s.remove(x))  | O(1)       |
  | ...                                  | ...        |
  +--------------------------------------+------------+

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.

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?

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)]`

`values = [i * M % 1_000_000_000_000_000 for i in range(1, n + 1)]`

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.

The map is not the territory.

Lemire back again with CS101 insights.

Next, he will teach us doubles have finite precision.

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.

Measurement is for micro-optimizations, and it's definitely important. But you should also know the complexity.

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.

Reply on news.ycombinator.com