Альтернатива использованию оператора% и / оператора в C ++

Question

Сказано, что оператор по модулю "%" и оператор деления "/" очень неэффективны во встроенном C ++.

Как альтернативно получить следующее выражение:

a = b % c;

Я понимаю, что этого можно достичь, используя следующую логику:

a = b - c;
while (a >= c) {
  a = a - c;
}

Но мой вопрос: достаточно ли эффективен этот код для циклов while по сравнению с оператором%?

Спасибо, Kirti

Answer 1

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

^{Однако на современных ноутбуках или серверах, а также на высокопроизводительных микроконтроллерах, кэш промахи часто намного медленнее делений!}

Компилятор GCC часто может оптимизировать их, когда делитель постоянный.

Ваш наивный цикл обычно намного медленнее, чем при использовании инструкции аппаратного деления (или при выполнении библиотечной процедуры, если она не предоставляется аппаратным обеспечением). Я считаю, что вы не правы, избегая деления и заменяя его своим циклом.

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

Answer 2

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

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

Answer 3

Этот код почти наверняка будет медленнее, чем ваш процессор / компилятор решит выполнить разделение / мод.Как правило, довольно сложно найти ярлыки для основных арифметических операторов, так как разработчики mcu / cpu и программисты компиляторов довольно хорошо оптимизируют это почти для всех приложений.

Один общий ярлык во встроенных устройствах (где каждый цикл/ byte может иметь значение) состоит в том, чтобы сохранить все в терминах base-2, чтобы использовать операторы сдвига битов для выполнения умножения и деления, а побитовые и (&) для выполнения по модулю.

Примеры:

unsigned int x = 100;
unsigned int y1 = x << 4;   // same as x * 2^4 = x*16
unsigned int y2 = x >> 6;   // same as x / 2^6 = x/64
unsigned int y3 = x & 0x07; // same as x % 8

Answer 4

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

sign = ( x >> 31 ) | 1;

Это расширяет знаковый бит по слову, поэтому отрицательные значения дают -1и положительные значения 0. Затем бит 0 устанавливается так, что положительные значения приводят к 1.

Если мы увеличиваем значения только на величину, меньшую по модулю, то этот же трюк можно использовать для переносарезультат:

val += inc;
val -= modulo & ( static_cast< int32_t >( ( ( modulo - 1 ) - val ) ) >> 31 );

В качестве альтернативы, если вы уменьшаете значения на значения меньше, чем по модулю, соответствующий код:

int32_t signedVal = static_cast< int32_t >( val - dec );
val = signedVal + ( modulo & ( signedVal >> 31 ) );

Я добавил операторы static_cast, потому что передавалuint32_t, но вы, возможно, не найдете их необходимыми.

Это сильно помогает в отличие от простого оператора%?Это зависит от вашего компилятора и архитектуры процессора.Я обнаружил, что простой цикл работает на 60% быстрее на моем процессоре i3 при компиляции под VS2012, однако на чипе ARM11 в Raspberry Pi и компиляции с GCC я получил улучшение только на 20%.

Answer 5

Если делитель известен во время компиляции, операция может быть преобразована в умножение на обратную, с некоторыми сдвигами, сложениями и другими быстрыми операциями.Это будет быстрее на любом современном процессоре, даже если он реализует аппаратное деление.Встраиваемые цели обычно имеют высоко оптимизированные подпрограммы для деления / по модулю, так как эти операции требуются стандартом.

Answer 6

Деление на константу может быть достигнуто путем сдвига, если степень 2 или комбинация с множественным добавлением сдвига для других.

http: // masm32.com/board/index.php?topic=9937.0 имеет версию сборки x86, а также исходный код C, загружаемый из первого поста. который генерирует этот код для вас.