[BUG]: Random key generator does not produce keys according to input parameters

[sleeepyjack]

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 and M_EXPECTED=1 the M_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