icc Jul 29 2011 at 14:52

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

4 min

58K

Programming*

+94

Comments 61

daspisch Jul 29 2011 at 15:10

Отлично. Заставляет пересмотреть написание циклов в лоб. Для нахождения числа Пи, думаю, можно применить сначала разрезание а потом развёртку.
Хотелось бы и дальше видеть Ваши статьи по оптимизации на Хабре.

LeiTZ Jul 29 2011 at 16:46

В первую очередь — вынести из цикла инвариатны, в формуле не зря «4» стоит до интеграла.

daspisch Jul 29 2011 at 16:47

Блин, не то написал, конечно имел в виду Разделение и Развёртку.

ckald Jul 29 2011 at 15:13

Как насчет примеров с числами? Насколько эффективны подобные оптимизации, например, на современных двух/четырех-ядерных процессорах?

icc Jul 29 2011 at 15:27

Через некоторое время выложу таблицу для примера с числом Пи.

NiGHt_LEshiY Jul 29 2011 at 16:28

Нет разницы в процессорах, если после оптимизации скорость изменяется в процентном соотношении. +20% это всегда +20%. И на Celeron и на Core i7.

borisko Jul 29 2011 at 16:45

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

Aquahawk Jul 29 2011 at 17:31

Вы очень неправы, под NetBurst ядро(pentum 4) я оптимизировал однажды софтину, сделал ~60% прироста. Недавно запустил тесты на Core 2 и обнаружил 0-5% торможения оптимизированной версии против лобовой. Может как-нибудь напишу об этом развёрнуто.

susl Jul 29 2011 at 21:12

Напишите, плз, будет интересно почитать.

UFO just landed and posted this here

ckald Jul 29 2011 at 17:15

Я сначала так и думал, но почитал статью и передумал. Не понимаю, что имеется в виду под «исполняющими устройствами»

lnv Jul 29 2011 at 17:43

Полагаю, что под «исполняющими устройствами» имеется в виду это: www.ixbt.com/cpu/cpu-digest-2009.shtml#33

DeXPeriX Jul 29 2011 at 15:57

Спасибо, узнал много нового — постараюсь выполнять данные методики на практике (в случаях, когда это нужно)

LeiTZ Jul 29 2011 at 16:35

С разрезанием странный пример — введение временной переменной на этой же итерации не поможет сократить количество необходимых регистров. В случае с gcc временная переменная повлияет только на название операнда в SSA (static single assignment) — вместо сделанного автоматически будет tmp.

HhyperR Jul 29 2011 at 18:32

Тоже не понял о чем речь. Может имеется в виду замена x[i] + d[i] * x[i] на (d[i] + 1) * x[i], но почему это называется разрезанием не понятно.

infreerat Jul 29 2011 at 16:43

>>>for (int i = 0; i < iN; i+=3){
res *= a[i];
res *= a[i+1];
res *= a[i+2];
}

infreerat Jul 29 2011 at 17:52

не помогло, ладно, а так:

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];

borisko Jul 29 2011 at 17:55

%3 вычислять вообще очень плохая идея. Лучше вычислять &3 и &~3 (т.е. по модулю 4).

infreerat Jul 29 2011 at 18:04

>>%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-х кратного разворота

borisko Jul 29 2011 at 18:16

На самом деле, про понимание ещё спорный вопрос:
for (int i = 0; i < iN & ~3; i += 4) { посчитали осн. часть; }
for (int i = 0; i < iN & 3; ++i) { посчитали оставшуюся; }

infreerat Jul 29 2011 at 18:27

@автор: в первой таблице исходника, где «после» и «после №2» исправьте бред.

@borisko: вы привели пример 4х кратного разворота, я указывал на 3х кратной, который использовал автор. Более того ваш пример — еще больший бред.
Может так:
for (int i = 0; i < iN & ~3; i += 4) { посчитали осн. часть; }
for (int i = iN & ~3; i < iN; ++i) { посчитали оставшуюся; }

susl Jul 29 2011 at 21:18

Скажите, чему равно "(iN & ~3) + (iN & 3)"?

infreerat Jul 29 2011 at 21:24

iN.
?

susl Jul 29 2011 at 21:27

да, это я к тому что число итераций будет верно, просто я не заметил что borisko от 0 считает второй цикл. Сорри. Ваш цикл правильней.

infreerat Jul 29 2011 at 21:36

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

susl Jul 29 2011 at 21:39

Лучше в вашем варианте объявление int i вынести вне циклов и тогда не нужно лишнего присваивания :) Только зачем это все, если за нас это компилятор сделает?

susl Jul 29 2011 at 21:26

Хотя да, начинать от нуля ошибка по-любому. Беру слова обратно

karbachinsky Jul 29 2011 at 16:58

Интересная статья, Спасибо.
Еще можно упомянуть про разницу
for(int i = 0; i < iN; i++){
и
for(int i = 0; i < iN; ++i){
По этому поводу тоже была хорошая статья на Хабре.

Gumanoid Jul 29 2011 at 17:34

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

borisko Jul 29 2011 at 17:56

Для int разницы не будет. Будет разница для кастомных классов.

agorkov Jul 29 2011 at 17:16

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

CKOPOBAPKuH Jul 29 2011 at 18:00

А в конце — «Преждевременная пессимизация — не меньшее зло»

NikoM Jul 29 2011 at 18:54

А в середине «принцип Парето». На 20% методов программы приходится 80% времени её выполнения.

Catalysis Jul 29 2011 at 17:27

Следовало бы упомянуть об устройстве Даффа — en.wikipedia.org/wiki/Duff%27s_device.

Catalysis Jul 29 2011 at 18:36

Исправил линк — 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);

 }

}

