[BUG]: Random key generator does not produce keys according to input parameters
Opened this issue · 0 comments
sleeepyjack commented
Is this a duplicate?
- I confirmed there appear to be no duplicate issues for this bug (https://github.com/NVIDIA/cuCollections/issues)
Type of Bug
Silent Failure
Describe the bug
This snippet generates N
uniform keys given a target key multiplicity M
for each iteration and produces the following output:
N=10
M_EXPECTED=1
M_MEASURED=10
CONSECUTIVE_SAMPLES=[ 3 3 3 3 3 3 3 3 3 3 ]
N=10
M_EXPECTED=5
M_MEASURED=10
CONSECUTIVE_SAMPLES=[ 2 2 2 2 2 2 2 2 2 2 ]
N=10
M_EXPECTED=10
M_MEASURED=10
CONSECUTIVE_SAMPLES=[ 1 1 1 1 1 1 1 1 1 1 ]
N=100
M_EXPECTED=1
M_MEASURED=100
CONSECUTIVE_SAMPLES=[ 44 44 44 44 44 44 44 44 44 44 ]
N=100
M_EXPECTED=5
M_MEASURED=100
CONSECUTIVE_SAMPLES=[ 13 13 13 13 13 13 13 13 13 13 ]
N=100
M_EXPECTED=10
M_MEASURED=100
CONSECUTIVE_SAMPLES=[ 8 8 8 8 8 8 8 8 8 8 ]
N=1000
M_EXPECTED=1
M_MEASURED=41.6667
CONSECUTIVE_SAMPLES=[ 244 244 244 244 244 244 244 244 244 244 ]
N=1000
M_EXPECTED=5
M_MEASURED=166.667
CONSECUTIVE_SAMPLES=[ 194 194 194 194 194 194 194 194 194 194 ]
N=1000
M_EXPECTED=10
M_MEASURED=250
CONSECUTIVE_SAMPLES=[ 21 21 21 21 21 21 21 21 21 21 ]
N=10000
M_EXPECTED=1
M_MEASURED=4.44642
CONSECUTIVE_SAMPLES=[ 9668 9668 9669 9669 9669 9669 9670 9670 9670 9670 ]
N=10000
M_EXPECTED=5
M_MEASURED=22.1729
CONSECUTIVE_SAMPLES=[ 1801 1801 1801 1801 1802 1802 1802 1802 1802 1802 ]
N=10000
M_EXPECTED=10
M_MEASURED=44.4444
CONSECUTIVE_SAMPLES=[ 248 248 248 248 248 248 248 248 248 248 ]
N=100000
M_EXPECTED=1
M_MEASURED=1.87691
CONSECUTIVE_SAMPLES=[ 62772 62774 62776 62779 62781 62783 62785 62788 62790 62792 ]
N=100000
M_EXPECTED=5
M_MEASURED=5
CONSECUTIVE_SAMPLES=[ 8175 8176 8176 8177 8177 8178 8178 8179 8179 8180 ]
N=100000
M_EXPECTED=10
M_MEASURED=10
CONSECUTIVE_SAMPLES=[ 6935 6935 6935 6935 6936 6936 6936 6936 6936 6937 ]
N=1000000
M_EXPECTED=1
M_MEASURED=1.34564
CONSECUTIVE_SAMPLES=[ 854682 854705 854727 854750 854772 854795 854817 854840 854862 854885 ]
N=1000000
M_EXPECTED=5
M_MEASURED=5
CONSECUTIVE_SAMPLES=[ 68414 68419 68423 68428 68432 68437 68441 68446 68450 68455 ]
N=1000000
M_EXPECTED=10
M_MEASURED=10
CONSECUTIVE_SAMPLES=[ 98136 98138 98140 98142 98145 98147 98149 98151 98154 98156 ]
Which surface multiple problems with the generated keys:
- When
N<100,000
then measured key multiplicity is way off the expected multiplicity value - Even for large
N
andM_EXPECTED=1
theM_MEASURED
is still somewhat far off - The sequence of output keys seems to be at least partially sorted (see
CONSECUTIVE_SAMPLES
) which is undesireable since it leads to caching effects that could skew our benchmarks
How to Reproduce
See above section
Expected behavior
- Fix multiplicity value for small
N
- Find a way to ensure
M_EXPECTED=1 -> M_MEASURED=1+epsilon
(maybe just dispatch to a unique key sequence?) - Eliminate consecutive runs of the same key in the output (either by shuffling the generated keys one more time or shuflle/randomize the seeds)
Reproduction link
https://godbolt.org/z/cqeWG8af1
Operating System
No response
nvidia-smi output
No response
NVCC version
No response