Python Sets Can Go Quadratic on Keys Chosen to Collide

Computer science courses teach that inserting into a hash-based set or dictionary takes constant time, no matter how many elements are already inside. Daniel Lemire, a professor at the Université du Québec who writes frequently about CPython performance, published a benchmark on Sept. 3 showing that claim fails on Python 3.14 once the keys are chosen rather than random, and a second, unrelated slowdown that shows up even when they are not.

Why a Python set can go quadratic

Lemire built a set from integers generated as i * ((1 << 61) - 1) for values of i from 1 up to n. That constant, 2^61 minus 1, is a Mersenne prime that CPython's integer hash function also uses as its modulus on 64-bit builds, so every integer in the sequence hashes to the same value and lands in the same bucket. Inserting n of them, measured as the median of three runs, took 4.8 milliseconds at n equal to 1,000, 257 milliseconds at 8,000, and 1,072 milliseconds at 16,000. Doubling n roughly quadrupled the time at each step, which is quadratic, or O(n squared), performance rather than the constant time the textbook promises.

Why ordinary large dictionaries also get slower

A second, separate benchmark in the same post used a million ordinary, randomly generated sixteen-character strings as dictionary keys, with no chosen collisions. Lookup time rose from about 21.8 nanoseconds per key at 1,000 entries to 201.9 nanoseconds per key at 1,000,000 entries, a ninefold increase, not a quadratic one. Lemire attributed this to memory rather than algorithm: a million keys, plus the string and integer objects behind them, occupy roughly 116 bytes per key, so once the table outgrows the CPU's cache, most lookups have to reach into RAM, which is far slower than cache.

What CPython's own developers found when they looked at this

The cache-miss problem predates Lemire's post by years. In a January 2022 GitHub discussion opened by contributor lpereira in the faster-cpython/ideas repository, CPython core developer Inada Naoki benchmarked replacing the dict implementation with a cache-friendlier design modeled on Google's SwissTable and Rust's hashbrown library, the same family of designs Lemire's post points to as the fix other languages use. Naoki found the change yielded roughly a 1 percent improvement for dict and concluded the bigger win was available in Python's set implementation instead. Fellow core developer Brandt Bucher discussed a cache-line-friendly layout requiring 8-byte keys in the same thread, and Python creator Guido van Rossum weighed in directly; CPython's dict has not been rebuilt around a SwissTable-style layout in the three and a half years since.

What this changes for working code

Lemire's own conclusion is narrower than his headline: "Some models are useful but none of them is reality." The quadratic case needs an attacker, or a careless test author, who can choose the exact integers a set or dict receives, a condition that matters most for code building sets or dicts from untrusted numeric input, such as IDs parsed from a network request. The cache-driven slowdown in the second benchmark applies more broadly, to any dict or set that grows past a few hundred thousand entries regardless of what is inserted, and CPython's own contributors have known about it, and left it unresolved for dict specifically, since at least 2022.

The same gap between an algorithm's advertised complexity and its measured cost is what has pushed some projects to rewrite rather than patch: two developers separately ported the GNU Radio signal-processing toolkit to the browser via WebAssembly rather than accept a native dependency's limits, and a cluster of newer libraries chose to bolt durable execution onto Postgres instead of building a bespoke coordination layer on top of existing data structures.

Lemire's numbers also point at a narrower, practical rule. Python's own documentation on the PYTHONHASHSEED variable says the interpreter randomizes the hash of every str and bytes object with a value set once per process, specifically, it says, "to provide protection against a denial-of-service caused by carefully chosen inputs that exploit the worst case performance of a dict construction, O(n²) complexity." That is the exact failure mode Lemire measured. The documentation does not list integers among the randomized types, and Lemire's demonstration works because it targets that gap directly: multiples of a Mersenne prime collide the same way in every run of the interpreter, with no seed to guess. For string or bytes keys built from untrusted input, the randomized seed is the mitigation Python already ships; for integer keys, as Lemire's benchmark shows, it is not, and none of the sources reviewed for this piece say Python's core developers are planning to extend it.