Пользователь
0,0
рейтинг
29 июля 2011 в 14:52

Разработка → Введение в технику оптимизации циклов

Большая часть времени исполнения программы приходится на циклы: это могут быть вычисления, прием и обработка информации и т.д. Правильное применение техник оптимизации циклов позволит увеличить скорость работы программы. Но прежде, чем приступать к оптимизациям необходимо выделить «узкие» места программы и попытаться найти причины падения быстродействия.

Время исполнения кода в циклах зависит от организации памяти, архитектуры процессора, в том числе, поддерживаемого набора инструкций, конвейеров, кэшей и опыта программиста.
Рассмотрим некоторые методы оптимизаций циклов: развертка циклов (loop unrolling), объединение циклов (loop fusion), разрезание циклов (loop distribution), выравнивание циклов (loop alignment), перестановка циклов (loop interchange), разделение на блоки (loop blocking).
Перед применением какой-либо оптимизации сделайте самое простое: вынесите из цикла все переменные, которые в нем не изменяются.

Какие причины могут привести к уменьшению скорости работы программы в циклах?
  1. Итерации цикла зависимы и не могут исполняться параллельно.
  2. Тело цикла большое и требуется слишком много регистров.
  3. Тело цикла или количество итераций мало и выгоднее совсем отказаться от использования цикла.
  4. Цикл содержит вызовы функций и процедур из сторонних библиотек.
  5. Цикл интенсивно использует какое-то одно исполняющее устройство процессора.
  6. В цикле имеются условные переходы.
Развертка циклов

Такая оптимизация выполняется, когда тело цикла мало. Необходимо более эффективно использовать исполняющие устройства на каждой итерации. Поэтому многократно дублируют тело цикла в зависимости от количества исполняющих устройств. Но такая оптимизация может вызвать зависимость по данным, чтобы от нее избавиться вводятся дополнительные переменные.
До После После №2
for (int i = 0; i < iN; i++){
 res *= a[i];
}
for (int i = 0; i < iN; i+=3){
 res *= a[i];
 res *= a[i+1];
 res *= a[i+2];
}
for (int i = 0; i < iN; i+=3){
 res1 *= a[i];
 res2 *= a[i+1];
 res3 *= a[i+2];
}
res = res1 * res2 * res3;
В gcc можно применить следующие ключи: -funroll-all-loops -funroll-loops.

Объединение циклов

В цикле может быть долго выполняющиеся инструкции, например, извлечение квадратных корней. Или есть несколько циклов, которые выполняются по одинаковому интервалу индексов. Поэтому целесообразно объединить циклы для более сбалансированной нагрузки исполняющих устройств.
До После
for(int i = 0; i < iN; i++){
 a[i] = b[i] - 5;
}
for(int i = 0; i < iN-1; i++){
 d[i] = e[i] * 3;
}
for(int i = 0; i < iN-1; i++){
 a[i] = b[i] - 5;
 d[i] = e[i] * 3;
}
a[iN-1] = b[iN-1] - 5;

Разрезание циклов

Данная оптимизация применяется, когда тело цикла большое и переменным не хватает регистров. Поэтому данные сначала вытесняются в кэш, а если совсем все плохо, то и в оперативную память. А доступ к оперативной памяти занимает ~300 тактов процессора, а доступ к L2 всего ~10. Доступ к памяти с большим шагом еще больше замедляет программу. Оптимально «ходить» по памяти с шагом 2n, где n — достаточно маленькое число (<7).
До После
for (int j = 0; j < jN; j++){
for (int k = 0; k < kN; k++){
for (int m = 0; m < mN; m++){
 i = j * k + m;
 a[i] = b[i] * c[i] + f[i]/e[i]+ x[i] - y[i] +
  z[i]/r[i] + d[i] * x[i];
}
}
}
for (int j = 0; j < jN; j++){
for (int k = 0; k < kN; k++){
 double tmp;
 for (int m = 0; m < mN; m++){
  i = j * k + m;
  tmp = b[i] * c[i] + f[i]/e[i];
  a[i] = tmp - y[i] + z[i]/r[i] +
  (d[i] + 1) * x[i];
 }
}
}

