А чё, так можно было? Опечатка в исходниках .NET, которой больше 20 лет

В System.Random кто-то двадцать лет назад написал 21 вместо 31. Опечатку заметили, разобрали и оставили как есть — исправить, и new Random(42) начнёт выдавать другие числа.

А ещё new Random() и new Random(42) — вообще разные генераторы. На NextInt64 один медленнее другого в 10 раз. 

Все машины x64

Рантаймы .NET 8, 9 и 10 — все три в одном запуске BenchmarkDotNet 0.15.8.

1. Две цифры, которые перепутали

Исходник

Алгоритм взят у Кнута: там генератор берёт два числа из массива — 24-е и 55-е с конца — и вычитает одно из другого. Заполняется массив шагом 31. В исходниках .NET шаг 21:

int ii = 0;
for (int i = 1; i < 55; i++)
{
    // The range [1..55] is special (Knuth)
    if ((ii += 21) >= 55)     // здесь должно быть 31
    {
        ii -= 55;
    }
 
    seedArray[ii] = mk;
}

Рядом, строкой выше, ещё одна примечательная константа:

int mj = 161803398 - subtraction;   // magic number based on Phi

Это золотое сечение, умноженное на 100 млн.

Причина

Код переносили не из книги Кнута, а из «Численных рецептов»: в issue указана страница 283 второго издания и отмечено, что совпадают даже имена переменных. В .NET Framework это было написано комментарием прямо над алгоритмом. В книге 31, в .NET получилось 21. Оттуда же взято и 161803398 — в книге эта константа названа MSEED.

Из-за этого массив заполняется не так, как у Кнута, и свойства его генератора на такую последовательность не распространяются. Ошибку нашёл разработчик, разобрав библиотеку декомпилятором, и открыл issue. В Microsoft ответили: чинить не будем, иначе у всех, кто задаёт начальное значение, поменяются числа.

Ссылка на этот issue есть в исходниках, в комментарии к алгоритму.

Где легко ошибиться

Решить, что из-за опечатки числа перестали быть равномерными. Отчёт из проекта делит диапазон на десять равных частей и считает, сколько чисел попало в каждую, плюс корреляцию соседних значений. Отклонений нет:

  генератор            отклонение от среднего   связь соседних
 
  new Random()                       0.118 %         -0.000359
  new Random(42)                     0.219 %          0.000427
  Random.Shared                      0.254 %          0.000391

Опечатка сказывается на длине периода, а его проверка требует отдельного набора тестов вроде TestU01.

2. Два разных генератора под одним именем

Исходник

Вычислениями занимается не Random, а одна из двух реализаций внутри него. Выбор алгоритма идет в конструкторе и зависит от того, задано начальное значение или нет.

public Random()
{
    _impl = new XoshiroImpl();
}

public Random(int seed)
{
    _impl = new Net5CompatSeedImpl(seed);
}

Что выводит отчёт

  как создан                     реализация
 
  new Random()                    XoshiroImpl
  new Random(42)                  Net5CompatSeedImpl
  new Random(0)                   Net5CompatSeedImpl
  new Random(int.MaxValue)        Net5CompatSeedImpl
  Random.Shared                   реализация не задана

Без начального значения используется XoshiroImpl — алгоритм, добавленный в .NET 6. С начальным значением — Net5CompatSeedImpl, тот самый, с опечаткой. Random.Shared работает иначе: вместо одной реализации на объект он создаёт отдельный XoshiroImpl для каждого потока.

Что показывает замер

Наносекунды на вызов Next, .NET 10

На обычном Next разница невелика: 1,14 раза. Random.Shared отстаёт от обоих, хотя алгоритм у него тот же: перед каждым вызовом он обращается к хранилищу потока за своим экземпляром. Криптографический генератор медленнее в 22–40 раз.

Причина

XoshiroImpl выдаёт 64 бита за один шаг. Net5CompatSeedImpl умеет только 31 бит, поэтому на одно 64-битное число уходит три вызова вместо одного. Разница не в три раза, а в десять: один вызов Net5CompatSeedImpl уже медленнее, а к трём вызовам добавляются сдвиги для сборки результата.

Где легко ошибиться

Померить только Next и решить, что разницы нет. На других методах она совсем другая:

Наносекунды, без начального значения и с ним, .NET 10 

