Stronger, better, morer, Moremur; a better Murmur3-type mixer.

I'll keep this brief: The original constants used in MurmurHash3 and Stafford's Variant 13 are not as good as they could have been. This affects the strength of SplitMix64.

The testing procedure I've used is described in an earlier post. There is one extension, compared to the earlier post: every rotation and reversal is also complemented for a total of 256 subtests. I'll call the extended version "RRC-64-40-TF2-0.94" for "Reversed, rotated, complemented-64 bits, 2^40 bytes, PractRand 0.94 with -tf 2". Without further ado, here's "Moremur", a statistically stronger but equally fast mixer:

uint64_t moremur(uint64_t x) {
  x ^= x >> 27;
  x *= 0x3C79AC492BA7B653UL;
  x ^= x >> 33;
  x *= 0x1C69B3F74AC4AE35UL;
  x ^= x >> 27;

  return x;
}

One strong flaw with this construction, i.e. the first operation being an xor-shift, is that there are many increments that will lead to few or none of the less significant bits being one. This in turn implies that the less significant bits will be zero after the first two operations, xor-shift and multiply. Particularly bad increments have this form: $\gamma = (2^s + 1)a, a \lt 2^s$, $s$ being the first shift and $a$ being sparse.

In the table below, Moremur outperforms Murmur3 and Variant13 by quite some margin.

Table 1: Test length where PractRand fails

$\gamma$	Murmur3	Variant13	Moremur
0x0000000000000001	$2^{17}$	$2^{19}$	$2^{33}$
0x0000000000000003	$2^{17}$	$2^{17}$	$2^{34}$
0x0000000000000005	$2^{17}$	$2^{18}$	$2^{34}$
0x0000000000000009	$2^{16}$	$2^{18}$	$2^{34}$
0x0000010000000001	$2^{18}$	$2^{21}$	$2^{41}$
0xffffffffffffffff	$2^{17}$	$2^{19}$	$2^{33}$
0x0000000000ffffff	$2^{17}$	$2^{23}$	$2^{37}$
0xffffff0000000001	$2^{18}$	$2^{23}$	$2^{43}$
0x0000000000555555	$2^{18}$	$2^{28}$	$2^{42}$
0x1111111111110001	$2^{25}$	$2^{30}$	$> 2^{46}$
0x7777777777770001	$2^{28}$	$2^{34}$	$> 2^{45}$
0x7f7f7f7f33333333	$2^{30}$	$2^{33}$	$> 2^{46}$
0x5555550000000001	$2^{21}$	$2^{27}$	$2^{45}$
0xc45a11730cc8ffe3	$2^{39}$	$> 2^{42}$	$2^{?}$
0x2b13b77d0b289bbd	$2^{39}$	$> 2^{42}$	$2^{?}$
0x40ead42ca1cd0131	$2^{40}$	$> 2^{42}$	$2^{?}$

As can be seen from the tables below, these constants are a great improvement over the ones I've been aware of so far (original MurmurHash3 and Variant13). Moremur still fails RRC-64-40-TF2-0.94 but far from as badly as the earlier constants do.

Moremur failures, $2^{40}$ bytes maximum.

