3

Есть блоки кода вычислений блок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;
}

Можете объяснить почему? Мне лично кажется, что первый вариант быстрый и правильный.

7
  • 6
    Если блоки абсолютно независимы, то зачем городить кучу циклов?
    – user6550
    13 авг 2012 в 13:59
  • 1
    @Vfvtnjd, в большинстве случаев, безусловно, первый вариант лучше. Конечно, можно представить ситуацию, когда при первой итерации несколько блоков запрашивают большое количество памяти (каждый независимо от других), а при последней итерации освобождают ее. В подобном (теоретическом) случае в первом варианте может начаться paging, а во втором нет (и время исполнения будет отличаться на пару порядка).
    – avp
    13 авг 2012 в 14:11
  • @Vfvtnjd Сможете придумать ситуацию, когда быстродействие этого кода будет действительно на что-либо влиять? 13 авг 2012 в 14:15
  • Если бы речь шла о C, то возможно в некоторых случаях циклы по отдельности работали бы быстрее. Но в PHP, я думаю, разницы не будет никакой.
    – dzhioev
    13 авг 2012 в 14:27
  • Кстати, Автор, Вас какой язык-то интересует? В тэгах C++ и PHP, а в заголовке вопроса PHP...
    – gecube
    13 авг 2012 в 15:28

4 ответа 4

7

Можно перефразировать вопрос так: "Есть процедура1 и процедура2. Какая работает быстрее?".

Очевидно, что выбор реализации надо решать на конкретном коде, потому что смоделировать в голове сложный процессор с кучей фишек вроде реордеринга и префетча нереально. Так что тестить, тестить и еще раз тестить.

Мои соображения:

  1. Первый вариант (Убер-цикл) хорош для маленьких несвязных кусочков или слабо-связных (не связность вычислений вообще всегда хорошо). В этом случае сведется к минимуму кеш-миссы (Предполагаем что мало кода дергает мало памяти). Реордеринг инструкций и конвейер позволит добиться параллелизма на уровне АЛУ при выполнении инструкций.

  2. Для обратной ситуации в убер-цикле, когда много кода (и он скорее всего дергает кучу разной памяти) можно убить хардварный префетч и потерять много на кеше. Товарищ avp сказал про выгрузку\загрузку страниц, но это уже макроуровень. Сложно представить код, который должен выполнится туеву хучу раз и каждая итерация при этом так нагружает менеджер памяти. Если данные сильносвязаны, то будет совсем все плохо, если же нет - то можно ожидать частичного паралелизма некоторых инструкций.

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

  4. Вариант с хардварным анроллом. Если цикл совсем мал и он попадает под определенные паттерны, то его может развернуть сам процессор. Производительность при срабатывании этой фичи серьезно подскакивает. Загвоздка в том что нет рекомендаций по тому, как писать код для этой фичи (В одном из докладов видел сложное объяснение почему этим нереально пользоваться на практике).

  5. Анролл компилятором (или вручную). Компилятору будет проще развернуть (при указании опции это сделать) простой маленький цикл, чем громадный и непонятный. После правильного анролла вручную можно повысить шанс генерирования кода для векторного процессора.

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

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

Ну вот такая вот простынка. Замечания приветствуются.

1
  • @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 минут на коленке) в моем ответе.
    – avp
    13 авг 2012 в 20:10
2

Ответ скорее не ТС, а @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 <stdio.h>

#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 <stdio.h>
#include <sys/time.h>

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);
...
5
  • Ваш пример это мой первый пункт, где убер-цикл быстрее. 4, 5, 6 это надежда на анролл и векторизацию. Если запустить с -ftree-vectorize -msse2 -ftree-vectorizer-verbose=5. То получаем, что ни один из циклов не поддается автоматической векторизации. -funroll-loops ускоряет вариат с шестью циклами, но не настолько что бы обогнать один. Согласен, что тут один цикл лучше.
    – IronVbif
    14 авг 2012 в 7:24
  • Вот пункт 1 (один цикл) это и есть ручной анролл (а также (в некотором смысле векторизация) думаю, что в данном случае конвейер FPU загружается достаточно полно за счет опережающей выборки команд без реальной записи результатов в кэш (в проце будет переименование регистров)). В реальной жизни я бы не обольщался насчет 4, 5, 6. С другой стороны, программа написанная как последовательность коротких циклов легче распараллеливается вручную.
    – avp
    14 авг 2012 в 8:29
  • спасибо @avp, это то что я хотел понят.
    – Vfvtnjd
    14 авг 2012 в 8:45
  • Сегодня попался код, как раз в тему вопроса, поэтому решил понекропостить. В примере 1 цикл не только страшнее, но и медленней (на моей машине). Выложил тут.
    – IronVbif
    28 авг 2012 в 13:15
  • @IronVbuf, глянул код. IMHO цикл в proc1 это совсем не то, что мы здесь обсуждали. Очевидно, что if в нем жрет много времени.
    – avp
    28 авг 2012 в 14:24
1

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

Если использование многопоточности не подразумевается (я бы не стал надеется, что умный компилятор или интерпретатор сделает это за вас), первый вариант выглядит предпочтительней, так как:

  1. Обслуживание каждой итерации цикла - это как минимум несколько процессорных команд (инкремент счётчика, переход на адрес)
  2. В ряде языков каждая итерация может также неявно обкладываться управляющими конструкциями типа try/catch/finally.
  3. Пример приведён на PHP, а это язык интерпретируемый, больший скрипт дольше компилируется, а это тоже время.

Так или иначе, я бы в первую очередь обратил внимание на читабельность кода. Оптимизацию по скорости целесообразно проводить только для "узких мест". Первый вариант, безусловно, читается лучше, особенно, если тело цикла выделить в отдельную функцию.

0

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.