На NextInt64 разрыв 8,6–10,4 раза, на NextBytes с буфером в килобайт — 13,0–17,5 раза.

У NextDouble скорость одинаковая, потому что оба алгоритма получают дробное число одним умножением. Разница между ними в количестве бит за шаг, а для NextDouble обоим достаточно одного шага.

3. Создание генератора

Исходник

// с начальным значением: цикл на 56 чисел
public Net5CompatSeedImpl(int seed)
{
    _prng = new CompatPrng(seed);
}
 
// без него: четыре числа от операционной системы
public unsafe XoshiroImpl()
{
    ulong* ptr = stackalloc ulong[4];
    do
    {
        Interop.GetRandomBytes((byte*)ptr, 4 * sizeof(ulong));
        _s0 = ptr[0];
        _s1 = ptr[1];
        _s2 = ptr[2];
        _s3 = ptr[3];
    }
    while ((_s0 | _s1 | _s2 | _s3) == 0);
}

new Random(42) прогоняет цикл на 56 чисел — тот самый, с опечаткой. new Random() запрашивает у операционной системы четыре случайных числа. Цикл нужен на редкий случай: если все четыре числа окажутся нулями, XoshiroImpl будет выдавать только нули, поэтому запрос повторяется.

Что показывает замер

Наносекунды, .NET 10. Памяти 72 байта против 304 

Создание с начальным значением занимает 240,64 наносекунды против 97,56 и требует 304 байта против 72. На трёх машинах картина одна и та же.

Где легко ошибиться

Создавать new Random(42) внутри цикла. На каждой итерации это 304 байта в куче и 56 чисел, которые считаются с нуля.

4. Числа предсказываются за 24 миллисекунды

Исходник

Net5CompatSeedImpl хранит 55 чисел. Их хватает, чтобы подобрать начальное значение перебором:

for (int seed = 0; seed < 100_000; seed++)
{
    Random guess = new(seed);
    if (guess.Next() != seen[0])
    {
        continue;
    }
 
    // сверяем остальные
}

Что выводит отчёт

  начальное значение подобрано: 12345, за 24 мс
 
  программа выдаст:  1153550655, 1527729513, 144439007
  предсказано:       1153550655, 1527729513, 144439007
  совпало: True 

Трёх чисел уже достаточно: перебрал миллион вариантов, подошёл один.

Причина

В примере перебор идёт до 100 000, потому что начальное значение взято небольшое. В худшем случае перебирать нужно все значения знакового int — 4 294 967 296 вариантов. Скорость перебора — миллионы в секунду, на весь диапазон уйдёт несколько минут. А если начальное значение взяли от времени, счёт идёт на тысячи.

Где легко ошибиться

Сгенерировать через Random токен сброса пароля, код подтверждения или номер заказа. Перебор займёт от секунд до нескольких минут — смотря откуда взято начальное значение.

На этот случай в .NET есть правило CA5394: System.Random не годится там, где от значения зависит безопасность. Но по умолчанию правило выключено и в .NET 10, так что предупреждения при сборке не будет. Включается строкой в .editorconfig:

dotnet_diagnostic.CA5394.severity = warning

Границы замеров

Все замеры сняты на x64 под Windows, на .NET 8, 9 и 10.

Генераторы создаются заранее и передаются аргументом: их создание замеряется отдельно. У всех измеряемых методов запрещено встраивание.

В сверке дробные числа сравниваются через ==, и это не ошибка: проверяется совпадение двух последовательностей, а не близость значений. Оба генератора выполняют одни и те же операции, поэтому результаты совпадают.

Отчёт с распределением и корреляцией соседних чисел период не проверяет. Он показывает ровно одно: на таких проверках разницы нет.

По документации Random не рассчитан на вызовы из разных потоков. При тестах расхождений не найдено: 8 и 32 потока по миллиону вызовов дали ту же сумму, что и один поток. Не стоит забывать, что отсутствие расхождений в одном прогоне ничего не гарантирует.

Код из статьи

• RandomProof — замеры, отчёты и выгрузки с трёх машин

Ссылки

• Обсуждение опечатки в dotnet/runtime

• Алгоритм, оставленный ради совместимости

• Число на основе золотого сечения

• Современный алгоритм

• CA5394: не применять Random там, где важна безопасность

• System.Random

Всем удачи и до новых встреч!

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.