Рейтинг:2

Эффективный способ выбрать индекс массива, используя, скажем, 64-битное случайное число?

флаг in

Скажем, у меня есть uint64_t rand = <какое-то случайное число>, и массив символов [20] = .... Моя цель - выбрать элемент в множество исходя из содержания ранд.

  1. Один медленный способ - использовать остаток: size_t i = ранд% 20 затем выберите элемент массив [я].
  2. Другой способ, который Наверное быстрее, есть i = ранд/UINT64_MAX * 20. Или, чтобы избежать плавающих операций, его обратная часть 20/(UINT64_MAX/ранд).
  3. Третий способ - использовать случайные биты для перехода к индексу, подобно дереву (но пропускает каждое 5-е число):
size_t total_bytes = 20;
маска size_t = 1;
размер_т я = 0;
в то время как (всего_байтов) {
  если (ранд и маска) i += total_bytes / 2; // переход вправо
  иначе я += 0; // левая ветвь
  маска <<= 1;
  всего_байт /= 2;
}

Есть ли более быстрый способ на обычном оборудовании? Например. ноутбуки/настольные ПК?

Причина, по которой меня это волнует: я реализую функцию вывода жесткого ключа памяти, и в какой-то момент мне нужно выбрать элемент массива на основе содержимого вычисленного зашифрованного текста. Случайное число составляет 64 бита.

Целевой язык — C.

Meir Maor avatar
флаг in
Вы действительно проверили, что% 20 слишком медленный? На современном ПК? Я был бы шокирован.
Maarten Bodewes avatar
флаг in
@caveman Неважно, вопрос немного отличался от ожидаемого. Ночные комментарии....
флаг in
Перекрестно опубликовано: https://stackoverflow.com/questions/68809491/whats-the-fastest-method-in-c-for-converting-a-64bit-random-number-into-a-small с более подробной информацией в комментариях. , включая то, что "20" не является константой.
Рейтинг:4
флаг ng

ранд % 20 генерирует результат в $\{0,1,\ldots,18,19\}$ это Около униформа (при условии ранд является): $\Pr(19)/\Pr(0)=1-1/922337203685477581$. Часто это терпимая предвзятость.

На «ноутбуке/настольном ПК» с современным 64-битным процессором ранд % 20 является достаточно быстрым и обладает важными достоинствами, заключающимися в том, что он правильный, простой и легко адаптируемый. Однако, по крайней мере, часто (см. комментарий) можно быстрее использовать

(ранд-((ранд-(ранд>>2))>>1))>>59

который имеет такое же (оптимальное) соотношение между наименее и наиболее вероятными исходами при использовании только операций сдвига и сложения. Я более уверен, что сгенерированный код является постоянным, что может быть важно в криптографических приложениях. И среднее ближе к $19/2$.

Для интуиции того, как работает эта формула: для любого $x\in\mathbb R$ он держит $(x-(x-x\,2^{-2})\,2^{-1})\,2^{-59}=20\,x\,2^{-64}$, таким образом, мы по существу оцениваем, что выражения (uint64_t)пол(ранд*(20/(UINT64_MAX+1.))) или же (uint64_t)((ранд*(uint128_t)20)>>64) попытаться оценить. Обратите внимание, что для некоторых значений, включая Ранд = 0xCCCCCCCCCCCCCCCC более поздняя формула не совсем совпадает с формулой, которую я предлагаю; однако распределение, достигаемое обоими, является оптимально однородным.

Метод не ограничивается постоянным $м=20$ для размера массива. Он обобщается на любой постоянный $м$ с умеренным весом Хэмминга. Вычисление подходящего количества сдвигов из констант нетривиально. я имею в виду это чудесный ответ (примечание: последний счетчик смен, указанный там, должен быть увеличен на 32 в данном случае) для чего-то, что работает, но не всегда оптимально. У меня нет другой ссылки на метод, который я (повторно?) изобрел для ARM Cortex-M0, где он оказался полезным. На самом деле я только эмпирически нашел формулы для нескольких констант, соответствующих моим потребностям, и Андерс Касеорг берет на себя всю ответственность за то, как систематически генерировать формулы.


Если мы хотим потерять немного единообразия и уверенности в том, что код работает с постоянным временем, мы можем использовать

((ранд>>3)*5)>>59