ror64(reverse(x, R) ^ 0x0000000000000000, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	33	19	19	19	22	22	24	25	28	27	28	29	16	16	16	17		16	17	19	19	20	28	27	28	34	29	29	35	36	37	37	38
16	17	17	18	19	19	19	19	20	21	22	23	23	24	25	26	27		36	35	35	39	40	34	31	31	39	40	39	38	37	34	34	36
32	28	29	30	31	31	32	33	33	34	34	34	34	34	33	32	32		28	34	33	32	32	31	33	33	34	34	34	35	35	36	37	36
48	32	28	28	28	29	29	29	29	30	30	30	30	31	31	31	32		31	31	31	33	36	37	36	28	33	34	31	31	28	25	22	19
ror64(reverse(x, R) ^ 0xFFFFFFFFFFFFFFFF, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	33	19	19	19	22	22	24	25	28	29	18	28	15	16	16	17		16	17	19	21	21	26	28	30	34	31	34	34	36	36	37	37
16	17	18	18	19	19	19	19	19	21	22	23	24	24	25	26	27		36	35	35	39	40	34	31	31	39	40	39	38	37	34	34	36
32	28	29	30	30	32	33	33	34	34	35	35	34	34	32	33	32		28	34	33	32	32	31	33	33	34	34	34	35	36	36	36	36
48	32	28	28	28	28	28	29	29	29	30	30	30	31	31	32	32		31	31	31	33	35	35	34	28	32	32	31	30	28	25	22	19

Murmur3 failures, $2^{40}$ bytes maximum.

ror64(reverse(x, R) ^ 0x0000000000000000, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	17	18	18	18	17	16	16	16	16	15	15	17	15	14	15	15		15	17	18	18	18	17	17	16	16	14	14	14	14	14	14	17
16	14	14	14	14	14	15	15	15	15	15	16	16	16	16	15	15		17	17	16	17	17	17	17	18	19	17	18	18	17	16	14	14
32	16	16	17	17	16	16	14	14	16	15	14	15	15	15	15	15		15	16	17	18	18	17	17	17	17	16	14	14	14	14	15	15
48	15	14	14	14	14	14	15	15	15	15	15	16	17	17	17	17		17	17	17	17	17	17	17	18	18	19	19	18	18	18	17	16
ror64(reverse(x, R) ^ 0xFFFFFFFFFFFFFFFF, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	17	17	18	17	17	15	16	16	16	15	15	17	14	15	15	15		14	17	18	18	17	17	16	17	16	15	14	14	14	14	16	17
16	14	14	14	14	15	15	15	15	15	15	16	16	16	16	15	15		17	17	16	17	17	17	17	18	18	18	17	16	15	15	14	14
32	16	17	17	17	16	14	14	14	15	15	14	15	14	15	15	14		15	15	17	18	18	17	17	17	17	16	15	14	14	14	14	15
48	14	14	14	14	14	14	15	15	15	15	15	16	17	17	17	17		17	17	17	16	17	17	17	17	18	19	19	18	18	18	17	15

Variant 13, $2^{40}$ bytes maximum.

ror64(reverse(x, R) ^ 0x0000000000000000, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	19	17	18	18	18	17	18	18	18	18	18	19	19	16	17	17		16	17	18	18	18	19	19	20	20	19	20	20	19	20	20	19
16	17	17	16	17	16	16	17	17	16	17	16	17	17	17	18	18		20	19	21	18	19	21	19	22	20	21	22	21	20	22	22	19
32	19	19	19	19	19	19	19	19	19	19	20	20	19	20	19	19		18	18	18	19	19	20	20	19	20	20	19	20	20	20	20	19
48	17	17	16	17	17	17	16	17	16	17	17	17	18	18	19	19		21	18	18	21	19	22	20	21	19	18	18	18	18	18	18	18
ror64(reverse(x, R) ^ 0xFFFFFFFFFFFFFFFF, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	19	17	18	18	18	17	18	18	18	18	18	18	19	16	17	17		16	17	18	18	18	19	19	20	20	19	20	20	19	20	20	19
16	17	17	16	17	16	17	17	17	16	17	16	17	17	17	17	18		20	19	21	18	18	21	19	22	20	21	22	21	20	22	22	19
32	19	19	19	19	19	19	19	19	19	19	20	20	19	20	20	19		18	18	18	19	19	20	20	19	20	20	19	20	20	19	20	19
48	16	17	16	16	17	17	16	17	16	17	17	17	18	18	19	19		21	19	19	21	19	22	20	21	19	18	18	18	18	18	18	18

The constants were found through a stochastic hill climber I wrote using CUDA. The first testing I did of Murmur3 and Variant13 revealed that they had fairly weak higher order avalanche properties. Letting the fitness function include metrics for 1st to 4th order avalanche proved to be quite successful. The CUDA program was used for sieving; once some possibly good candidates turned up, I ran them through RRC-64-40-TF2-0.94. The constants above were the best I could find; the fitness function, combining several tests, was too insensitive to make any further improvements possible with the approach I used.

Conclusion

The shifts and constants above give a permutation that is statistically closer to a pseudo-random permutation than the ones used in SplitMix64, java.util.SplittableRandom and java.util.ThreadLocalRandom. In particular, the number of bad gammas/increments should be considerably fewer.