torsdag 24 januari 2019

Better, stronger mixer and a test procedure.


An intermediate result (much stronger mixer).

A frustrating search.

When working on finding good mixers, I got really frustrated by the extremely slow process of testing a new set of constants or other tweaks to functions that were "kind of good".
My criterion for "success" was that the output from a simple counter, starting at 0, passed to the mixing function, and then taking the output from the mixing function and feeding it to PractRand with -tf 2 should not generate any failures up to $2^{45}$ bytes.

Eventually, I came to realize that what I really wanted was not just a function that would satisfy the "generate PractRand-passing output when fed a unitary counter" but rather "a decent approximation of a random permutation". Such a permutation would give a higgledy-piggledy sequence from a very regular one, regardless of what the regularity looks like (just kidding; the regularities of interest are affine transformations, of course there are many other sequences one could think of as "regular"). Previosuly, I had been testing with feeding gray-code sequences to the mixing function, hoping that the unit Hamming distance between adjacent inputs would reveal flaws more quickly. For the functions I tested, I couldn't find that it made any difference w.r.t. how quickly testing failed.

As I was thinking about more sequences that would be "very well ordered" I came up with a very simple testing procedure that seems to work well: A function that pass the subtests described below is also very likely to work well on any kind of (affine) counter update.

The fact that many of the subtest input sequences intersect does not affect the tests since they are run independently.

Test procedure

Instead of testing the full output, which is very slow, test many short output sequences in the hopes that anomalies in the mixer will be revealed more quickly. There's quite some conjecturing here: the (lack of) failures on many short tests hopefully correlate with overall quality. If the mixer is good, this is also a very lengthy process (the way I have been doing it, 128 TB of data will be tested if there are no failures) but running many small tests (1 TB a piece) can be done in parallell on a machine with many cores but without a using a lot of RAM.

Naming

To avoid confusion, let's call this test procedure "RR-b-x-TF2-0.94". "RR" to indicate "rotate and bit reversal", "b" for the word size in input/output bits, x for the tlmax-exponent, TF2 to indicate that PractRand was run with "-tf 2" and "0.94" for the version of PractRand I am currently using. The same procedure can be used for any permutation of size $2^{8b}$. Pseudo-code for RR-b-x-TF2-0.94:
# The tests I have run have been with b = 64 and x = tlmax = 40,
# i.e. 1 TB per subtest.
# rfun is either the identity function or a b-bit bit-order reversal function.
for rfun in {identity, bitreversal}
  # Rotate counter 0 to (b - 1) bits.
  for r in {0, ..., b - 1}
    # No failure seen for this rfun & rotation so far.
    failure = 0
    # 2^x bytes, 2^x / b * 8 b-bit words.
    for ctr in {0, ..., (2^tlmax / b * 8) - 1}
      # Feed PractRand, break on failure.
      # RORb is a b-bit right rotate function.
      if feedPractRandFails(RORb(rfun(ctr), r))
        # Note the failure level.
        failure = ceil(log_2(ctr))
        break for
      end if
    end for
    emitTestScore(rfun, r, failure)
  end for
end for

Test results

MurmurHash3 finalizer

RR-64-40-TF2-0.94 fails the MurmurHash3 finalizer quickly. This is to be expected considering that it is known to fail quickly when fed a unitary counter.

MurmurHash3 failures, $2^{40}$ bytes maximum.
Offset IDENTIY
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 17181818171616161615151715141515
16 14141414141515151515161616161515
32 16161717161614141615141515151515
48 15141414141415151515151617171717
Offset REVERSE
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 15171818181717161614141414141417
16 17171617171717181917181817161414
32 15161718181717171716141414141515
48 17171717171717181819191818181716

MurmurHash3, Variant 13

RR-64-40-TF2-0.94 fails Variant 13 quickly too. This is also to be expected considering that it is known to fail almost as fast as the MurmurHash3 finalizer.
MurmurHash3/Variant 13 failures, $2^{40}$ bytes maximum.
Offset IDENTIY
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 19171818181718181818181919161717
16 17171617161617171617161717171818
32 19191919191919191919202019201919
48 17171617171716171617171718181919
Offset REVERSE
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 16171818181919202019202019202019
16 20192118192119222021222120222219
32 18181819192020192020192020202019
48 21181821192220211918181818181818

Ettinger's mixer

Tommy Ettinger came up with a quite different construction, compared to MurmurHash3 (and variants) and my own rrmxmx (in C):
uint64_t ettingerMixer(uint64_t v) {
  uint64_t z = (v ^ 0xDB4F0B9175AE2165UL) * 0x4823A80B2006E21BUL;
  z ^= rol64(z, 52) ^ rol64(z, 21) ^ 0x9E3779B97F4A7C15UL;
  z *= 0x81383173UL;
  return z ^ z >> 28;
}
According to him it passes 32 TB of PractRand but with -tf unspecificed, defaulting to 1 instead of 2 which is what I use for all tests. I was a bit too quick here and tested his function with RIGHT-rotates and not LEFT-rotates which is what Ettinger used. The table below is now updated to reflect a correct implementation of his mixer. The performace w.r.t. RR-64-40-TF2-0.94, compared to my incorrect implementation, is about the same. 122 failed tests out of 128:
"Ettinger's mixer" failures, $2^{40}$ bytes maximum.
Offset IDENTIY
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 40161615141516161512121314151415
16 15161516161718191717171718171718
32 19202123242526272828303032241916
48 16191919222224314040404036344040
Offset REVERSE
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 12131514151515151616161616161617
16 17181919222020172325252526303029
32 30343336211917161716161721211919
48 22222120212019201918161616151514
So this is a special case where an increment of one works particularly well. It would be interesting to know at what level it fails PractRand (with -tf 2, if at all) with a unitary counter.

