Зачем нужен оператор по модулю?
Я прочитал в документе, что вы можете заменить операцию мода на логическую и вот так:
Вместо:
int Limit = Value % Range;
Ты сделаешь:
int Limit = Value & (Range-1);
Но компиляторы все еще генерируют инструкции модов, и мой вопрос в основном: почему компиляторы не используют наиболее эффективный подход, если они работают одинаково?
3 ответа
Вы можете заменить по модулю на это, только если это степень 2. Использование элементарной математики, чтобы заменить его без модуля
a = b % c;
может быть сделано с
x = b % c;
a = b / (x*c);
Давайте проверим это на примере
25 % 7 =
25 / 7 = 3 (integer math)
25 - (3 * 7) =
25 - 21 = 4
Вот как я должен это делать на калькуляторе, так как у меня нет оператора по модулю.
Обратите внимание, что
25 & (7-6) =
0x19 & 0x6 = 0x0
Так что твоя замена не работает.
Мало того, что большинство процессоров не имеют модуля, многие не имеют разрыва. Проверьте книгу восхищения хакеров.
ПОЧЕМУ ты хочешь по модулю? Если вы сожгли оборудование, чтобы разделить, вы, возможно, захотите пройти лишнюю милю, чтобы добавить по модулю. Большинство процессоров переносят ваш вопрос на следующий уровень. Зачем вам реализовывать аппаратное деление, если это можно сделать программно. Ответ на ваш вопрос заключается в том, что большинство семейств процессоров не имеют модуля по модулю, а многие не имеют деления, потому что это не стоит затрат на чипы, потребляемую мощность и т. Д. По сравнению с программным решением. Программное решение менее болезненно / дорого / рискованно.
Теперь я предполагаю, что ваш вопрос не в том, на что ответил победитель. Для случаев, когда Range является степенью двойки и идентичность работает... Во-первых, если range не известен во время компиляции, тогда вы должны сделать вычитание и две операции, и, возможно, промежуточную переменную, то есть гораздо более дорогостоящий, чем по модулю, компилятор будет по ошибке оптимизирован для вычитания и вместо модуля. Если диапазон является степенью двойки и известен во время компиляции, ваши лучшие / лучшие компиляторы будут оптимизировать. Временами, особенно с набором команд переменной длины слова, где меньшая инструкция может использоваться над большой инструкцией, может быть менее болезненно загружать Range и выполнять по модулю, чем загружать большее количество ненулевых битов (значения Диапазон, соответствующий вашей идентичности, имеет один бит, установленный в значении, остальные биты равны нулю, 0x100, 0x40, 0x8000 и т. Д.) И выполняются по модулю. немедленный плюс плюс по модулю может быть дешевле немедленного плюс плюс, или немедленный по модулю может быть дешевле немедленного. Вы должны изучить набор инструкций и то, как компилятор реализовал решение.
Я предлагаю вам опубликовать несколько примеров, когда он не выполняет оптимизацию, и я предполагаю, что мы можем опубликовать много примеров, когда компилятор выполнил оптимизацию, которую вы ожидали.
Хм нет... это работает только когда Range это сила двух.
Для всех других значений вам все еще нужен модуль % оператор.
Есть также некоторые тонкие (возможно, определенные реализацией) различия при работе с отрицательными числами.
В качестве примечания: с помощью % оператор, вероятно, также более читабелен.
Как уже говорили другие, диапазон должен быть 2^n-1, и даже тогда, если это делается во время выполнения, у вас есть проблемы.
На последних архитектурах (скажем, что-нибудь после эры P4) задержка для команд целочисленного деления составляет от 26 до 50 или около того циклов наихудшего случая. Умножение, для сравнения, может составлять 1-3 цикла и часто может быть выполнено параллельно намного лучше.
Инструкция DIV возвращает частное в EAX и остаток в EDX. "Остаток" свободен (модуль - остаток).
Если вы реализуете что-то, где диапазон является переменным во время выполнения, если вы хотите использовать &, вы должны:
a) проверьте, равен ли диапазон 2^n-1, если это так, используйте ваш & codepath: который представляет собой ветвь, возможную ошибку кэша и т. д., добавляя огромный потенциал задержки b) если он не равен 2^n-1, используйте a Инструкция DIV
Использование DIV вместо добавления ответвления в уравнение (что может привести к сотням или даже тысячам циклов в плохих случаях с плохим удалением кэша) делает DIV очевидным лучшим выбором. Кроме того, если вы используете & с типом данных со знаком, потребуется преобразование (нет & для смешанных типов данных, но есть для DIV). Кроме того, если DIV используется только для перехода от модуля, а остальные результаты не используются, умозрительное выполнение может работать хорошо; Кроме того, ухудшение производительности дополнительно снижается несколькими конвейерами, которые могут выполнять команды параллельно.
Вы должны помнить, что если вы используете реальный код, большая часть вашего кеша будет заполнена данными, с которыми вы работаете, и другим кодом и данными, с которыми вы будете работать в ближайшее время или только что поработали. Вы действительно не хотите удалять страницы кеша и ждать, пока они перейдут на страницу из-за неправильных прогнозов веток. В большинстве случаев по модулю вы не просто идете, я = 7; d = i % 4; вы используете больший код, который часто вызывает подпрограмму, которая сама по себе является (прогнозируемой и кэшированной) вызовом подпрограммы непосредственно перед этим. Кроме того, вы, вероятно, делаете это в цикле, который также использует предсказание ветвлений; Предсказания вложенных ветвлений с циклами обрабатываются довольно хорошо в современных микропроцессорах, но в конечном итоге они просто глупы, чтобы добавить к предсказанию, которое пытаются сделать.
Итак, подведем итог: использование DIV имеет больше смысла на современных процессорах для общего случая использования; на самом деле это не "оптимизация" для компилятора для генерации 2 ^ n-1 из-за соображений кеша и прочего. Если вам действительно нужно точно настроить это целочисленное деление, и вся ваша программа зависит от него, вы в конечном итоге жестко закодируете делитель на 2 ^ n-1 и будете делать побитовую и логику самостоятельно.
Наконец, это немного напыщенно - выделенный блок ALU для целочисленных делений может реально уменьшить задержку примерно до 6-8 циклов, он просто занимает относительно большую область матрицы, потому что путь данных в конечном итоге имеет ширину около 128 бит и Ни у кого нет недвижимости, когда целочисленные DIV работают так, как они есть.