PERFORMANCE Signal 310 3 feeds carried it
Python sets and dictionaries can have quadratic-time performance
↗
Daniel Lemire demonstrates that Python sets and dictionaries can exhibit quadratic-time performance through engineered hash collisions, and even without collisions, lookups slow down significantly as memory footprint exceeds CPU cache limits.
Relying on the assumption that Python hash tables are strictly O(1) can lead to severe performance degradation in applications processing large or adversarial inputs. For read-heavy workloads with known keys, alternative data structures like fastconstmap can avoid cache misses and maintain significantly lower lookup times.
Written by elseif from the cluster below · every claim links back to a sourceThe three things worth knowing
Python sets and dictionaries can be forced into quadratic-time performance by crafting inputs that trigger hash collisions.
Even without collisions, dictionary lookups slow down by a factor of nine as the data structure grows and exceeds CPU cache limits.
The fastconstmap library provides faster lookups for immutable maps by reducing memory footprint to 9 bytes per key, keeping data in the cache.
THE CLUSTER