что проще, скорее всего, быстрее и легче адаптировать к другим константам $м$ скорее, чем $20$: мы пишем $м$ как $г\,2^я$ с $я$ целое число и $г$ желательно нечетное, затем найдите целое число $j$ с $2^{j-1}\le r<2^j$. Мы используем ((ранд>>j)*r)>>(64+i-j). Проблема в том, что нижняя $j$ кусочки ранд не используются, а единообразие результата соответственно снижается (за исключением случаев, когда $м$ является степенью двойки).

Когда $м$ является $2^j$ для некоторого целого числа $j$, мы можем использовать ранд>>(64-j) или же ранд&(м-1). Последнее замечено в тот другой ответ. Эти методы не теряют единообразия, если все биты ранд единообразны и независимы.

Если $м$ изменяется во время выполнения с $м<2^j$ для некоторой известной постоянной $j$, мы можем использовать

((ранд>>j)*m)>>(64-j)

Однако $j$ младшие биты ранд теряются, и это снижает единообразие результата (за исключением случаев, когда $м$ является степенью двойки).


Не по теме:

  • (uint64_t)(пол(ранд*(20/(UINT64_MAX+1.)))) было бы хорошо, если бы не было ошибки округления, но, поскольку они существуют, трудно сказать, может ли это дать 20 для некоторого ввода; также на многих компиляторах он не является оптимально однородным.
  • (uint64_t)((ранд*(uint128_t)20)>>64) математически верен и очень близок к тому, что мы оцениваем, но uint128_t является необязательным и все еще незначительно поддерживаемым компонентом C.
  • Вопросы ранд/UINT64_MAX * 20 выходы в $\{0,20\}$ таким образом непригоден. Проблемы заключаются в округлении деления до целого числа и (независимо) в том, что ранд возможно UINT64_MAX.
  • Вопросы 20/(UINT64_MAX/ранд) выходы в $\{0,1,2,3,4,5,6,10,20\}$ и может вызвать деление на ноль, поэтому не годится. Проблемы заключаются в округлении деления до целого числа и (независимо) в том, что ранд возможно 0.
  • Фрагмент кода вопроса 3 всегда имеет я% 5 != 4 на выходе, таким образом непригоден. Проблема в том, что вывод я построен как 10+5+2+1 с некоторыми удаленными терминами.
