How to generate huge uniform distribution over small range of int in C++ fastly?

Wongboo 0
Viewed 146

Edited: to clarify high dimension meaning

My problem is generating N size array or vector(corresponding to math N dimensional vector), N is huge, more than 10^8, each dimension lies at i.i.d uniform distribution over 1~q(or 0~q-1), where q is very small, q<=2^4. And array must be good statistically. So the basic soltuion is

constexpr auto N = 1000000000UZ;
constexpr auto q = 12;
std::array<std::uint8_t, N> Array{};
std::random_device Device{};
std::mt19937_64 Eng{Device()};
std::uniform_int_distribution<std::uint8_t> Dis(0, q);
std::ranges::generate(Array, [&]{return Dis(Eng);});

But the problem lies in performance, I have several plans to improve it:

  1. because s=q^8<=2^32 so, we use
std::uniform_int_distribution<std::uint8_t> Dis(0, s);

add decompose the result t<q^8 into 8 different t_i<q, but this decomposition is not straightforward, and may have performance flaw in decomposition.

  1. use boost::random::uniform_smallint, but I don't know how much improvement will be? this cann't be used together with method 1.

  2. use multi-threading like openmp or <thread>, but C++ PRNG may not be thread-safe, so it's hard to write to my knowledge.

  3. use other generator such as pcg32 or anything else, but these are not thread-safe as well.

Does anyone offer any suggestions?

boost openmp multithreading random c++
1 Answers

If the running time for a sequential initialization is prohibitive (for instance because it happens multiple times), you can indeed consider doing it in parallel. First of all, the C++ random number generation does not have global state, so you don't have to worry about thread-safety if you create a separate generator per thread.

However, you have to wonder independence. Clearly you can not start them all on the same seed. But picking random seeds is also dangerous. Just imagine what would happen if sucessive generators started on successive values in the sequence.

Here are two approaches:

  1. If you know how many threads there are, say p, first start each generator at the same seed, and then thread t generates t numbers. That's the starting point. Now every time you need a new number, you take p steps! This means that the threads are using interlacing values from the random sequence.
  2. On the other hand, if you know how many iterations i will happen in total, start each thread on the same seed, and then let thread t take t * i steps. So now each thread gets a disjoint block of values from the sequence.

There are other approaches to parallel random number generation, but these are simple solutions based on the standard sequential generator.

Victor Eijkhout0
Related