gribozavr Jul 29 2011 at 18:40

На современных машинах копировать побайтово вредно. Нужно копировать как можно большими словами, а небольшой остаток — так уж и быть, побайтово.

Catalysis Jul 29 2011 at 18:56

Согласен, идея все таки старая (1983 год). Хотелось просто показать немножко другой способ оформления раскрутки цикла.

1amer Jul 29 2011 at 20:29

Кстати, значение слова «word» тоже поменялось, похоже с переходом на 32-битные машины. По крайней мере в winapi DWORD всегда 32 бита, в не зависимости от архитектуры, при этом DWORD_PTR всего 32 и 64 бита на 32 и 64-битных машинах соответственно!

gribozavr Jul 29 2011 at 20:33

Слово — целое число естественного размера для данной машины и его размер не меняется со временем, он зависит от машины. Например, сегодня есть машины с размером слов 8, 16, (микроконтроллеры и эмбеддед) 32, 64, (эмбеддед и десктоп) и кто-его-знает-сколько-бит в DSP процессорах.

1amer Jul 29 2011 at 20:39

Да, но сейчас когда говорят «слово» обычно подразумевают размер в два байта, тоесть 16 бит. Я привел пример из WINAPI, там двойное слово 32 бита. Возможно ассемблерщики в курсе, но большинство десктопщиков по умолчанию считают, что длинна слова равна 16 бит.

gribozavr Jul 29 2011 at 20:40

Видимо так считают только WinAPI программисты, потому что в стандарте языка этих глупых typedef'ов нет.

1amer Jul 29 2011 at 21:03

Посмотрел: ситуация аналогична в MASM и FASM. И хорошо что таких глупостей нет в стандарте C

gribozavr Jul 29 2011 at 21:16

MASM и FASM x86-only, им можно.

1amer Jul 29 2011 at 21:50

Они оба с поддержкой AMD64.
Вот реритетная цитата, книжицу откопал:
«Процессор в PC и в совместимых моделях использует 16-битовую архитектуру, поэтому он имеет доступ к 16-битовым значениям как в памяти, так и в регистрах. Шестнадцатибитовое (двухбайтовое) поле называется словом» © Язык ассемблера для IBM PC/П.Абель, 1992
Вот еще:
«Несмотря на то, что микропроцессор 80386 является 32-разрядным, наибольшая эффективность достигается в нем при обработке 16-разрядных данных. Два объединенных байта образуют слово.» © Микропроцессор 80386б/К.Паппас, У.Марри, 1993

gribozavr Jul 29 2011 at 21:57

x86 = IA-32 + Intel 64 :)

a5b Jul 29 2011 at 22:28

Устройство Даффа уже не является оптимизацией копирования. Это скорее оптимизация количества строк, которые займет раскрученный вручную цикл. А для современных компиляторов такое «устройство» даже может быть вредным (т.к. имеет очень сложный граф управления). Как пример: «When numerous instances of Duff's device were removed from the XFree86 Server in version 4.0, there was an improvement in performance»

Volfram Jul 29 2011 at 17:40

Неужели те же gcc и icc не делают всего этого автоматически в -02 \ -03?

VladX Jul 30 2011 at 20:47

Делают, но компилятору трудно предсказать, когда оптимизировать можно, а когда нет. Надёжнее всё делать самому.

Houston Jul 29 2011 at 19:13

А в C# такие действия имеют смысл?

CKOPOBAPKuH Jul 29 2011 at 19:25

перестроение цикла, чтобы попадать в L2, имеет смысл совершенно точно. и вынесение инвариантов.

с остальными нужно пробовать.

infreerat Jul 29 2011 at 19:58

>>>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];
}
}
}

tenshi Jul 29 2011 at 20:31

о каком языке программирования идёт речь?

HhyperR Jul 29 2011 at 22:41

В тегах написано.

tenshi Jul 30 2011 at 04:33

это был риторический вопрос…

UFO just landed and posted this here

DustCn Jul 30 2011 at 08:20

>>Доступ к памяти с большим шагом еще больше замедляет программу.
Предлагаю определить что значит «большой шаг».

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

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

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

VladX Jul 30 2011 at 21:09

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

Не факт, что компилятор оставит порядок ветвлений в нетронутом состоянии. Лучше для этого использовать встроенные возможности компилятора. У 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
 {
   /* Более вероятный переход */
 }

UFO just landed and posted this here

VladX Jul 31 2011 at 01:04

Компилятор: «Обо всём этом должен заботиться программист! Если программисту класть на это — он плохой, негодный программист; руки бы ему оторвать».

UFO just landed and posted this here

icc Jul 31 2011 at 03:39

К сожалению, это несбыточная мечта. Чтобы принять соответствующие решения — компилятор должен думать как программист, а это уже ИИ.