Несколько вложенных для циклов против одного для цикла

Question

Несколько вложенных для циклов против одного для цикла

Я провел небольшое тестирование скорости в c ++ (MSVS) и получил странный результат. Я тестировал скорость использования одного цикла for против нескольких вложенных циклов. Вот код:

double testX = 0;
// Single loop executes in roughly 0.04 seconds
for( int i = 0; i < 27000000; i++ ){
testX += 1;
}

// Nested loop executes in roughly 0.03 seconds
for( int x = 0; x < 300; x++ ){
for( int y = 0; y < 300; y++ ){
for( int z = 0; z < 300; z++ ){
testX += 1;
}
}
}

Как видите, разница в скорости довольно очевидна. Я запускал это много раз, и это среднее время, которое я вижу (они рассчитаны с использованием glfwGetTime ()).

Итак, мой вопрос: почему? Является ли мой метод испытаний неадекватным? Я использую слишком мало петель? Я попытался найти в Google, и единственный подобный вопрос, который я смог найти, связал его проблему с когерентностью кэша, но, поскольку они пустые для циклов, я не думал, что это действительно даст эффект.

Любая помощь ценится 🙂

Редактировать: Благодаря комментариям я понял, что использование пустых циклов for, вероятно, было не лучшим способом проверки вещей … Поэтому я обновил свой код, чтобы выполнить некоторые (очень) простые операции до двойного. Я также собираю в режиме релиза. Тем не менее, хотя эти два метода во многом похожи во времени, второй метод все же немного быстрее.

И да, это весь тестовый код (за исключением функций синхронизации / вывода, но они не совсем специфичны для вопроса).

5

c++for-loop nested timing

Решение

Другие решения

Если вы не используете свой for переменные (x,y,z) внутри вашего for цикл, умный компилятор может (и должен) преобразовать вашу вторую форму в одном for цикл без вложенности. Если вы не запретите такую оптимизацию компилятора, удаляя статическую предсказуемость, если пользователь введет x,y,z значения во время выполнения от stdinили чтение из какого-то потока и т.д ..

Кроме того, если вы не делаете что-то с вашим testX переменная (скажем, печать в stdout), умный компилятор может (и должен) оптимизировать его, то есть полностью удалить мертвый код.

Так что я говорю о том, что эталон, как и сейчас, как-то плохо сформирован.

1

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

0

Источник

Accepted Answer

Компилятор не будет «оптимизировать» циклы, когда переменная testX используется где-то позже в коде. Когда я просто добавляю одну строку в код для вывода testX, результаты выглядят следующим образом:

single for loop: 1.218 ms
nested for loop: 1.218 ms

Это в значительной степени показывает, что компилятор конвертирует вложенный цикл в один цикл, когда это возможно. Индекс цикла можно использовать для предотвращения этой оптимизации:

Модификация кода таким образом

for( int i = 0; i < 27000000; i++ ){
testX += i;
}

а также

for( int x = 0; x < 300; x++ ){
testX += x;
for( int y = 0; y < 300; y++ ){
testX += y;
for( int z = 0; z < 300; z++ ){
testX += z;
}
}
}

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

single for loop: 1.224 ms
nested for loop: 1.226 ms

Приведенное здесь время усредняется за 30 000 циклов.

Обратите внимание testX += x; только вносит 1 в 90000 и testX += x; дает только 1 из 300. Таким образом, два раздела выше остаются сопоставимыми.

Вложенные циклы не намного медленнее, чем одиночные, но вы заметили, что они быстрее не правда.

А также: Время, которое вы показываете, примерно в 40 раз больше, чем я наблюдал. Я бы посоветовал тщательно проверить настройки компилятора, поскольку я запускал тест на среднескоростном оборудовании. Может быть, результаты glfwGetTime() сомнительны, и это главная причина вашего вопроса. Вы пытались использовать другую схему синхронизации?

Редактировать: Чтобы предотвратить оптимизацию компилятора, предел цикла может быть выбран непостоянным:

int lmt = rand() % 1 + 300;      // random value 300 or 301
int big_lmt = lmt * lmt * lmt;   // random value 27000000 or 27270901

for( int i = 0; i < big_lmt; i++ ){
testX += i;
}

for( int x = 0; x < lmt; x++ ){
testX += x;
for( int y = 0; y < lmt; y++ ){
testX += y;
for( int z = 0; z < lmt; z++ ){
testX += z;
}
}
}

Это позволяет избежать предсказуемости компилятора.

Результаты (для lmt = 300 случай, чтобы быть сопоставимым):

single for loop: 1.213 ms
nested for loop: 1.216 ms

Результат:

Вложенные циклы не быстрее, чем одиночные петли.

9