Говорят, что modulo operator "%" и оператор деления "/" очень неэффективны во встроенном С++.
Как я могу альтернативно достичь следующего выражения:
a = b % c;
Я понимаю, что это может быть достигнуто с использованием следующей логики:
a = b - c;
while (a >= c) {
a = a - c;
}
Но мой вопрос заключается в том, что этот код включает в себя достаточно эффективные циклы по сравнению с% operator?
Спасибо, Kirti
Ничто не будет значительно более эффективным, чем оператор %. Если бы был лучший способ сделать это, любой разумный компилятор автоматически преобразил бы его. Когда вам говорят, что % и / неэффективны, это просто потому, что это сложные операции - если вам нужно выполнить modulo, тогда сделайте это.
Могут быть особые случаи, когда есть лучшие способы - например, mod, мощность двух может быть записана как двоичная или - но они, вероятно, оптимизированы вашим компилятором.
Подразделение и модуль действительно являются дорогостоящими аппаратными операциями, что бы вы ни делали (это больше связано с аппаратной архитектурой, чем с языками или компиляторами), возможно, в десять раз медленнее, чем добавление.
Однако на текущих ноутбуках или серверах, а также на high-end микроконтроллерах cache промахи часто бывают намного медленнее, чем деления
Компилятор GCC часто может их оптимизировать, когда делитель является константой.
Ваш наивный цикл, как правило, намного медленнее, чем использование инструкции аппаратного деления (или выполняемой ею библиотечной процедуры, если она не предоставляется аппаратными средствами). Я считаю, что вы ошибаетесь, избегая деления и заменяя его своим циклом.
Вы можете настроить свои алгоритмы - например. имея силу двойки, но я не рекомендую использовать ваш код. Помните, что преждевременная оптимизация - это зло, поэтому сначала попробуйте правильно настроить вашу программу, а затем профилируйте ее, чтобы найти проблемы.
Этот код почти наверняка будет медленнее, чем ваш процессор/компилятор решает выполнить деление /mod. Как правило, ярлыки довольно сложно найти для основных арифметических операторов, поскольку дизайнеры mcu/cpu и программисты компилятора довольно хорошо оптимизируют это для почти всех приложений.
Один общий ярлык во встроенных устройствах (где каждый цикл/байт может изменить ситуацию) заключается в том, чтобы сохранить все в терминах base-2, чтобы использовать операторы сдвига битов для выполнения умножения и деления, а побитовые и (&) - для выполнения modulo.
Примеры:
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
Если делитель известен во время компиляции, операция может быть преобразована в умножение на обратную, с некоторыми сдвигами, добавлениями и другими быстрыми операциями. Это будет быстрее на любом современном процессоре, даже если он реализует разделение на аппаратном уровне. Встраиваемые цели обычно имеют высоко оптимизированные подпрограммы для деления/модуляции, так как эти операции требуются стандартом.
Если вы тщательно профилировали свой код и обнаружили, что оператор modulo является основной стоимостью во внутреннем цикле, тогда есть оптимизация, которая может помочь. Возможно, вы уже знакомы с трюком для определения знака целого числа с использованием арифметических сдвигов влево (для 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 в малине Pi и компиляции с GCC я получил только улучшение на 20%.
Разделение на константу может быть достигнуто сдвигом, если сила 2 или комбинация смещений добавляется к другим.
http://masm32.com/board/index.php?topic=9937.0 имеет версию сборки x86, а также источник C при загрузке с первого сообщения. который генерирует этот код для вас.