Repository navigation
Description
Bug report
Bug description:
This came up long ago when I was working on hardening the tuple hash, but got dropped on the floor.
It recently came up again in the context of frozendict haahing, which just copied much of the frozenset hashing code:
The problem is that shuffle_bits() only propagates changes from low-order bits to higher. Any function using only left shifts and multiplies suffers from this.
But hash codes may differ only in high-order bits to begin with. Avalanche is horrid in the absence of a stronger bit shuffler, which also propagates higher-to-lower.
It so happens that hash codes of low-precision floats do suffer from this.
>>> len(set(hash(i/256) for i in range(256))
256So they're all different, but the variation is only in the topmsot bits:
>>> for i in range(10):
... print(hex(hash(i/256)))
...
0x0
0x20000000000000
0x40000000000000
0x60000000000000
0x80000000000000
0xa0000000000000
0xc0000000000000
0xe0000000000000
0x100000000000000
0x120000000000000
>>>So frozenset struggles with them. First block of output from the code at the end, which analyzes the hashes of frozensets of all ways of taking 3 elements from those 256 floats (of course it doesn't matter if the same values are spelled as Fraction and/or Decimal instead).
number of possible hash codes: 18_446_744_073_709_551_616
number of hash codes total: 2_763_520
number of unique hash codes: 2_048
number of collisions: 2_761_472
mean expected collisions: 0.00
and its sdev: 0.00
z: +6069500754.14
worst pileups:
2_020
2_015
2_005
2_005
2_002
2_001
1_999
1_993
1_988
1_980
The z score is crazy high, but "pileups" matter much more than that. That's the number of distinct inputs that map to the same hash code. It's the length of collision chains the drive catastrop;ic slowdowns, not really the number of collisions.
The second block of output shows what happens instead if we just xor together the hashes of 1-tuples containing the same values:
number of possible hash codes: 18_446_744_073_709_551_616
number of hash codes total: 2_763_520
number of unique hash codes: 2_753_525
number of collisions: 9_995
mean expected collisions: 0.00
and its sdev: 0.00
z: +21968232.90
worst pileups:
4
4
3
3
3
3
3
3
3
3
The z score is still very high, but max pileup has become quite minor. Move to 4-element subsets and max pileup for frzenset zooms to over 100 thousand, while the xor of 1-tuple hashes peaks at a modest 13.
Tuple hashing doesn't do full-blown xxHash. In the full version, there's a long stretch at the end to work harder at avalanche. The per-element version tuple uses skips that. There's some useful left-to-right propagation via its rotate operation, but for 1-element tuples that's a "one and done" thing. High-order bits can't affect low-order ones further away than the one-tiee rotate count, Its effect in this context is nevertheless dramatic.
So what to do? If the problem is lack of left-to-right propagation, introduce some. Everyone else does ;-)
-
Roll our own. Even one ju8icious right shift could help a lot. Rohate (as in xxHash) even more (rotate propagates in both directions).
-
Look at adopting the tail end of xxHaah.
-
The C++ Boost library's
combine_hashes()also propagates in both directions. -
As does the "tempering" code before the Mersenne Twister delivers a result. The underlying generator is very slow at propagating bit changes across the state space, so they tacked on a "heavy avalanching sequence" to disguise that weakness. But even so it can very famously fall into "zeroland regions" (if most of state space bits happen to become zero, it cah take millions of iterations to break free of that).
As for frozendict, it doesn't appear to need any of this. The current PR uses a much stronger scheme based on copy/pasting two rounds of tuple's xxHash code, one round for the key hash and another to fold in the value hash. That's bound to be stronger than just (as in the attached code) xor'ing the hashes of 1-tuples, and it's almost certainly a complete waste of cycles to go on to call shuffle_bits() now. The propagation it does is weak (and zero of left-to-rght) compared to xxHash's core.
At a higher level, the spread of copy/pasted "mystery code" across modules is concerning. I'm old enough to know where all the bodies are buried, but the next generation isn't. If we have to duplicate code (and typically without enough comments to trace the code back to its original source), let's at least stick it in a new include file? Then there's just one place to look for comprehensive explanations and cautions - and no possibility of getting out of sync by accident. This kind of code is the opposite of "obvious" 😉.
Driving code:
from test import support
from collections import Counter
import math
def fint(n):
return f"{n:_}"
def analyze(hashcounts, nbins=1<<support.NHASHBITS):
print("number of possible hash codes:", fint(nbins))
assert all(hashcounts.values()) # counts of 0 not allowed
print()
numtotal = hashcounts.total()
numseen = len(hashcounts)
ncollision = numtotal - numseen
print(" number of hash codes total:", fint(numtotal))
print("number of unique hash codes:", fint(numseen))
print(" number of collisions:", fint(ncollision))
print()
mean, sdev = support.collision_stats(nbins, numtotal)
print("mean expected collisions:", format(mean, ".2f"))
print(" and its sdev:", format(sdev, ".2f"))
diff = ncollision - mean
z = diff / sdev
print(" z:", format(z, "+.2f"))
print()
print("worst pileups:")
for h, c in hashcounts.most_common(10):
print(" ", fint(c))
N, K = 8, 3
from itertools import combinations
def create(N=N, K=K):
c = Counter()
pow2 = 1 << N
small = tuple(i / pow2 for i in range(pow2))
for t in combinations(small, K):
c[hash(frozenset(t))] += 1
assert c.total() == math.comb(pow2, K)
return c
def create2(N=N, K=K):
c = Counter()
pow2 = 1 << N
small = tuple(i / pow2 for i in range(pow2))
for t in combinations(small, K):
h = 0
for e in t:
h ^= hash(tuple([e]))
c[h] += 1
assert c.total() == math.comb(pow2, K)
return c
analyze(create())
analyze(create2())CPython versions tested on:
CPython main branch, 3.14, 3.13
Operating systems tested on:
No response
Activity
tim-one commentedon May 20, 2026
Google's Gemini pointed me at these 2 64-bit mixers as "best of general breed" for avalanche quality (every input bit affects every output bit.
SplitMix64 / MurmurHash3
Nasam
The latter is fastest, but of "slightly" lower quality. Two things they have in common:
1, No left shifts. Only right shifts. That's what gives "left to right" propagation.
2. "Right to left" is done by multiplication, which is much stronger than left shifting.
Nasm in fact does worse than than tuple-based approach on the challenging 4-subsets of 256 case in my driver:
Far better than our
scramble_bits(), though, and possibly acceptable.Murmur does best of all, but appears slightly more expensive than our xxHash-based tuple core (both have two multiplies, but murmur a little more shift-xor action than xxHash's slngle rotate).
In fact, it's perfect! No collisions, and max pileup of 1 (the smallest possible). @rhettinger,, what do you think? Nasam may be even faster than what we have now, but Murmur is in a whole different universe of avalanche quality.
Here's the murmur code I used:
tim-one commentedon May 21, 2026
I wrote code to test "avalanche" on random 64-bit inputs. Ideally, a 1-bit change in an input should change around 32 bits in the output. And for all bit position pairs, flipping bit i in the input should flip bit j in the output about half the time.
murmur does very well on that, with actual (i, j) counts differing from the expected ideal mean by at worst 3 standard deviations. (using a normal distribution approximation to a p=0..5 binomial distribution) Since there are 4096 position pairs, seeing some$\pm 3$ deviations is expected.
Nasam does very well on average number of bits changed (very close to 32), but has extremely out-of-whack (i, j) counts at times, hundreds of sdevs from the expecte4 mean. ( think Gemini hallucinated that Nasam was only "slightly" weaker than murmur.
Our
shuffle_bits()didn't really aim at avalanche, just a bit of right-to-left propagation - and it shows ;-) For almost all i , flipping bit i affects bit j sometimes never, sometimes always, across 100 thousand trials, leading to z scores in the hundreds.. An extreme is flipping bit position 63,. which doesn't change any output bit other than 63 (no left-to-right propagation at all). The average number of bits changed was 16.7, about half the idea;l.Unless I transcribed the C code to Python incorrectly, but I don't think that's it. Here's what I used
If that's wrong, let me know! Several things suggest it would do poorly at avalanche:
murmur stands alone, but it's not perfect. It's not "crypto strength" avalanche, and seemingly can't be with so few operations. While in my
comb(256,, 4)subsets "bad case", it gives unique 64-bit hash cades, a set with 2**n slots only looks at the last n bits for the first probe, and murmur's results are not ideal in the lower order bits., Some collisions are inevitable (pigeonhole) then, and murmur's is about 10z higher then. But worst pileup is just 8, which is thoroughly acceptable.The hash probe sequence does its own "left-to-right" propagation, by folding in higher-order bits as it goes along,. and the more it does fold in, the smaller the z scores deviate from "really random" inputs. By the time it folds in 39 bits, the collision z score was only +0.75, and at 49 bits they're unique again. So the initial pileups will resolve as the probe sequence goes along.
tim-one commentedon May 22, 2026
I was mistaken to call this "mumur". It's actually SplitMix64, which is structurally the same as one member of the MurMur family, but uses different constants, derived from deep analysis and mountains of statistical testing.
Cute: by design it gets much closer to 50% probability of flipping each output bit (given a 1-bit input change) than a "truly random" mixer would. Took me by surprise! I ran chi-square tests on a matrix recording how often a change in input bit i caused a change in output bit j, and the chi-square statistic for each row was almost always "impossibly low".
So lots of double- and triple-checking, then more searches. It all makes sense now 😃 .
It can also be used a decent 64-bit PRNG with very small state (64 bits):
|https://prng.di.unimi.it/splitmix64.c
tim-one commentedon May 22, 2026
Recapping, SplitMix64 is best-of-breed, and does spectacularly well on the sets-of-floats problem case here. It's industry-standard,, very widely deployed,. and is well-grounded in academic theory, with people working on it from Guy Steele to Sebastian Vigna and Melissa O'Neil (of PCG fame,). There's every reason to expect it will defeat all patterns that show up in real life.
Bite the bulled. I don't really care that it may take 12 cycles (on a box with 3-cycle 64x64->64 IMUL, which is no longer cutting edge). In this case, we'd get better protection against catastrophic slowdowns than we'd pay for. It's much better at spreading out input differences than one round of xxHash's core too (which is expected - you get no more than you pay for 😉:, and xxHash's core has 5 fewer bit-fiddling ops).
tim-one commentedon May 23, 2026
Let's make that very clear - it's not just unlucky, it's certain to be extremely bad.
All the hash codes for these floats have at least 53 trailing zero bits. All the variation is in their top 11 bits. Regardless of how many are xoir'ed together (from 0 through 256), the same is true of their xor reduction: because
shuffle_bits()does no left-to-right propagation, all xor's of a subset's shuffled hashes will also have at least 53 trailing zero bits. So only 2**11 = 2048 final hash codes are possible. In the case of 4-subsets,.So, by a pigeonhole argument, there must be at least 85348 subsets with the same 64-bit hash code. That's already a disaster - 100K is only a little bit unluckier than the ideal theoretical lower bound.
It's remarkable that splitmix64 manages to deliver a unique hash code for each 4-siubset.
zware commentedon May 23, 2026
gvanrossum commentedon Nov 11, 2026
This Issue was Tim's last contribution ever.
pythongh-150134: Use a stronger bit mixer for frozenset and frozendic…
skyvegetable666 commentedon Nov 12, 2026
I have a patch for this that follows the SplitMix64 approach analysed in this
issue (fmix32 on 32-bit builds). One deviation from the mix64 snippet above:
I add SplitMix64's additive "golden gamma" before mixing so that a zero hash
does not map to zero; I'm happy to drop it if preferred.
The new mixer gives unique hashes for the {i/256} subsets (64-bit) and
near-random ones on 32-bit; large frozensets hash about 1.6-1.8x slower
(pyperf numbers will be in the PR), while the pathological case is about 2x
faster. Please let me know if someone is already working on this; otherwise
I'll open a PR shortly.