JEP 356: Enhanced Pseudo-Random Number Generators

Аннотация

Предоставить новые типы интерфейсов и реализации генераторов псевдослучайных чисел (PRNG), в том числе PRNG с поддержкой прыжков (jumpable) и дополнительный класс разделяемых (splittable) алгоритмов PRNG (LXM).

Цели

• Упростить взаимозаменяемое использование различных алгоритмов PRNG в приложениях.
• Улучшить поддержку программирования на основе потоков (streams) за счёт потоков объектов PRNG.
• Устранить дублирование кода в существующих классах PRNG.
• Тщательно сохранить существующее поведение класса java.util.Random.

Что не является целью

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

Критерии успеха

Выходные данные новых алгоритмов LXM проходят существующие широко известные наборы тестов TestU01 и PractRand.

• Pierre L'Ecuyer and Richard Simard. TestU01: A C Library for Empirical Testing of Random Number Generators. ACM Transactions on Mathematical Software 33, 4 (август 2007), статья 22. ISSN 0098-3500. http://doi.acm.org/10.1145/1268776.1268777

• Richard Simard. TestU01, версия 1.2.3 (август 2009). http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

• Pierre L'Ecuyer and Richard Simard. TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators: User's guide, compact version. Département d'Informatique et de Recherche Opérationnelle, Univerité de Montréal, май 2013. http://www.iro.umontreal.ca/~simardr/testu01/guideshorttestu01.pdf

• Chris Doty-Humphrey. PractRand, версия 0.90. Июль 2014. http://pracrand.sourceforge.net [Это не опечатка. Программа называется «PractRand», а проект на SourceForge называется «pracrand».]

Алгоритмы PRNG с поддержкой прыжков (jumpable) и дальних прыжков (leapable) проходят тесты, проверяющие коммутативность определённых операций.

Мотивация

Мы выделяем пять направлений для улучшения в области генераторов псевдослучайных чисел в Java:

• Унаследованные классы PRNG Random, ThreadLocalRandom и SplittableRandom трудно заменить в приложении каким-либо другим алгоритмом, несмотря на то что все они поддерживают практически один и тот же набор методов. Например, если приложение использует экземпляры класса Random, в нём обязательно будут объявлены переменные типа Random, которые не могут хранить экземпляры класса SplittableRandom; чтобы перевести приложение на SplittableRandom, пришлось бы менять тип каждой переменной (включая параметры методов), в которой хранится объект PRNG. Единственное исключение — ThreadLocalRandom является подклассом Random исключительно для того, чтобы переменные типа Random могли хранить экземпляры ThreadLocalRandom, однако ThreadLocalRandom переопределяет почти все методы Random. Интерфейсы легко решают эту проблему.

• Унаследованные классы Random, ThreadLocalRandom и SplittableRandom поддерживают такие методы, как nextDouble() и nextBoolean(), а также методы, создающие потоки, например ints() и longs(), но у них полностью независимые и почти идентичные, словно скопированные, реализации. Рефакторинг этого кода упростил бы его сопровождение, а документация, кроме того, значительно упростила бы третьим сторонам создание новых классов PRNG, которые также поддерживают тот же полный набор методов.

• В 2016 году тестирование выявило две новые слабости алгоритма, используемого классом SplittableRandom. С одной стороны, этих слабостей можно избежать сравнительно небольшой доработкой. С другой стороны, был также открыт новый класс разделяемых алгоритмов PRNG (LXM), которые почти так же быстры, ещё проще в реализации и, по-видимому, полностью свободны от трёх классов слабостей, которым подвержен SplittableRandom.

• Возможность получить от PRNG поток объектов PRNG значительно упрощает запись некоторых видов кода с помощью потоковых методов.

• В литературе описано множество алгоритмов PRNG, которые не являются разделяемыми, но поддерживают прыжки (а возможно, и дальние прыжки, то есть способны выполнять как очень длинные, так и обычные прыжки); это свойство сильно отличается от разделения, но тем не менее тоже хорошо подходит для поддержки потоков объектов PRNG. Раньше воспользоваться этим свойством в Java было трудно. Примеры алгоритмов PRNG с поддержкой прыжков — Xoshiro256** и Xoroshiro128+.

  • Xoshiro256** и Xoroshiro128+: http://xoshiro.di.unimi.it

Описание

Мы предоставляем новый интерфейс RandomGenerator, который задаёт единый API для всех существующих и новых PRNG. RandomGenerators предоставляют методы ints, longs, doubles, nextBoolean, nextInt, nextLong, nextDouble и nextFloat со всеми их текущими вариантами параметров.

Мы предоставляем четыре новых специализированных интерфейса RandomGenerator:

• SplittableRandomGenerator расширяет RandomGenerator и также предоставляет
  методы split и splits. Разделяемость позволяет пользователю породить из существующего RandomGenerator новый RandomGenerator, который, как правило, будет выдавать статистически независимые результаты.

• JumpableRandomGenerator расширяетRandomGenerator и также предоставляет
  методы jump и jumps. Поддержка прыжков позволяет пользователю перескочить вперёд на умеренное количество выборок.

• LeapableRandomGenerator расширяет RandomGenerator и также предоставляет
  методы leap и leaps. Поддержка дальних прыжков позволяет пользователю перескочить вперёд на большое количество выборок.

