#c #циклы #cpp #php
Есть блоки кода вычислений блок1, блок2, блок3, блок4,...блок 10, скажем. Скажите,
как поступить при использовании их в цикле:
for (i = 0; i <= n; i++) {
блок1;
блок2;
блок3;
блок4;
...
блок10;
}
Или же так оптимально:
for (i = 0; i <= n; i++) {
блок1;
}
for (i = 0; i <= n; i++) {
блок2;
}
.............
for (i = 0; i <= n; i++) {
блок10;
}
Можете объяснить почему? Мне лично кажется, что первый вариант быстрый и правильный.
Ответы
Ответ 1
Ответ скорее не ТС, а @IronVbuf. Начало развернутого комментирования его ответа. Копия моего комментария: @IronVbif, рассуждения красивые. Время позднее, не хочу (сейчас) все разбирать. Если правильно понял, в пунктах 4, 5 и 6 Вы склоняетесь к тому, что несколько маленьких циклов (особенно если их тела маленькие) будут производительней одного. Практический замер (gcc -O3 MinGW (32-bit) Windows 7 64-bit I5-2500 3.3GHz) показал обратное (причем аж в 3 раза для 6 циклов и 10^9 повторов маленьких вычислений (преобразование int->double, double умножение и сложение) Примерчик (нисколько не претендует на полноту, 5 минут на коленке). gcc -O3 MinGW (32-bit) Windows 7 64-bit I5-2500 3.3GHz #include#define incvar(x,y) {x = x + i*y;} main (int ac, char *av[]) { double a = 0, b = 0, c = 0, d = 0, e = 0, f = 0; int i; if (av[1]) { printf ("one loop\n"); for (i = 0; i < 1000000000; i++) { incvar(a,1.234); incvar(b,7.234); incvar(c,11.234); incvar(d,111.234); incvar(e,51.234); incvar(f,21.234); } } else { printf ("six loops\n"); for (i = 0; i < 1000000000; i++) incvar(a,1.234); for (i = 0; i < 1000000000; i++) incvar(b,7.234); for (i = 0; i < 1000000000; i++) incvar(c,11.234); for (i = 0; i < 1000000000; i++) incvar(d,111.234); for (i = 0; i < 1000000000; i++) incvar(e,51.234); for (i = 0; i < 1000000000; i++) incvar(f,21.234); } printf ("%e %e %e %e %e %e\n",a,b,c,d,e,f); } c:/Users/avp/src/cc/hashcode $ gcc -O3 bloloops.c c:/Users/avp/src/cc/hashcode $ date; ./a; date Mon Aug 13 23:55:42 2012 six loops 6.170000e+017 3.617000e+018 5.617000e+018 5.561700e+019 2.561700e+019 1.061700e+019 Mon Aug 13 23:56:00 2012 c:/Users/avp/src/cc/hashcode $ date; ./a 1; date Mon Aug 13 23:56:17 2012 one loop 6.170000e+017 3.617000e+018 5.617000e+018 5.561700e+019 2.561700e+019 1.061700e+019 Mon Aug 13 23:56:23 2012 c:/Users/avp/src/cc/hashcode $ Все желающие приглашаются к экспериментированию (вместо теоретизирования на основе прочитанной литературы) с последующим обсуждением результатов. UPDATE Для замера времени исполнения фрагментов программы удобно использовать функцию: /* avp время в миллисекундах */ #include #include long long mtime() { struct timeval t; gettimeofday(&t, NULL); long long mt = (long long)t.tv_sec * 1000 + t.tv_usec / 1000; return mt; } Меряем так: ... long long mtime(void); ... long long start = mtime(); // измеряемый код ... printf ("duration: %lld msec\n",mtime()-start); ... Ответ 2
Можно перефразировать вопрос так: "Есть процедура1 и процедура2. Какая работает быстрее?". Очевидно, что выбор реализации надо решать на конкретном коде, потому что смоделировать в голове сложный процессор с кучей фишек вроде реордеринга и префетча нереально. Так что тестить, тестить и еще раз тестить. Мои соображения: Первый вариант (Убер-цикл) хорош для маленьких несвязных кусочков или слабо-связных (не связность вычислений вообще всегда хорошо). В этом случае сведется к минимуму кеш-миссы (Предполагаем что мало кода дергает мало памяти). Реордеринг инструкций и конвейер позволит добиться параллелизма на уровне АЛУ при выполнении инструкций. Для обратной ситуации в убер-цикле, когда много кода (и он скорее всего дергает кучу разной памяти) можно убить хардварный префетч и потерять много на кеше. Товарищ avp сказал про выгрузку\загрузку страниц, но это уже макроуровень. Сложно представить код, который должен выполнится туеву хучу раз и каждая итерация при этом так нагружает менеджер памяти. Если данные сильносвязаны, то будет совсем все плохо, если же нет - то можно ожидать частичного паралелизма некоторых инструкций. Куча маленьких циклов будет хороша для большого количества данных (используемых в каждом блоке). С одной стороны всегда четко отрабатывает префетч и кеш (Насколько это возможно, потому что все что вы будете дергать нужно именно этому блоку), но при этом спариться инструкции между итерациями не смогут (скорее всего). Потеря производительности на инструкциях не страшна, поскольку лучше всегда выигрывать в обращении к памяти. В ряде случаев компилятор может построить код для векторного сопроцессора (работает в случае простых циклов с маленькими блоками, отсюда же понятно почему для убер-цикла шанс векторизации меньше). Вариант с хардварным анроллом. Если цикл совсем мал и он попадает под определенные паттерны, то его может развернуть сам процессор. Производительность при срабатывании этой фичи серьезно подскакивает. Загвоздка в том что нет рекомендаций по тому, как писать код для этой фичи (В одном из докладов видел сложное объяснение почему этим нереально пользоваться на практике). Анролл компилятором (или вручную). Компилятору будет проще развернуть (при указании опции это сделать) простой маленький цикл, чем громадный и непонятный. После правильного анролла вручную можно повысить шанс генерирования кода для векторного процессора. Вариант когда несколько циклов будет работать медленней придумать сложно, но можно предположить что оверхед от инкрементов переменной i и сравнений будет сравним с временем выполнения цикла. Но скорей всего такой цикл заанролится или векторизуется компилятором, поскольку он очень простой. Естественно для интерпретируемых языков это все не будет работать. Насколько я понимаю, для них чем меньше кода, тем лучше. Ну вот такая вот простынка. Замечания приветствуются.Ответ 3
В случае независимых блоков можно получить выигрыш с помощью второго варианта, разместив каждый цикл в своём потоке. Если же последовательность выполнения блоков важна это вряд-ли получится. Если использование многопоточности не подразумевается (я бы не стал надеется, что умный компилятор или интерпретатор сделает это за вас), первый вариант выглядит предпочтительней, так как: Обслуживание каждой итерации цикла - это как минимум несколько процессорных команд (инкремент счётчика, переход на адрес) В ряде языков каждая итерация может также неявно обкладываться управляющими конструкциями типа try/catch/finally. Пример приведён на PHP, а это язык интерпретируемый, больший скрипт дольше компилируется, а это тоже время. Так или иначе, я бы в первую очередь обратил внимание на читабельность кода. Оптимизацию по скорости целесообразно проводить только для "узких мест". Первый вариант, безусловно, читается лучше, особенно, если тело цикла выделить в отдельную функцию.Ответ 4
Все сильно зависит от характера блоков. Возможна связность между блоками кода и их нельзя будет просто так попередвигать. Ну, или наоборот. Так же бывает, что выгоднее использовать не прямой порядок, а обратный. В общем, слишком много нюансов.
Комментариев нет:
Отправить комментарий