Ускоряет ли перестановка условной оценки цикл?
Немного странно: мне недавно друг сказал, что я переставляю этот пример for цикл из:
for(int i = 0; i < constant; ++i) {
// code...
}
чтобы:
for(int i = 0; constant > i; ++i) {
// code...
}
немного увеличит производительность в C++. Я не понимаю, как сравнение постоянного значения с переменной происходит быстрее, чем наоборот, и некоторые элементарные тесты, которые я выполнял, не показали никакой разницы в скорости между двумя реализациями. То же самое относится и к тестированию этого Python while цикл:
while i < constant:
# code...
i += 1
против:
while constant > i:
# code...
i += 1
Я ошибся? Моих простых тестов недостаточно, чтобы определить изменение скорости? Это правда о других языках? Или это просто новая лучшая практика?
13 ответов
Это больше относится к фольклору C++, ручным микрооптимизациям, которые когда-то работали над определенной версией конкретного компилятора и впоследствии передавались как своего рода знания, отличающие владельца от общего стада. Это мусор. Профилирование - это правда.
Вероятно, нет, но если это произойдет, компилятор в любом случае, вероятно, выполнит оптимизацию автоматически. Так что делайте так, чтобы ваш код был наиболее читабельным.
Мое подозрение, что твой друг на 100% неправ. Но я бы не стал доверять своему мнению больше, чем доверять твоему другу. На самом деле, если есть проблема с производительностью, есть только один человек, которому вы должны доверять.
Профилировщик
Это единственный способ, с помощью которого вы можете утверждать, что один путь есть или не быстрее другого.
Приведенные вами примеры не должны иметь абсолютно никакой разницы в производительности в C++, и я сомневаюсь, что в Python они также будут отличаться.
Возможно, вы путаете это с другой оптимизацией:
for (int i = 0; i < variable; ++i)
// ...vs...
for (int i = variable; i ; --i)
Последнее работает быстрее в некоторых архитектурах, потому что при уменьшении переменной будет установлен нулевой флаг, который затем может быть проверен с помощью инструкции "прыгай, если не ноль", давая вам итерацию цикла и условие за один раз. В первом примере необходимо выполнить явное сравнение или вычитание, чтобы установить флаг, а затем перейти на основе этого.
Однако большую часть времени компилятор может оптимизировать первый случай во второй (особенно, если он видит, что переменная фактически является константой), и на некоторых комбинациях компилятор / архитектура могут генерироваться инструкции, которые делают первый метод более похожим на второй, Подобные вещи стоит попробовать только в том случае, если у вас узкий внутренний цикл, о котором говорит ваш профилировщик, это дорого, но в противном случае вы никогда не заметите разницу, даже если она есть.
Предполагая оценку короткого замыкания, единственное время, которое должно иметь большое значение, - это если у вас есть вызов медленной функции в вашем цикле. Например, если у вас есть функция, которая запросила значение из вашей базы данных и вернула его, то это:
while(bContinue && QueryStatusFromDatabase==1){
} //while
Будет намного быстрее чем:
while(QueryStatusFromDatabase==1 && bContinue){
} //while
Хотя они логически идентичны.
Это связано с тем, что первый из них может быть остановлен, как только простое логическое значение будет FALSE - запрос должен выполняться только тогда, когда логическое значение равно TRUE, а второе всегда будет запускать запрос.
Если у вас нет необходимости выдавливать все возможные циклы ЦП из цикла, то эти крайние случаи, вероятно, являются единственными, на которые стоит потратить ваше время. Подумайте об этом так: для того, чтобы тратить время, затрачиваемое на этот вопрос, возможно, потребуется несколько миллиардов итераций вашего цикла.
Хуже всего то, что когда у вас есть функция как условие, и у этой функции есть побочные эффекты, которые тайно ожидаются в другом месте кода. Поэтому, когда вы проводите небольшую оптимизацию, побочные эффекты случаются только иногда, и ваш код ломается странным образом. Но это немного касательно. Короткий ответ на ваш вопрос: "Иногда, но обычно это не имеет значения".
Хотя профилирование является лучшим, это не единственный способ.
Вы можете сравнить сборку, создаваемую каждой опцией, которая не должна быть исключена для микрооптимизации, подобной этой. Небольшое исследование команд вашей аппаратной платформы может дать вам хорошее представление о том, имеет ли это изменение какое-то значение и как оно может работать по-другому. Я предполагаю, что вы будете считать количество ходов и сравнивать команды для вашего примера.
Если ваш отладчик позволяет переключаться между исходным и дизассемблированным видом во время перехода, это должно быть довольно легко.
Лучше не выходить из-под контроля для таких оптимизаций оптимизации, которые дадут вам незначительную выгоду (при условии, что это настройка).
Любой здравомыслящий компилятор будет реализовывать оба одинаково. Если один из них работает быстрее, чем другой в какой-либо архитектуре, компилятор оптимизирует его таким образом.
Сравнение с 0 очень быстро, так что на самом деле это будет немного быстрее:
for (int i = constant; i > 0; --i)
{
//yo
}
Я думаю, что лучше использовать != в любом случае, поскольку это облегчает обнаружение одной ошибки и является единственным способом использования итераторов с несмежными структурами данных, такими как связанные списки.
Сегодня на хорошем компиляторе совсем нет.
Во-первых, порядок операндов не имеет никакого значения для наборов команд, которые я видел. Во-вторых, если бы он был, любой достойный оптимизатор выбрал бы лучший.
Мы не должны слепо отклонять производительность, хотя. Отзывчивость по-прежнему имеет значение, равно как и время расчета. Особенно когда вы пишете библиотечный код, вы не знаете, когда вас будут вызывать два миллиона раз подряд.
Кроме того, не все платформы созданы равными. Встраиваемые платформы часто страдают от некондиционных оптимизаторов из-за низкой вычислительной мощности и требований к обработке в реальном времени.
На платформах Desktop/Server вес сместился в сторону хорошо инкапсулированной сложности, которая реализует лучшие алгоритмы масштабирования.
Микрооптимизации вредны только тогда, когда они вредят чему-то другому, например читабельности, сложности или ремонтопригодности. Когда все остальное равно, почему бы не выбрать быстрее?
Было время, когда завершение цикла в нуле (например, путем обратного отсчета) на x86 действительно могло дать ощутимые улучшения в узких циклах, как DEC CX/JCXNZ был быстрее (он все еще потенциально мог бы быть, поскольку он мог сохранить доступ к регистру / памяти для сравнения; теперь оптимизация выполнения компилятора обычно выходит за рамки этого). То, что слышал твой друг, может быть искаженной версией этого.
Я смиренно предполагаю, что на некоторых компиляторах на определенных архитектурах следующее может сократить более эффективно, чем варианты:
i = constant - 1
while (--i) {
}
Чтобы получить постоянные итерации.
Как отмечалось во многих комментариях, компилятор хорошо поработает над оптимизацией цикла для вас (люди, занимающиеся оптимизацией компилятора, много и много времени думают об этом). Разборчивый код, вероятно, более ценный, но YMMV!
Если вы действительно хотите оптимизировать сверх того, что, как вы думаете, может сделать компилятор, я предлагаю посмотреть на сборку, которую генерирует язык высокого уровня, и рассмотреть дальнейшую оптимизацию оттуда.
На высоком уровне вы также можете получить значительно более высокую производительность, используя OpenMP или на более низком уровне с помощью набора векторных команд (например, MMX) для выполнения нескольких вычислений в одной инструкции. Это немного выходит за рамки вопроса, и вам придется дать гораздо больше информации о том, что делает цикл, за полезные советы по этому вопросу.
Надеюсь, что это помогает и ура.
Поставленная оптимизация только оптимизирует больше для данного компилятора (возможно). Абстрактно, он должен генерировать тот же код.
Если вы выполняете микрооптимизацию - если предположить, что требования к микрооптимизации выполнены - ваш первый шаг должен состоять в том, чтобы взглянуть на сгенерированную сборку, а затем на руководства по сборке для вашей архитектуры.
Например, i++ может быть быстрее, чем i+1. Зависит. В наивных процессорах равенство 0 намного быстрее, чем меньше. Если ваш компилятор / ЦП не поддерживает переупорядочение инструкций, вы можете обнаружить, что перераспределение назначений с помощью вычислений ускоряет ваш код. (некоторые вычисления могут привести к остановке конвейера) Но это то, что вам нужно будет специально определить для вашей комбинации компилятор / архитектура.
Честно говоря, я бы не стал заниматься оптимизацией такого уровня, если бы мне абсолютно не требовался каждый последний цикл от моего процессора. Традиционно, графические или научные вычисления - это то, где вам нужны подобные вещи [*].
* Я знаю программу, которая после нескольких месяцев оптимизации и на современных машинах все еще может занять много месяцев для обработки данных. Время выполнения для одного набора данных находится в недельном диапазоне. Есть довольно много данных для использования....
Это абсолютно случай микрооптимизации, и в действительности это не нужно делать.
Это правда, что (особенно) в C++ существует небольшая разница в производительности между операцией после инкремента и операцией перед инкрементом, но эта разница в современных компиляторах, как правило, незначительна. Причина изменения порядка условных выражений заключается в переходе от пост-к пре-приращению.