Changing the rotation constants to {12, 43} (corresponding to right rotates instead of left rotatets) gives a function with about the same number of failures, 120 out of 128:
"Ettinger's mixer, ROR-version", $2^{40}$ bytes maximum.
Offset IDENTIY
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 40151514151516161515151515151515
16 16161616161616181817181718191918
32 17181921231917171919192124283135
48 36373834363635384040404040404040
Offset REVERSE
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14141415151515161616171617171716
16 18171716242322212425252219171917
32 16161719191921222527262524232221
48 20191817171717171717171716161515

Testing rrmxmx

I already knew that rrmxmx fails PractRand -tf 2 -te 1 after $2^{44}$ bytes when fed a unitary counter, starting at 0. If I recall correctly that took about one week of computing time to find out. The table below took about 20 minutes to generate and it clearly shows that rrmxmx is far from optimal (note that x = 33, quick and dirty):
The original rrmxmx, $2^{33}$ bytes maximum.
Offset IDENTIY
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 33333333333333333325253333333333
16 33283333333333333333333333333333
32 33313333333330303033333333333333
48 33333333333333333333333333333333
Offset REVERSE
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 33333333333333333333312831333333
16 33333333333333333333332833333333
32 28283025223333333333333333333333
48 33333333333333333333333333333333
The somewhat good news to anyone who decides to use it are that an increment of 1 is the only odd integer I have found which fails PractRand. The even better news is that a variation where the first ror-ror-xor and first shift-xor are interchanged in general performs better. For the constants I have tried so far, it still fails RR-64-x-TF2-0.94 but to a lesser extent. Which leads us to the latest and greatest. Even more rotates.

Intermediate result, my best so far

Compared to my previous function, rrmxmx, this is much more well behaved and has passed 128 TB of PractRand -tf 2 with a unitary counter (one single run, inputs $\{0, \ldots, 2^{44} - 1\}$). Testing with RR-64-40-TF2-0.94, there is 1 failure:
rrxmrrxmsx_0 failures, $2^{40}$ bytes maximum.
Offset IDENTIY
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 40404040404040404040404040404040
16 40404040404040404040404040404040
32 40404040404040404040404040404040
48 40404040404040404040404040404040
Offset REVERSE
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 40404040404040404040404040403940
16 40404040404040404040404040404040
32 40404040404040404040404040404040
48 40404040404040404040404040404040
Trying to fix this failure (ROR(reversed, 14)) has so far only given me variants with more failures or a single failure happening in a different subtest with less than $2^{39}$ bytes.
Compared to rrmxmx it is slightly slower, doing 2 rotations instead of the shift in the middle of rrmxmx. Temporarily, let's call it "rrxmrrxmsx_0" (in C):
// Old mixer, my rrmxmx
uint64_t rrmxmx(uint64_t v) {
  v ^= ror64(v, 49) ^ ror64(v, 24);
  v *= 0x9FB21C651E98DF25L;
  v ^= v >> 28;
  v *= 0x9FB21C651E98DF25L;
  return v ^ v >> 28;
}

// New mixer, "rrxmrrxmsx_0", failing one subtest of RR-64-40-TF2-0.94.
// With a unit counter starting at 0, it has passed 128 TB of
// PractRand 0.94 -tf 2 without anomalies found past 2 TB.
uint64_t rrxmrrxmsx_0(uint64_t v) {
  v ^= ror64(v, 25) ^ ror64(v, 50);
  v *= 0xA24BAED4963EE407UL;
  v ^= ror64(v, 24) ^ ror64(v, 49);
  v *= 9FB21C651E98DF25UL;
  return v ^ v >> 28;
}
I found this function a few months ago but have been hoping to find something of similar speed that doesn't fail any of the 128 subtests. If I do find one, I'll post it here!

I kind of gave up on finding better constants for functions having the same form as the original rrmxmx. To check that there really is a reasonable correlation between "quite good behaviour" when feeding the function with a unitary counter and not failing many subtests, I am running RR-64-40-TF2-0.94 on it. It fails much much less badly than MurmurHash3 and Variant13 but still much worse than rrxmrrxmxs.

Conclusion

Running RR-b-x-TF2-0.94 can be relatively quick way of detecting if a particular 64-bit permutation function is a good approximation of a random permutation. The approach can be extended to any permutation of size $2^{8b}$. As a preliminary step, one could lower x significantly. In case the function under test gives many failures at, say, x = 30, it may not be worthwhile to examine the number of failures at x = 40 or above. Passing the test is a necessary but not sufficient requirement for any function that is expected to behave like a random permutation. There are probably bad permutations that do pass RR-b-x-TF2 but no good ones that does not pass it.

NASAM: Not Another Strange Acronym Mixer!

NASAM: Not Another Strange Acronym Mixer The various abbreviations became more and more unpronouncable. I give you "NASAM". T...