Page MenuHomePhabricator

sigencoding_tests : use pseudorandom generator for flag patterns
ClosedPublic

Authored by markblundeberg on Feb 1 2019, 03:54.

Details

Summary

4096 iterations tests a big mix of flag combination mixes,
and runs far faster than the previous 131072 nonrandom iterations.
The nonrandom approach was getting unsustainable as we are getting up
to 1<<20 in the flag bits (would be 1 million iters).

Test Plan

I've run this LCG in python to do histogramming & verify the
correct order. Also the iterations include a testpoint to make sure the LCG
is producing the expected sequence.

Diff Detail

Repository
rABC Bitcoin ABC
Branch
lcg_sigencoding_tests
Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 4824
Build 7711: Bitcoin ABC Buildbot (legacy)
Build 7710: arc lint + arc unit

Event Timeline

Does this hit enough flag combinations? See comments in the code..

Here is the Python code for doing a direct histogram of four-flag AND and four-flag NOR for every possible combination of four flags, producing the numbers mentioned in code comments:

#!/usr/bin/env python3
import numpy as np

MAX = 2**64 - 1
def nextlcg(x):
    return (x * 6364136223846793005 + 1442695040888963407) & MAX

# flags goes like:
#0x14057b7e
#0x1a08ee11
#0x9af67822
#....

# create 4D arrays 32x32x32x32...
histand = np.zeros((32,32,32,32), dtype='uint32')
histnor = np.zeros((32,32,32,32), dtype='uint32')

state = 0
for i in range(4096):
    state = nextlcg(state)
    flags = state >> 32
    flagbits = (np.array(list('{:032b}'.format(flags))) == '1')

    # use numpy array broadcasting
    hand = flagbits * flagbits[:,None] * flagbits[:,None,None] * flagbits[:,None,None,None]
    hnor = ~(flagbits + flagbits[:,None] + flagbits[:,None,None] + flagbits[:,None,None,None])

    histand += hand
    histnor += hnor
    if i % 100 == 0:
        print(i, np.min(histand), np.min(histnor))
print('Minimums for 4096 iters: ', np.min(histand), np.min(histnor))

For bigger flag tuples, it gets hard to brute force like that but we can do probabilistic predictions based on poisson distribution. Lets say you're worried about a specific combination of M=7 flags occurring or not (flag3=True,flag20=False,...) -- the probability of this being missed is exp(-4096/2^M). The chance of hitting ALL possible variations of those 7 flags is about (1 - 2^M * exp(-4096/2^M)).

For 4096 this only gets to be a problem once we reach M=9 (17% chance that we missed one possible 9-flag combination, but, 99.97% chance of hitting a *given* 9-flag combination). With M=8 these numbers are ~10^-5 and 99.99999% respectively.

However if we are worried about missing one possible true/false variation of all *possible* M-flag sets, the probability is (32 choose M) * 2^M * exp(-4096/2^M). For M=8 we are guaranteed to miss some variations, With M=7 it is very unlikely (10^-5) that out of all ~3 million possible choices of 7 flags, and all 128 true/false variations of each of those flagsets, we would miss any.

deadalnix requested changes to this revision.Feb 1 2019, 17:03

This is great. I do thing that there are other tests that would benefit from this. I think we can shave off a lot of run time from the test suite while keeping the same runtime.

src/test/sigencoding_tests.cpp
183 ↗(On Diff #7086)

Update the state after picking a value, this ensure we test all zeros.

188 ↗(On Diff #7086)

If you feel this is require,d it's probably better to encapsulate the generator in its own class and write tests for it. This is fairly unrelated to what is tested here. It also seems logical to do that because this is already the second place where this generator is used now.

365 ↗(On Diff #7086)

dito

370 ↗(On Diff #7086)

dito

This revision now requires changes to proceed.Feb 1 2019, 17:03
src/test/sigencoding_tests.cpp
183 ↗(On Diff #7086)

👍

188 ↗(On Diff #7086)

Hmm true. I think the class is overkill at the moment but I'll make a separate boost test for this purpose.

(My worry with this test is that maybe some architectures don't do the 64 bit multiplication wraparound correctly, and thus maybe get stuck into a small cycle)

ensure flags=00000...000 is done at start; rewrap LCG as class & separate test

deadalnix requested changes to this revision.Feb 1 2019, 17:43
deadalnix added inline comments.
src/test/sigencoding_tests.cpp
101 ↗(On Diff #7096)

Put that in a header file (there is probably an existing one that can be leveraged for this.), Migrate the radix test to use it and make it have its own test. This can be done in its own diff or in that one.

rename GetFlags and just do the advancing in there. Just call it next() or something.

This revision now requires changes to proceed.Feb 1 2019, 17:43
deadalnix added inline comments.
src/test/sigencoding_tests.cpp
18 ↗(On Diff #7107)

You can remove the comment. It's not up to this test to know how's the generator working.

This revision is now accepted and ready to land.Feb 1 2019, 22:49
src/test/sigencoding_tests.cpp
18 ↗(On Diff #7107)

k

This revision was automatically updated to reflect the committed changes.