Тестирование производительности ГСЧ

Как-то раз, на очередном этапе оптимизации в текущем проекте в список hot methods вырвался Random.nextDouble(). Его загнали назад в хвост, но осадочек остался, так что последние пару недель в свободное время я гоняю бенчмарки различных реализаций генераторов случайных чисел. В соревновании участвуют заведомый аутсайдер java.util.Random, плюс два хорошиста из cern.jet.random -- вихрь Мерсена и DRand -- наверное, самый короткий из возможных на джаве (next = current * 0x278DDE6D).

Гоняю я их в многопоточном варианте -- ибо у нас-то симулятор далеко не однопоточный. Стандартный генератор, поскольку он thread-safe (использует AtomicLong) в двух режимах: shared (один на все потоки) и exclusive (на каждый поток свой генератор). Не то, чтобы я собирался в продакшене использовать Random в shared режиме, нет, упаси боже -- но как еще одна реперная точка (наряду с "dummy" ГСЧ) вполне подойдет. Остальные два участника не потокобезопасны, поэтому для них используется только вариант exclusive.

На днях бенчи досчитались, и обнаружились интересные вещи:

В однопоточном варианте все довольно предсказуемо: стандартный ГСЧ немного (на 10%) опережает вихрь Мерсена (при несопоставимом качестве), Drand всех рвет на части, опережая обоих в 3 раза.

jdk-shared с ростом количества потоков быстро деградирует -- на 16 потоках он почти в 60 раз медленнее, чем на одном -- тоже ничего удивительного.

А вот с остальными по мере увеличения количества потоков начинают твориться веселые вещи. И DRand и jdk-exclusive замедлились почти в 10 раз при переходе от 1 потока к 16. Ну замедление при переходе от 8 к 16 еще понятно -- реальных-то ядер на сервере только 8, 16 это с учетом гипертрединга. Но и на 8 потоках замедление почти в 5 раз. False sharing в действии -- генераторы создаются в цикле, каждый из них занимает явно меньше, чем cache-line, так что очевидно они ложатся на одну строку кэша, что не очень здорово.

Косвенно гипотеза подтверждается тем, что вихрь Мерсена (который внутри себя выделяет еще и массив на int[624]) скалировался до 8 ядер почти идеально, и только при переходе к 16 немного просел.

Проверим -- введем поля:

//было new DRand( 1 ); 
new DRand( 1 ){
                    private final long pad0 = 0;
                    private final long pad1 = 0;
                    private final long pad2 = 0;
                    private final long pad3 = 0;
                    private final long pad4 = 0;
                    private final long pad5 = 0;
                    private final long pad6 = 0;
                    private final long pad7 = 0;
                    private final long pad8 = 0;
                    private final long pad9 = 0;
                };

-- ну и с Random такое же. Результаты заметно улучшаются -- и DRand и Mersenne начинают масштабироваться практически идеально вплоть до 8 потоков, и деградируют лишь на 16, что объяснимо.

Остается неразгаданной ситуация с jdk-exclusive. Во-первых производительность продолжает сильно деградировать -- примерно в 3.5 раза с 1 до 8 потоков. Причины этого поведения мне пока непонятны. Плюс здесь еще самый большой статистический разброс результатов: относительная погрешность достигает 50%, отдельные измерения с одинаковыми параметрами дают, в разных заходах, результаты, различающиеся раза в 3. В раздумьях.

P.S. Код здесь