Почему псевдослучайные биты не кэшируются, когда используется только один бит для «рисования» (например, вызов nextBoolean)?

Question

Я иду через source code for Math.Random и я заметил, что исходный код для nextBoolean()

public boolean nextBoolean() { 
    return next(1) != 0; 
} 

требует нового розыгрыша псевдослучайных битов, через next(int bits), которые «перебирает» ЛК-ПСЧ к следующему состоянию, т.е. «рисует» целый набор новых бит, хотя только один бит используется в nextBoolean. Это фактически означает, что остальные биты (точнее, 47) в значительной степени теряются в этой конкретной итерации.

Я посмотрел на другой PRNG, который, похоже, делает практически то же самое, хотя базовый генератор отличается. Поскольку несколько бит из одной и той же итерации используются для других вызовов методов (таких как nextInt(), nextLong(), ...), а последовательные биты считаются «независимыми» друг от друга.

Так что мой вопрос: почему только один бит используется из ничьей PRNG, используя nextBoolean()? Должно быть возможно кэшировать, скажем, 16 бит (если нужно использовать биты самого высокого качества), для последовательных вызовов nextBoolean(), я ошибаюсь здесь?

Edit: Что я имею в виду кэширование результатов что-то вроде этого:

private long booleanBits = 0L; 
private int c = Long.SIZE; 
public boolean nextBoolean(){ 
    if(c == 0){ 
     booleanBits = nextLong(); 
     c = Long.SIZE; 
    } 

    boolean b = (booleanBits & 1) != 0; 
    booleanBits >>>= 1; 
    return b; 

    //return (next() & 1) != 0; 
} 

Конечно, это не уверен, и довольно как закомментированного текст, но он заканчивается в 64x меньше тянет. Стоимость 1 int сравнения и 1 операция смены вправо на звонок до nextBoolean(). Я ошибаюсь?

Редактировать2: Хорошо, мне пришлось проверить тайминги, см. Код here. Выходной сигнал выглядит следующим образом:

Uncached time lapse: 13891 
Cached time lapse: 8672 

Testing if the order matters..: 
Cached time lapse: 6751 
Uncached time lapse: 8737 

Который предполагает, что кеширование битов не является вычислительным бременем, а улучшением. Несколько вещей, которые я должен отметить об этом тесте:

1. Я использую пользовательские реализации xorshift * генераторов, которые сильно вдохновлены от Sebastiano Vigna's work on xorshift* generators.

2. Генераторы xorshift * на самом деле намного быстрее, чем собственный генератор Java. Поэтому, если бы я использовал java.util.Random, чтобы нарисовать мои биты, кеширование окажет большее влияние. Или это то, чего я ожидал бы по крайней мере.

3. Применяется однопоточное приложение, поэтому никаких проблем с сифом. Но это, конечно, распространено в обоих условиях.

Answer 1

Conditionals любого вида может быть довольно дорогим (см Why is it faster to process a sorted array than an unsorted array?), и next сам не делает, что гораздо больше операций: Я считаю пять арифметических операции плюс compareAndSet, которая не должно стоить много в одном -решенный контекст.

С помощью compareAndSet выдается еще одна проблема - безопасность потоков - это намного сложнее, если у вас есть две переменные, которые необходимо синхронизировать, например booleanBits и c.Накладные расходы на синхронизацию, поддерживающие синхронизацию для многопоточного использования, почти наверняка превысят стоимость звонка next().