Сравнение прямого и обратного цикла для int с одним лимитом 0

Question

Рассмотрим пример с циклом for:

for(int i = 0; i <= NUM; i++);  // forward
for(int i = NUM; i >= 0; i--);  // reverse

Я проверил этот цикл с помощью gcc (linux-64).Без какого-либо флага оптимизации прямой цикл был быстрее, а при оптимизации до O3 / O4 обратный цикл был быстрее.

Где-то я слышал, что благодаря лучшим методам замены кэша прямой цикл быстрее.

Лично я считаю, что обратный цикл должен быть быстрее (независимо от того, является ли NUM константой или переменной).Потому что любой микропроцессор будет иметь одну инструкцию для сравнения с 0, i >= 0 (то есть JLZ (jump if less than zero) и эквивалентными).

Есть ли какой-либо детерминированный ответ на это?

Answer 1

Нет, для этого нет абсолютно нет детерминированного ответа. Вы смотрите на два разных уровня абстракции.

C ++ не имеет абсолютно ничего , чтобы сказать о том, что происходит под прикрытием с точки зрения производительности. Он определяет виртуальную машину, которая выполняет код C ++, и, хотя он охватывает функциональность, он не покрывает производительность базовой среды ^(a) .

Какой из них быстрее, будет зависеть от множества факторов. Вы можете работать на процессоре, который не делает различий между сравнением с произвольным значением и сравнением с нулем.

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

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

Итог: вы не можете позволить себе знать, что происходит под капотом, если вы не хотите смотреть на очень специфический процессор, компилятор и т. Д.

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

В любом случае, поскольку вы почти наверняка будете использовать i для чего-то, вполне вероятно, что любое незначительное увеличение производительности, которое вы получите, идя самым быстрым путем, будет более чем подавлено тот факт, что теперь вы должны вычислять NUM-i внутри цикла (если, конечно, компилятор не умнее разработчика, что, на основании того, что я видел из gcc, вполне возможно).

---

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

Answer 2

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

Попытка потенциально сохранить одну машинную инструкциюпоказывая отсутствие доверия к компилятору.Если бы это было так просто, то оптимизатор знал бы это!

Answer 3

Хотя на самом деле это не ответ на ваш вопрос, а мысль. Как насчет этого цикла:

int  i = NUM + 1;
while ( i --> 0 )//it looks as if i goes to zero (like in calculus)!
{
}

Answer 4

Возможно, приращение переменной цикла является настолько более распространенным, что предсказание ветвления ЦП работает лучше для них.

С оптимизацией компилятора ваш цикл может быть просто развернут - учитывая, что я правильно предполагаю, что NUMявляется константой #define и, следовательно, быстрее.