More clearly define randomness in timing_array.h

[ssbr]

This is a Linear Congruential Generator. See e.g. https://en.cppreference.com/w/cpp/numeric/random/linear_congruential_engine and compare the formula ;) i.e. we're basically reimplementing std::linear_congruential_engine<113, 100, 256>

This is an important observation, because it implies further restrictions on the number 113 -- it shouldn't just be odd, but in fact prime (or at least co-prime with the modulus), and 112 needs to satisfy several tests (in particular, divisible by 2 and 4, but ideally not 8 or 16 or so on). This also informs us how we can extend this to arbitrary sizes rather than 256.

The most obvious next step, if we want to reuse this for non-256-sized arrays, is to make it a PCG over the next-biggest sized power of 2 (and step the PCG until an in-range value is found). Alternatively, any other PRNG that supports O(1) seek and can have its period set arbitrarily small would suffice.

I'm not sure what these are called in computer science -- in math, it's just called a permutation. As in, I want a permutation over the integers 0..n -- a bijection from 0..n to 0..n. But if I google for permutation functions, I get algorithms for shuffling vectors instead of int->int permutations. :/

[ssbr]

BTW if you want someone else like Matt to review this, I understand, but we'll need to talk about mechanically how to do this...

[sivachandra]

I don't know much, but just saying - IIUC, you looking for pairs (x, y) with x and y picked randomly from {1, 2, ... , n}, correct? If so, would this work?

std::vector<int> a, b; 
// populate a with {1, 2, ... , n}
// shuffle a
// populate b with {1, 2, ... , n}
// shuffle b
std::vector<std::pair<int, int>> pairs;
for (size_t i = 0; i < a.size(); ++i) {
  pairs[i].first = a[i];
  pairs[i].second = b[i];
}

[ssbr]

I don't know much, but just saying - IIUC, you looking for pairs (x, y) with x and y picked randomly from {1, 2, ... , n}, correct? If so, would this work?

The issue (as I understand it) is that the shuffling has to take O(1) memory so as to avoid creating cache pressure that would interfere with our measurements, so we can't just shuffle a list of indexes or similar. Instead, we need a permutation function f : int -> int which returns a "randomish" invertible mapping from 0..256 to itself, and can be computed in O(1) space and time. In this case, we're using an LCG for that, as it requires no state and only a little in the way of computation. Other options include a PCG or an ICG, I think -- and those would hopefully be less fragile and sensitive to parameters than an LCG.

(We also can't shuffle the underlying array, because objective is to randomize the order in which we access cache lines, not to randomize the order of accessed values.)