Неслучайные неслучайности

При тестировании серверной геометрии мы столкнулись с курьезной проблемой - время формирования случайного вектора было дольше времени расчета видимости этого вектора. Сложив это с постоянными репортами клиентов о сбоях генератора псевдослучайных чисел (повторах при многопоточных вызовах и пр.), я решил изучить этот вопрос поглубже.

Работая в среде Mono для генерации случайных чисел RunServer использует System.Random - есть предпосылки считать, что он базируется на /dev/random, но под .Net и Windows используется другой подход - обращение к системной функции RtlGenRandom, известной также под именем SystemFunction036.
Данная функция должна была гарантировать равномерное распределение случайных чисел, отсутствие повторений, многопоточную безопасность. Практика показала, что это не совсем так, а время вызова функции сравнительно велико.
Как оказалось, проблема была не в самой функции, а в ее использовании: при каждом обращении к классу Utility.Random вызывалась функция с временным буфером 4 байта, в то время как функция рассчитана на генерацию страницы cлучайных чисел. Повторения при многопоточном использовании могут быть вызываны различными внутренними кешированиями.
Я думал было отказаться от этой функции, но решил дать функции еще один шанс - вместо вызова для буфера в 4 байта, я сделал генерацию случайного блока в несколько килобайт и его кеширование. Конечно же, при этом встал вопрос синхронизации: боступ к пулу чисел должен быть последовательным, но использовать блокировки при каждом запросе - не очень выгодно. Вопрос был решен с помощью Interlocked операций:

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];
}

В приведенном коде RtlGenRandom заполняет буфер в 4096 байт, который для удобства хранится как массив int []. Использование Interlocked.Increment гарантирует, что пул будет обновляться один раз в 1024 вызова и извлечение одного и того же числа два раза возможно лишь при 1024 конкурирующих потоках.
Возможна ситуация, когда в одном потоке пул еще обновляется, а в другом идет вызов rand(). Если пул уже был заполнен, то ничего страшного в этом нет - будет извлечено число из нового пула (если заполнение буфера идет последовательно), либо закешированное значение из старого пула. Если первое заполнение еще не произошло, то в муле будут нули, потому целесообразно в статическом конструкторе класса единожды вызывать rand(), чтобы заполнить пул до его использования.

За счет подобной оптимизации в сотни раз сократилось время вызова метода rand(), была обеспечена многопоточная безопасность и равномерность распределения случайных чисел. Возможно, есть и более быстрые реализации, например, комбинация Interlocked операций с математическими, но в случае с RtlGenRandom можно не опасаться частых повторений одного и того же числа, частичного диапазона и других болезней генераторов псевдослучайных чисел.

Update: Обнаружен гадкий баг. Странно, что никто из читателей не заметил. Мы увеличиваем 32-битный инт и когда он дойдет до максимума, начнутся отрицательные значения. Их остаток от деления тоже отрицателен и нам грозит обращение по неверному адресу. Самый простой способ - не остаток от деления использовать, а маску. Например так:

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

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