Gilles 'SO- stop being evil' avatar
флаг cn
При оптимизации скорости на типичном 64-битном процессоре остаток или деление на константу компилируется в умножение на константу плюс некоторые сдвиги и сложения/вычитания. Аппаратное деление работает медленно, и компиляторы об этом знают (хотя большинство из них не будут выполнять расчеты времени компиляции для 64-битного деления на 32-битном процессоре).Предлагаемые вами сдвиги имеют примерно такое же количество инструкций, но без умножения и одинакового количества обращений к памяти, поэтому ваш метод сдвига, скорее всего, будет быстрее на любом процессоре, за исключением тех, которые предназначены для работы в реальном времени с малым числом циклов. /разд. https://godbolt.org/z/z4PverffY
fgrieu avatar
флаг ng
@Gilles'SO-stopbeingevil': мне не удалось найти соответствующую информацию в [этом беспорядке](https://software.intel.com/content/dam/develop/external/us/en/documents-tps/325462-sdm -vol-1-2abcd-3abcd.pdf), чтобы подтвердить, что упомянутая вами оптимизация по-прежнему стоит того на последних процессорах x64. Обновление: я указал [эти] (https://www.agner.org/optimize/#manuals) полезные ресурсы.
Gilles 'SO- stop being evil' avatar
флаг cn
Я думаю, что вам нужно найти руководство для конкретной модели для этого. Вы ссылаетесь на общий справочник по архитектуре. Справочник по набору инструкций (том 2) был бы более уместным, но даже это только функциональное описание, оно не включает количество циклов (которые не рассказывают полную историю производительности, но для этого простого случая нет ветвления или параллелизма поэтому я думаю, что добавление количества циклов приведет к значимому сравнению).
caveman avatar
флаг in
Стоит ли обобщать это решение сдвига на любое число, отличное от 20, чтобы добиться меньшего количества циклов, чем при использовании подхода `%`? Потому что 20 — это не константа, а просто пример, который я выбрал.
fgrieu avatar
флаг ng
@caveman: теперь ответ поясняет, что да, мы можем распространиться на другие константы. [Это] (https://tinyurl.com/unicst) дает формулы для всех констант до 3 десятичных цифр (но не забудьте добавить 32 к последнему счету сдвига). Опять же, эта оптимизация имеет смысл только в том случае, если оператор `%` работает медленно, а на современных ноутбуках/настольных ПК этого не произойдет.
Gilles 'SO- stop being evil' avatar
флаг cn
@caveman Я не эксперт, но я думаю, что с точки зрения производительности расчеты, необходимые для расчета необходимых сдвигов, будут стоить больше, чем одна инструкция деления. Однако подход со сдвигом имеет преимущества помимо производительности, в основном гарантирует отсутствие времени, зависящего от секретных данных.
флаг pe
Это похоже на более сложную версию [Lemire](https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/) `(rand() * 20) >> 64` подход.
fgrieu avatar
флаг ng
@SamuelNeves: есть различия. (A) Выражение `(rand() * 20) >> 64` требует, чтобы произведение оценивалось в 69 битах, а это невозможно переносимо; связанный трюк Лемира состоит в том, что 32-битный `rand()` расширен до 64-битного, и ударяет по этой стене для 64-битного `rand()`. (B) Для некоторых значений `rand()`, включая 0xCCCCCCCCCCCCCCCC, то, что я предлагаю, отличается на единицу, но все же имеет идеально равномерное распределение.
Рейтинг:3
флаг in

Просто сделайте % 20

Согласно с http://ithare.com/infographics-operation-costs-in-cpu-clock-cycles/ Целочисленное деление не требует 12-44 циклов ЦП на современном ЦП (а в некоторых случаях меньше из-за конвейерной структуры, если АЛУ больше ничего не делает) Учитывая, что следующее, что вы хотите сделать, это доступ к памяти, который в лучшем случае будет чтением L1, само по себе будет стоить 3-4 цикла, и, вероятно, вы захотите что-то сделать с этим значением.

Я не могу представить себе сценарий, в котором это стоит оптимизировать, даже если можно сократить такт на один-два тактовых импульса.

Ищите узкие места перед оптимизацией.

fgrieu avatar
флаг ng
На [изображении] (http://ithare.com/wp-content/uploads/part101_infographics_v08.png) в вашем полезном источнике указано, что целочисленное деление стоит 15-40 циклов. В тексте цитируется ссылка, указывающая «стоимость 32/64-битного деления (известного как DIV/IDIV на x86/64) — между 12-44 циклами». По моему опыту, это чрезвычайно зависит от платформы и ширины аргументов, и моя интуиция подсказывает, что 15 или даже 12 не отражают передовой край 2021 года. Наша (общая) первоначальная интуиция о том, что на процессоре x64 `i%20` достаточно быстр и может быть самым быстрым, все еще имеет смысл.
Meir Maor avatar
флаг in
@fgrieu Действительно, я скопировал неправильный номер, я исправил номер. Сути это не меняет. Это быстро.
Gilles 'SO- stop being evil' avatar
флаг cn
Если 20 является константой и числа не больше одного машинного слова, `% 20` обычно оптимизируется для умножения, которое занимает меньше циклов, чем деление, что еще больше уменьшает разницу. В любом случае я согласен с тем, что даже деление незначительно по сравнению с доступом к памяти на любой платформе с кешем памяти (особенно если это поиск в таблице с постоянным временем, который требует много загрузок). Однако для криптографических приложений использование деления или умножения может оказаться нежелательным, поскольку для них обычно используется синхронизация, зависящая от данных.
Meir Maor avatar
флаг in
Сначала я дал количество циклов для умножения, а затем отредактировал следующий комментарий. Фактическая микрооптимизация, подобная этой, сложна и зависит от того, что еще происходит, чтобы увидеть, насколько хорошо процессор упаковывает инструкции. Хотя я думаю, что не буду делать свой ответ длиннее, чем он есть.
Рейтинг:1
флаг sk

Обычно нужно стремиться сделать размер массива степенью 2. Тогда индекс можно вычислить с помощью побитового И:

массив символов [0x40];
uint64_t ранд;
...
char c = массив [rand & 0x3f];
флаг id
Это своего рода ответ «Я могу решить другую проблему очень быстро». Конечно, но это не тот вопрос, который задают. А в криптографии, когда алгоритм говорит использовать 20, вы не заменяете 32 только потому, что это будет быстрее. Такое программирование — это то, как вы взламываете криптографию.
ThomasM avatar
флаг sk
Как я понял вопрос, алгоритм не дан, а строится. В противном случае, вероятно, был бы определенный способ вычисления индекса из случайного числа, и нельзя было бы пробовать разные методы, чтобы найти самый быстрый.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.