И быстрее, чем целочисленная операция по модулю?

Question

Возможно повторное выражение:

• i% m

как:

• i & (m-1)

, где

• i - целое число без знака
• м - это сила 2

У меня вопрос: быстрее ли операция AND? Разве современные процессоры не поддерживают целочисленные модули в аппаратном обеспечении в одной инструкции? Я заинтересован в ARM, но не вижу операции по модулю в наборе команд.

Answer 1

В наши дни это сложнее, чем «одна инструкция». Современные процессоры - это сложные звери, и их инструкции нужно разбить на выпуск / выполнение / задержку. Это также обычно зависит от ширины деления / по модулю - сколько битов задействовано.

В любом случае, я не знаю, что 32-битная задержка одного цикла на любом ядре, ARM или нет. В «современном» ARM есть инструкции целочисленного деления, но только в некоторых реализациях, и, что особенно важно, не в самых распространенных - Cortex A8 и A9.

В некоторых случаях компилятор может избавить вас от необходимости преобразования деления / модуля по битам / операций сдвига / маски. Однако это возможно только в том случае, если значение известно во время компиляции . В вашем случае, если компилятор может видеть наверняка , что 'm' всегда является степенью двойки, то он оптимизирует его для битовых операций, но если это переменная, переданная в функцию (или иначе вычисляется), то не может и прибегнет к полному разделению / модулю. Этот вид построения кода часто работает (но не всегда - зависит от того, насколько умен ваш оптимизатор):

unsigned page_size_bits = 12;
unsigned foo(unsigned address) {
  unsigned page_size = 1U << page_size_bits;
  return address / page_size;
}

Хитрость заключается в том, чтобы сообщить компилятору, что "page_size" является степенью двойки. Я знаю, что gcc и варианты будут в особом случае, но я не уверен насчет других компиляторов.

Как правило, для любого ядра - ARM или нет (даже x86), предпочитайте битовое смещение / маску делить / по модулю. Даже если ваше ядро ​​имеет аппаратный разрыв, это будет быстрее сделать это вручную.

Answer 2

Возможно, вас заинтересует Embedded Live: Руководство по встроенным программистам для архитектуры ARM Cortex-M .

Семейство ARM Cortex-M имеет беззнаковые и опаленные инструкции деления, UDIV и SDIV, которые занимают от 2 до 12 циклов. Инструкции MOD нет, но эквивалентный результат получается с помощью {S, U} DIV, за которым следует команда MLS умножения и вычитания, которая занимает 2 цикла, всего 4-14 циклов.

Инструкция AND является одиночным циклом, поэтому в 4-14 раз быстрее.

Answer 3

Если m известно во время компиляции (или даже не известно), целочисленное деление и по модулю может быть повторно выражено с помощью умножения на магический «мультипликативный обратный».Результат деления заканчивается в старших 32 битах, а остаток (модуль) в младших 32 битах:

http://www.hackersdelight.org/magic.htm

Следующая ссылка утверждает, что это стандартная сила компиляторасокращение:

http://www.flounder.com/multiplicative_inverse.htm

Answer 4

ARM очень универсальный. Существует много различных ARM, и есть ARM, которые НЕ имеют инструкции деления (как уже упоминал Рэй Тоал, модуль обычно реализуется как дополнительный результат реализации деления). Поэтому, если вы не хотите вызывать подпрограмму с очень медленным делением, логическая операция выполняется намного быстрее (и, как упоминалось в cyco130, любой хороший компилятор распознает ее самостоятельно и сгенерирует логическую операцию самостоятельно - так для ясности программного кода Я бы остался в отделе (кроме вас, ассемблер программ, тогда вы, конечно, должны программировать его самостоятельно, а затем вам следует выполнить логическую операцию).

Answer 5

Согласно http://www.coranac.com/tonc/text/asm.htm, ARM не имеет инструкции деления.Если это правда, то я бы не ожидал, что в нем также будет инструкция MOD.

Answer 6

Если вы используете приличный компилятор C с включенными оптимизациями, он уже оптимизирует это до скорости, которая называется «снижение силы». Если вы делаете рукописную сборку, единственный верный способ проверить это - сравнить его. Но будьте осторожны, даже разные модели одного и того же процессора могут давать разные результаты.