• ArbitrarilyJumpableRandomGenerator расширяет LeapableRandomGenerator и также предоставляет дополнительные варианты jump и jumps, позволяющие задать произвольное расстояние прыжка.

Мы предоставляем новый класс RandomGeneratorFactory, который используется для поиска и создания экземпляров реализаций RandomGenerator. RandomGeneratorFactory использует API ServiceLoader.Provider для регистрации реализаций RandomGenerator.

Мы провели рефакторинг Random, ThreadLocalRandom и SplittableRandom, чтобы они совместно использовали бо́льшую часть кода реализации и, кроме того, чтобы этот код можно было повторно использовать и в других алгоритмах. В результате рефакторинга появляются базовые непубличные абстрактные классы AbstractRandomGenerator, AbstractSplittableRandomGenerator, AbstractJumpableRandomGenerator, AbstractLeapableRandomGenerator и AbstractArbitrarilyJumpableRandomGenerator, каждый из которых предоставляет только реализации методов nextInt(), nextLong() и (если применимо) либо split(), либо jump(), либо jump() и leap(), либо jump(distance). После этого рефакторинга Random, ThreadLocalRandom и SplittableRandom наследуют интерфейс RandomGenerator. Обратите внимание: поскольку SecureRandom является подклассом Random, все экземпляры SecureRandom также автоматически поддерживают интерфейс RandomGenerator, и переписывать класс SecureRandom или какие-либо связанные с ним механизмы реализации не нужно.

Мы также добавили базовые непубличные классы, расширяющие AbstractSplittableRandomGenerator (и, следовательно, реализующие SplittableRandomGenerator и RandomGenerator), для поддержки шести конкретных представителей семейства алгоритмов PRNG LXM:

• L32X64MixRandom
• L32X64StarStarRandom
• L64X128MixRandom
• L64X128StarStarRandom
• L64X256MixRandom
• L64X1024MixRandom
• L128X128MixRandom
• L128X256MixRandom
• L128X1024MixRandom

Структура центрального метода nextLong (или nextInt) алгоритма LXM следует предложению Sebastiano Vigna, сделанному в декабре 2017 года: использование одного LCG-подгенератора и одного подгенератора на основе xor (вместо двух LCG-подгенераторов) обеспечит более длинный период, лучшую равнораспределённость, масштабируемость и более высокое качество. Каждая из приведённых здесь конкретных реализаций сочетает один из лучших известных на сегодня генераторов на основе xor (xoroshiro или xoshiro, описанных Blackman и Vigna в работе «Scrambled Linear Pseudorandom Number Generators», ACM Trans. Math. Softw., 2021) с LCG, использующим один из лучших известных на сегодня множителей (найденных Steele и Vigna в 2019 году при поиске более удачных множителей), а затем применяет функцию перемешивания, предложенную Doug Lea. Тестирование подтвердило, что по качеству алгоритм LXM намного превосходит алгоритм SplitMix (2014), используемый в SplittableRandom.

Мы также предоставляем реализации следующих широко используемых алгоритмов PRNG:

• Xoshiro256PlusPlus
• Xoroshiro128PlusPlus

Упомянутые выше непубличные абстрактные реализации в будущем могут быть предоставлены как часть SPI для разработчиков реализаций генераторов случайных чисел.

Этот набор алгоритмов даёт Java-программистам разумный диапазон компромиссов между объёмом памяти, временем, качеством и совместимостью с другими языками.

Альтернативы

Мы рассматривали вариант просто добавить новые интерфейсы, оставив реализации Random, ThreadLocalRandom и SplittableRandom без изменений. Это помогло бы сделать объекты PRNG более взаимозаменяемыми, но никак не упростило бы их реализацию.

Мы рассматривали вариант рефакторинга Random, ThreadLocalRandom и SplittableRandom без изменения их функциональности и без добавления новых интерфейсов. Мы считаем, что это уменьшило бы их общее потребление памяти, но никак не упростило бы реализацию или использование будущих алгоритмов PRNG.

Тестирование

• Все существующие тесты для Random, ThreadLocalRandom и SplittableRandom
  следует продолжать использовать.

• Новый тест, вероятно, для однократного применения: выходные данные переработанных
  версий Random, ThreadLocalRandom и SplittableRandom (до
  устранения двух недавно обнаруженных слабостей) следует выборочно сверить с существующими реализациями (JDK 8), чтобы убедиться, что их поведение осталось
  неизменным.

• Новый тест, вероятно, для однократного применения: выходные данные алгоритмов LXM
  следует выборочно сверить с версиями на C, использованными для проверки
  качества с помощью TestU01 и PractRand.

• Новый тест, который станет постоянной частью набора тестов: методы jump() и
  leap() следует протестировать, чтобы убедиться, что они действительно перемещаются по циклу состояний на заявленное расстояние. Например, начиная с любого конкретного начального состояния, последовательность операций nextLong(); jump() должна оставлять
  генератор в том же состоянии, что и последовательность операций jump(); nextLong().

Риски и допущения

Мы считаем, что это проект средней сложности и риски минимальны. Вероятно,
основной объём работы пришёлся на составление спецификации, а второй по объёму — на тестирование.

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