Перестановка циклов

Во вложенных циклах важен порядок вложения. Поэтому необходимо помнить как хранятся массивы в памяти. Классический пример: c/c++ хранят матрицы построчно, а fortran — по столбцам.
До После
for(int i = 0; i < iN; i++){
for(int j = 0; j < jN; j++){
for(int k = 0; k < kN; k++){
 c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
}
}
for(int i = 0; i < iN; i++){
for(int k = 0; k < kN; k++){
for(int j = 0; j < jN; j++){
  c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
}
}
Теперь обращения к массиву a идут последовательно.

Разделение циклов на блоки

Если тело цикла сложное, то можно применить эту оптимизацию для более лучшего расположения данных в памяти и улучшения использования кэшей. Результат оптимизации сильно зависит от архитектуры процессора.
До После
for(int i = 0; i < iN; i++){
for(int j = 0; j < jN; j++){
 a[i][j] = a[i][j] + b[i][j];
}
}
// размер блоков зависит от размера исходных массивов
int iBlk, jBlk;
for(int k = 0; k < iN/iBlk; k++){
for(int m = 0; m < jN/jBlk; m++){
 for(int i = k * iBlk; i < ((k + 1) * iBlk); i++){
 for(int j = m * jBlk; j < ((m + 1) * jBlk); j++){
  a[i][j] = a[i][j] + b[i][j];
 }
 }
}
}
Примерно по такому принципу работает технология MPI: делит большие массивы на блоки и рассылает отдельным процессорам.

Разрешение зависимостей

Лучшее решение — избавиться. Но не со всеми зависимостями это получится.
for (int i = 1; i < N; i++){
 a[i] = a[i-1] + 1;
}
Для этого примера лучше применить развертку, т.к. результат вычислений будет оставаться на регистрах. Но большинство таких циклов не могут быть полностью оптимизированы (или распараллелены), результат все равно зависит от предыдущего витка цикла.
Чтобы проверить цикл на независимость, измените направление движения в цикле на обратное. Если результат вычислений не изменился, то итерации цикла — независимы.

Относительно условных переходов

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

Вместо заключения

Если Вы создаете сложную программу, которая будет занимать много процессорного времени, то
  1. Ознакомтесь с архитектурой процессора (узнайте сколько и каких исполняющих устройств у него есть, сколько конвейеров, размеры кэшей L1 и L2).
  2. Попробуйте компилировать программу разными компиляторами и с различными ключами.
  3. Учитывайте влияние операционной системы.
Также советую ознакомиться с этой статьей.
По своему опыту могу сказать, что грамотное применение оптимизаций может улучшить быстродействие программы в разы.

Если хотите сами потренироваться в оптимизации, то попробуйте вычислить число Пи:
интеграл для вычисления числа Pi

Ниже приведен «плохой» код.
long N = 10000000;
double dx, sum, x;
sum = 0.0;
x = 0.0;
dx = 1.0 / (double) N;
for (long i = 0; i < N; i++){
 sum += 4.0 / (1.0 + x * x);
 x += dx;
}
double pi = dx * sum;

О чем я не рассказал: о векторизации вычислений (инструкции SSE); о prefetch'ах, облегчающих работу с памятью. Если будут люди «которым интересно», то напишу отдельную статью про векторизацию циклов.

Подсветка исходных кодов Source Code Highlighter.
@icc
карма
75,7
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (61)

  • 0
    Отлично. Заставляет пересмотреть написание циклов в лоб. Для нахождения числа Пи, думаю, можно применить сначала разрезание а потом развёртку.
    Хотелось бы и дальше видеть Ваши статьи по оптимизации на Хабре.
    • 0
      В первую очередь — вынести из цикла инвариатны, в формуле не зря «4» стоит до интеграла.
    • 0
      Блин, не то написал, конечно имел в виду Разделение и Развёртку.
  • +1
    Как насчет примеров с числами? Насколько эффективны подобные оптимизации, например, на современных двух/четырех-ядерных процессорах?
    • +1
      Через некоторое время выложу таблицу для примера с числом Пи.
    • 0
      Нет разницы в процессорах, если после оптимизации скорость изменяется в процентном соотношении. +20% это всегда +20%. И на Celeron и на Core i7.
      • +4
        Нет, так как новые процессоры могут иметь более качественные внутренние оптимизации, на которых ручные оптимизации могут давать меньший прирост.
      • +6
        Вы очень неправы, под NetBurst ядро(pentum 4) я оптимизировал однажды софтину, сделал ~60% прироста. Недавно запустил тесты на Core 2 и обнаружил 0-5% торможения оптимизированной версии против лобовой. Может как-нибудь напишу об этом развёрнуто.
        • 0
          Напишите, плз, будет интересно почитать.
    • +4
      Какая разница, сколько у процессора ядер? Цикл все с ядра на ядро не перепрыгнет. Оптимизации все так же эффективны, но прирост дало бы разбиение цикла на несколько нитей, выполняемых параллельно.
      • –1
        Я сначала так и думал, но почитал статью и передумал. Не понимаю, что имеется в виду под «исполняющими устройствами»
  • 0
    Спасибо, узнал много нового — постараюсь выполнять данные методики на практике (в случаях, когда это нужно)
  • +1
    С разрезанием странный пример — введение временной переменной на этой же итерации не поможет сократить количество необходимых регистров. В случае с gcc временная переменная повлияет только на название операнда в SSA (static single assignment) — вместо сделанного автоматически будет tmp.
    • 0
      Тоже не понял о чем речь. Может имеется в виду замена x[i] + d[i] * x[i] на (d[i] + 1) * x[i], но почему это называется разрезанием не понятно.
  • 0
    >>>for (int i = 0; i < iN; i+=3){
    res *= a[i];
    res *= a[i+1];
    res *= a[i+2];
    }
    • 0
      не помогло, ладно, а так:

      for (int i = 0; i < iN-(iN%3); i+=3){
      res *= a[i];
      res *= a[i+1];
      res *= a[i+2];
      }
      for (int i = iN-(iN%3); i < iN; i++)
      res *= a[i];
      • 0
        %3 вычислять вообще очень плохая идея. Лучше вычислять &3 и &~3 (т.е. по модулю 4).
        • +1
          >>%3 вычислять вообще очень плохая идея. Лучше вычислять &3 и &~3 (т.е. по модулю 4).
          это «вычисляется вообще» один раз и для счётчика потянет.
          Но, для понимания for (int i = 0; i < iN-(iN%3); i+=3) лучше и ваше for (int i = 0; i < iN-(iN&~3); i+=4 ) это для 4-х кратного разворота
          • 0
            На самом деле, про понимание ещё спорный вопрос:
            for (int i = 0; i < iN & ~3; i += 4) { посчитали осн. часть; }
            for (int i = 0; i < iN & 3; ++i) { посчитали оставшуюся; }
            • 0
              @автор: в первой таблице исходника, где «после» и «после №2» исправьте бред.

              @borisko: вы привели пример 4х кратного разворота, я указывал на 3х кратной, который использовал автор. Более того ваш пример — еще больший бред.
              Может так:
              for (int i = 0; i < iN & ~3; i += 4) { посчитали осн. часть; }
              for (int i = iN & ~3; i < iN; ++i) { посчитали оставшуюся; }
              • 0
                Скажите, чему равно "(iN & ~3) + (iN & 3)"?
                • 0
                  iN.
                  ?
                  • 0
                    да, это я к тому что число итераций будет верно, просто я не заметил что borisko от 0 считает второй цикл. Сорри. Ваш цикл правильней.
                    • 0
                      Ну, можно и его цикл сделать правильным, для этого на месте «посчитали оставшуюся» проводить операции над массивом со сдвигом.
                      • 0
                        Лучше в вашем варианте объявление int i вынести вне циклов и тогда не нужно лишнего присваивания :) Только зачем это все, если за нас это компилятор сделает?
                • 0
                  Хотя да, начинать от нуля ошибка по-любому. Беру слова обратно
  • –3
    Интересная статья, Спасибо.
    Еще можно упомянуть про разницу
    for(int i = 0; i < iN; i++){
    и
    for(int i = 0; i < iN; ++i){
    По этому поводу тоже была хорошая статья на Хабре.
    • +1
      Если когда-то разница была, то сейчас все нормальные компиляторы сделают из этого одинаковый код.
    • +3
      Для int разницы не будет. Будет разница для кастомных классов.
  • +5
    В начале таких статей всегда должен быть эпиграф: «Преждевременная оптимизация — корень всех бед».
    • +1
      А в конце — «Преждевременная пессимизация — не меньшее зло»
      • +1
        А в середине «принцип Парето». На 20% методов программы приходится 80% времени её выполнения.
  • 0
    Следовало бы упомянуть об устройстве Даффа — en.wikipedia.org/wiki/Duff%27s_device.
    • 0
      Исправил линк — en.wikipedia.org/wiki/Duff%27s_device
      Устройство использует технику раскручивания цикла для оптимизации последовательного копирования.
      В общих чертах выглядит вот так:

      strcpy(to, from, count)
      register char *to, *from;
      register count;
      {
      register n = (count + 7) / 8;
      if (!count) return;
      switch (count % 8) {
      case 0: do { *to = *from++;
      case 7: *to = *from++;
      case 6: *to = *from++;
      case 5: *to = *from++;
      case 4: *to = *from++;
      case 3: *to = *from++;
      case 2: *to = *from++;
      case 1: *to = *from++;
      } while (--n > 0);
      }
      }
      • 0
        На современных машинах копировать побайтово вредно. Нужно копировать как можно большими словами, а небольшой остаток — так уж и быть, побайтово.
        • 0
          Согласен, идея все таки старая (1983 год). Хотелось просто показать немножко другой способ оформления раскрутки цикла.
        • 0
          Кстати, значение слова «word» тоже поменялось, похоже с переходом на 32-битные машины. По крайней мере в winapi DWORD всегда 32 бита, в не зависимости от архитектуры, при этом DWORD_PTR всего 32 и 64 бита на 32 и 64-битных машинах соответственно!
          • 0
            Слово — целое число естественного размера для данной машины и его размер не меняется со временем, он зависит от машины. Например, сегодня есть машины с размером слов 8, 16, (микроконтроллеры и эмбеддед) 32, 64, (эмбеддед и десктоп) и кто-его-знает-сколько-бит в DSP процессорах.
            • 0
              Да, но сейчас когда говорят «слово» обычно подразумевают размер в два байта, тоесть 16 бит. Я привел пример из WINAPI, там двойное слово 32 бита. Возможно ассемблерщики в курсе, но большинство десктопщиков по умолчанию считают, что длинна слова равна 16 бит.
              • +1
                Видимо так считают только WinAPI программисты, потому что в стандарте языка этих глупых typedef'ов нет.
                • +1
                  Посмотрел: ситуация аналогична в MASM и FASM. И хорошо что таких глупостей нет в стандарте C
                  • 0
                    MASM и FASM x86-only, им можно.
                    • 0
                      Они оба с поддержкой AMD64.
                      Вот реритетная цитата, книжицу откопал:
                      «Процессор в PC и в совместимых моделях использует 16-битовую архитектуру, поэтому он имеет доступ к 16-битовым значениям как в памяти, так и в регистрах. Шестнадцатибитовое (двухбайтовое) поле называется словом» © Язык ассемблера для IBM PC/П.Абель, 1992
                      Вот еще:
                      «Несмотря на то, что микропроцессор 80386 является 32-разрядным, наибольшая эффективность достигается в нем при обработке 16-разрядных данных. Два объединенных байта образуют слово.» © Микропроцессор 80386б/К.Паппас, У.Марри, 1993
                      • 0
                        x86 = IA-32 + Intel 64 :)
      • +1
        Устройство Даффа уже не является оптимизацией копирования. Это скорее оптимизация количества строк, которые займет раскрученный вручную цикл. А для современных компиляторов такое «устройство» даже может быть вредным (т.к. имеет очень сложный граф управления). Как пример: «When numerous instances of Duff's device were removed from the XFree86 Server in version 4.0, there was an improvement in performance»
  • +1
    Неужели те же gcc и icc не делают всего этого автоматически в -02 \ -03?
    • 0
      Делают, но компилятору трудно предсказать, когда оптимизировать можно, а когда нет. Надёжнее всё делать самому.
  • 0
    А в C# такие действия имеют смысл?
    • +1
      перестроение цикла, чтобы попадать в L2, имеет смысл совершенно точно. и вынесение инвариантов.

      с остальными нужно пробовать.
  • 0
    >>>for (int j = 0; j < jN; j++){
    for (int k = 0; k < kN; k++){
    for (int m = 0; m < mN; m++){
    i = j * k + m;
    a[i] = b[i] * c[i] + f[i]/e[i]+ x[i] — y[i] +
    z[i]/r[i] + d[i] * x[i];
    }
    }
    }
    А здесь может так:
    for (int j = 0; j < jN; j++){
    for (int k = 0; k < kN; k++){
    for (int m = 0; m < mN; m++){
    i = j * kN + k * mN + m;
    a[i] = b[i] * c[i] + f[i]/e[i]+ x[i] — y[i] +
    z[i]/r[i] + d[i] * x[i];
    }
    }
    }
  • 0
    о каком языке программирования идёт речь?
    • 0
      В тегах написано.
      • 0
        это был риторический вопрос…
    • +1
      Причём тут язык вообще?
  • +1
    >>Доступ к памяти с большим шагом еще больше замедляет программу.
    Предлагаю определить что значит «большой шаг».

    Все ок, до тех пор пока вы не начнете выходить за пределы страницы (4К на обычных системах). В общем случае имеет смысл:
    а) Утилизация обращений к памяти. Читается всегда кэшлайн (64байта), если вы работаете с float и идете со страйдом у вас часть кэшлинии получается ненужный мусор;
    б) Эффективность префетчера. Хардварный префетчер хорошо распознает обычную загрузку с постоянным страйдом. Но — префетчер отключается в случае выхода за границу страницы (иначе возникнет TLB-miss, а это долго и сложно обработать).

    >> вынесите из цикла все переменные, которые в нем не изменяются.
    Это настолько тривиальная оптимизация, что в большинстве случаев можно «не париться» ухудшая, например, читабельность программы.

    и немного про раскрутку цикла…
    В современных процессорах небольшие циклы хорошо детектируются и сохраняются во внутреннем буфере уже после стадии декодировния. Это т.н. loop stream detector (LSD :) Если раскрутить такой цикл он может не влезть в буфер и получится замедление
  • +2
    Но, если это невозможно нужно постараться облегчить работу модулю предсказания переходов. Для этого разместите наиболее вероятные ветви в начале ветвления

    Не факт, что компилятор оставит порядок ветвлений в нетронутом состоянии. Лучше для этого использовать встроенные возможности компилятора. У gcc и clang, например, есть специальный встроенный макрос __builtin_expect:

    #if defined(__GNUC__) || defined(__clang__) /* Так можно определять наличие макроса,
                                                 * но лучше это делать с помощью cmake/autoconf */
     #define COMPILER_HAVE_BUILTIN_EXPECT 1
    #endif
    
    #ifdef COMPILER_HAVE_BUILTIN_EXPECT
     #define likely(X) __builtin_expect((X), 1)
     #define unlikely(X) __builtin_expect((X), 0)
    #else
     #define likely(X) (X)
     #define unlikely(X) (X)
    #endif
    
    
    for (i = 0;; i++)
     if (unlikely(i % 1000 == 0))
     {
       /* Менее вероятный переход */
     }
     else
     {
       /* Более вероятный переход */
     }
    
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Компилятор: «Обо всём этом должен заботиться программист! Если программисту класть на это — он плохой, негодный программист; руки бы ему оторвать».
      • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      К сожалению, это несбыточная мечта. Чтобы принять соответствующие решения — компилятор должен думать как программист, а это уже ИИ.

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