Non-Random Randomness

Alex Harbuzenko · 17 November 2009 · .Net, C#, Interlocked, random

While testing server-side geometry, we ran into a curious problem — generating a random vector took longer than computing that vector’s visibility. Combine that with a steady stream of client reports about pseudo-random number generator glitches (repeats under concurrent calls, and so on), and I decided to dig into this more deeply.

When running under Mono, RunServer uses System.Random to generate random numbers — there’s reason to believe it’s based on /dev/random, but under .Net on Windows a different approach is used — a call to the system function RtlGenRandom, also known as SystemFunction036.
This function was supposed to guarantee a uniform distribution of random numbers, no repeats, and thread safety. In practice it turned out that wasn’t quite the case, and the call itself was relatively slow.
As it turned out, the problem wasn’t the function itself but how it was being used: every call to the Utility.Random class invoked the function with a temporary 4-byte buffer, even though the function is designed to generate a whole page of random numbers at once. The repeats under concurrent use could be caused by various internal caching layers.
I considered dropping the function entirely, but decided to give it one more chance — instead of calling it for a 4-byte buffer, I generated and cached a random block several kilobytes in size. That, of course, raised a synchronization question: access to the number pool needs to be sequential, but using a lock on every request isn’t great for performance. I solved it using Interlocked operations:

const int PoolLength = 1024;
static readonly int[] s_randomPool = new int[PoolLength];
static int s_poolPosition;

static int rand()
{
       int pos = Interlocked.Increment(ref s_poolPosition) % PoolLength;

       if (pos == 0)
               RtlGenRandom(s_randomPool, PoolLength * 4);

       return s_randomPool[pos];
}

In the code above, RtlGenRandom fills a 4096-byte buffer, which for convenience is stored as an int [] array. Using Interlocked.Increment guarantees that the pool gets refreshed once every 1024 calls, and pulling the same number twice is only possible with 1024 threads racing simultaneously.
There’s a possible scenario where the pool is still being refreshed in one thread while another thread calls rand(). If the pool had already been filled, that’s not a problem — you either get a number from the new pool (if the buffer fill happens sequentially) or a cached value from the old pool. If the first fill hasn’t happened yet, the pool will contain zeros, so it makes sense to call rand() once in the class’s static constructor to fill the pool before it’s used.

Thanks to this optimization, the time to call the rand() method dropped by a couple of orders of magnitude, thread safety was ensured, and the random number distribution stayed uniform. There are probably faster implementations out there, for example combining Interlocked operations with arithmetic tricks, but with RtlGenRandom you don’t have to worry about frequent repeats of the same number, partial ranges, and the other usual ailments of pseudo-random number generators.

Update: Found a nasty bug. Odd that none of the readers caught it. We’re incrementing a 32-bit int, and once it hits the maximum it starts going negative. The modulo of a negative number is also negative, which risks an out-of-bounds access. The simplest fix is to use a mask instead of a modulo. Like this:

const intPoolLength = 0x400;
const intPoolMask = PoolLength - 1;
...

int pos = Interlocked.Increment(ref s_poolPosition) & PoolMask;