Если известно что запрошено будет не более скажем миллиона чисел
Вы шутите? Всего лишь миллион? Колоду из скольки карт можно перетасовать таким "генератором"?
Не шучу, Вы спросили, я прикинул, мало ли какие задачи есть. В общем случае генератор выходит слишком требовательным, в основном к памяти (линейно по номеру итерации). Можно ли требования уменьшить более чем вдвое я не вижу как, но тут математики могут подсказать, всё же эти автоматы хорошо исследованы.
(Вопрос про исходник)
Вычисление одной итерации требует одного чтения памяти, одной записи памяти, двух сдвигов, двух логических операций - итого в потоке в среднем по такту (все указанные операции могут выполниться параллельно) на каждое слово процессора.
Можно подробнее, пожалуйста?
А лучше бы, прямо работающий пример.
Прямо сразу работающий и сразу за такт процессора на слово? Тяжеловато, из-за учёта граничных эффектов между словами и запуска-останова процесса. Внутренний цикл должен выглядеть примерно так (пишу из головы, без проверки):
mov EDI,0 ;Предыдущее число справа
mov ECX,8000 ;Сколько чисел обрабатывать
mov ESI,offset buf ;Буфер состояния, выравнивание на правый единичный бит
;Порты Такты (Latency/Throughput)
.iter: mov EAX,[ESI] ;23 3/0.5
mov EDX,EAX ;0156 1/0.25 Часто =0
mov EBX,EAX ;0156 1/0.25 Часто =0
shld EAX,EDI,2 ;1 3/1
shld EDX,EDI,1 ;1 3/1
or EAX,EDX ;0156 1/0.25
xor EAX,EBX ;0156 1/0.25
mov [ESI],EAX ;4 -/1
mov EDI,EBX ;0156 1/0.25 Часто =0
add ESI,4 ;0156 1/0.25
sub ECX,1 ;0156 1/0.25
jnz .iter ;06 1/0.5 Часто склеивается с предыдущей командой
Итого если
mov и
jnz не считать, то получается 1 операция в 2+3 и 4 порты, 2 операции в 1 порт, 4 операции в любой из 0156 портов. В сумме самое долгое по 1 порту, два такта, тогда 4-5 (с
jnz) операций в порты 056 вполне раскладываются в два такта.
Итого: два такта на слово, 16 битов на такт. Для x64 будет ровно то же, но 64 битные регистры и соответственно 32 бита на такт.
В один такт не уложился, оказалось забыл что
shld не параллелится, да ещё и про add/sub для цикла не подумал. Ну два такта тоже неплохо.
На AVX переписывать лень, там добавится перестановка 64-бит слов (3/1 тактов, но в параллель), плюс нет двойных сдвигов, придётся добавлять два сдвига и пару-тройку and/or, ну и портов запуска меньше, лишь три. Ориентировочно 4-5 тактов, но уже на слово 256 битов.
PS. Все цифры для имеющегося у меня Haswell. Для более старых цифры могут быть хуже (и мне не интересны), для более новых лучше (но мне не на чем проверить и использовать), надо смотреть конкретно.
