coverage: 68.322% (+0.2%) from 68.154%
when pulling ce35824 on cmolder:develop/rng-fix
into 0bfb855 on ChampSim:develop.

I know adding boost to a project can be a big change, so I went ahead and limited the usage of it to a single header file (util/random.h). So, if we write our own implementation for champsim::uniform_int_distribution, we can get away with not using boost at all.

Is it as simple as something like

template <typename T>
class uniform_int_distribution {
  T a;
  T b;
public:
  uniform_int_distribution(T a_param, T b_param) : a(a_param), b(b_param) {}

  template <typename Gen>
  T operator()(Gen& generator) const {
    const auto width = b-a;
    constexpr auto genwidth = Gen::max() - Gen::min();
    const auto upperbound = Gen::min() + width*(genwidth / width);

    T retval = generator();
    while (retval >= upperbound) {
      retval = generator();
    }

    return ((retval - Gen::min()) % b) + a;
  }
};

Of course, that's a very, very loose sketch and doesn't include the full interface, but is it more complicated than just discarding out-of-range values from the generator? I'd want to test this to the moon and back, but I think it's conceptually pretty simple.

On the topic of adding boost, because we manage dependencies with vcpkg, I'm not too troubled by adding an additional package dependency. It will require all users to run vcpkg install again, but if it's justified, it's justified. My thinking is this: external libraries are (ideally) tested and maintained by someone else, so it's generally worth our brain bandwidth to rely on them, unless the thing is so simple we can just write it ourselves.

If we can find justifiable uses of Boost::random somewhere else, then I think we should add it. Example: our dependency on nlohmann::json, currently used only for stats output, but hopefully we can use it to parse the configuration soon.

I don't think you need to discard anything actually.
I would assume that a random number generator of any kind produces an apparently random uniform distribution, so wouldn't it be sufficient to just modulus the generated value by the width of the desired uniform distribution? Why the while loop and upper bound?

template <typename T>
class uniform_int_distribution {
  T a;
  T b;
public:
  uniform_int_distribution(T a_param, T b_param) : a(a_param), b(b_param) {}

  template <typename Gen>
  T operator()(Gen& generator) const {
    const auto width = b-a;

    T retval = generator() % width;
    return retval + a;
  }
};

If you just slap a modulus on it, it biases the distribution towards lower numbers. There's an explanation in the blog post that Carson linked above. So, I set the upper bound at an integer number of widths over Gen::min(), then dropped things that fell between that and Gen::max().

Furthermore, Gen::min() is not guaranteed to be zero, so that's important.

I don't believe this has a meaningful bias in distribution towards lower numbers. Modulus operations are the backbone of integer-based cryptography, so I highly doubt that this is an unsolvable issue.

Here is a short test I did in python with 100M samples of 8 random bytes modulo 100. Python uses mersenne twister for random().

For a small generator, I see how this could be a problem. Consider a generator that only generates a value between 0 and 255. Then a modulus operation to generate a proportionally large range (say 100), we will see a bias, since 255 % 100 = 55, so we will see a bimodal uniform distribution, with the bias difference beginning at 55.
See here.

That's not the right way to think about this or to evaluate the claim.

Consider the following scenario:

• The generator yields integer values in [0,1,2] with equal probability
• The distribution maps to [0,1] with equal probability

Before proceeding, I note that this scenario is entirely within the specification. The values are smaller than we might consider common, but they are legal values.

If we perform a modulo 2 on the generated values, we will map { [0,2] => 0, [1] => 1 }. This is far from a uniform distribution. If instead we discard all 2s, we will map { [0] => 0, [1] => 1 }. This will hold true for any instance where the range of the generator is not an integer multiple of the range of the distribution. Since the values a and b are given at runtime, we cannot assume anything about them (beyond the specification).

We also cannot evaluate this claim with your python script. What you have presented is but one realization of the probability distribution. Your modulus will produce the values of 0-15 with a probability 16/184467440737095516 ~= 8.67e-17 higher than values 16-99. Your run of 100million evaluations simply cannot illustrate this bias above the noise. You would need at least 10 orders of magnitude more evaluations to illustrate what I'm describing. None of this, however, denies that the bias is in fact present.

Edit: your edit does recognize the problem. We have to recognize that this bias does not go away with scale.

What kind of performance overhead to the randomness would we experience? Mainly, how many resamples?
I guess performance is worst when the bias is worst, mainly when the width is just over half of the genwidth? Something like a 2x overhead on the average worst case? I guess that is acceptable, as long as our generators remain over 2x the desired field width then I don't see this being a major problem.
I guess this is also technically a hard-to-predict branch, which may have additional performance considerations.

Here is data showing as much.
I am sure there's a whole relation here with the distribution of relative prime numbers, factors, etc...

After looking at a bunch of sample implementations, I've written a custom implementation of uniform_int_distribution that should be a drop-in replacement to the one in <random> while being platform-agnostic.

I like tossing out low values rather than high values. That's clever. We should put plenty of tests on this. Let's test at least the degenerate [0,1,2] => [0,1] case the blog above describes. I might also be curious to see benchmarks for various ratios of (range_g % range_d)/range_g, to address the concerns Maccoy raises. He's probably right that there are performance pessimizations in this implementation if that ratio gets too close to 1/2. But, if benchmarks show that processors can parallelize the wrong-path speculation, that would be good.

Okay, I pushed some tests for champsim::uniform_int_distribution. Next step is to test champsim::shuffle and expand the test suite further if we think it's necessary. I'd also like to test VirtualMemory::shuffle_pages, but that may be tricky.