Как стать автором
Обновить

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

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

@borisko: вы привели пример 4х кратного разворота, я указывал на 3х кратной, который использовал автор. Более того ваш пример — еще больший бред.
Может так:
for (int i = 0; i < iN & ~3; i += 4) { посчитали осн. часть; }
for (int i = iN & ~3; i < iN; ++i) { посчитали оставшуюся; }
Скажите, чему равно "(iN & ~3) + (iN & 3)"?
iN.
?
да, это я к тому что число итераций будет верно, просто я не заметил что borisko от 0 считает второй цикл. Сорри. Ваш цикл правильней.
Ну, можно и его цикл сделать правильным, для этого на месте «посчитали оставшуюся» проводить операции над массивом со сдвигом.
Лучше в вашем варианте объявление int i вынести вне циклов и тогда не нужно лишнего присваивания :) Только зачем это все, если за нас это компилятор сделает?
Хотя да, начинать от нуля ошибка по-любому. Беру слова обратно
Интересная статья, Спасибо.
Еще можно упомянуть про разницу
for(int i = 0; i < iN; i++){
и
for(int i = 0; i < iN; ++i){
По этому поводу тоже была хорошая статья на Хабре.
Если когда-то разница была, то сейчас все нормальные компиляторы сделают из этого одинаковый код.
Для int разницы не будет. Будет разница для кастомных классов.
В начале таких статей всегда должен быть эпиграф: «Преждевременная оптимизация — корень всех бед».
А в конце — «Преждевременная пессимизация — не меньшее зло»
А в середине «принцип Парето». На 20% методов программы приходится 80% времени её выполнения.
Исправил линк — 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);
}
}
На современных машинах копировать побайтово вредно. Нужно копировать как можно большими словами, а небольшой остаток — так уж и быть, побайтово.
Согласен, идея все таки старая (1983 год). Хотелось просто показать немножко другой способ оформления раскрутки цикла.
Кстати, значение слова «word» тоже поменялось, похоже с переходом на 32-битные машины. По крайней мере в winapi DWORD всегда 32 бита, в не зависимости от архитектуры, при этом DWORD_PTR всего 32 и 64 бита на 32 и 64-битных машинах соответственно!
Слово — целое число естественного размера для данной машины и его размер не меняется со временем, он зависит от машины. Например, сегодня есть машины с размером слов 8, 16, (микроконтроллеры и эмбеддед) 32, 64, (эмбеддед и десктоп) и кто-его-знает-сколько-бит в DSP процессорах.
Да, но сейчас когда говорят «слово» обычно подразумевают размер в два байта, тоесть 16 бит. Я привел пример из WINAPI, там двойное слово 32 бита. Возможно ассемблерщики в курсе, но большинство десктопщиков по умолчанию считают, что длинна слова равна 16 бит.
Видимо так считают только WinAPI программисты, потому что в стандарте языка этих глупых typedef'ов нет.
Посмотрел: ситуация аналогична в MASM и FASM. И хорошо что таких глупостей нет в стандарте C
MASM и FASM x86-only, им можно.
Они оба с поддержкой AMD64.
Вот реритетная цитата, книжицу откопал:
«Процессор в PC и в совместимых моделях использует 16-битовую архитектуру, поэтому он имеет доступ к 16-битовым значениям как в памяти, так и в регистрах. Шестнадцатибитовое (двухбайтовое) поле называется словом» © Язык ассемблера для IBM PC/П.Абель, 1992
Вот еще:
«Несмотря на то, что микропроцессор 80386 является 32-разрядным, наибольшая эффективность достигается в нем при обработке 16-разрядных данных. Два объединенных байта образуют слово.» © Микропроцессор 80386б/К.Паппас, У.Марри, 1993
x86 = IA-32 + Intel 64 :)
Устройство Даффа уже не является оптимизацией копирования. Это скорее оптимизация количества строк, которые займет раскрученный вручную цикл. А для современных компиляторов такое «устройство» даже может быть вредным (т.к. имеет очень сложный граф управления). Как пример: «When numerous instances of Duff's device were removed from the XFree86 Server in version 4.0, there was an improvement in performance»
Неужели те же gcc и icc не делают всего этого автоматически в -02 \ -03?
Делают, но компилятору трудно предсказать, когда оптимизировать можно, а когда нет. Надёжнее всё делать самому.
А в C# такие действия имеют смысл?
перестроение цикла, чтобы попадать в L2, имеет смысл совершенно точно. и вынесение инвариантов.

с остальными нужно пробовать.
>>>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];
}
}
}
о каком языке программирования идёт речь?
В тегах написано.
это был риторический вопрос…
НЛО прилетело и опубликовало эту надпись здесь
>>Доступ к памяти с большим шагом еще больше замедляет программу.
Предлагаю определить что значит «большой шаг».

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

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

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

Не факт, что компилятор оставит порядок ветвлений в нетронутом состоянии. Лучше для этого использовать встроенные возможности компилятора. У 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
 {
   /* Более вероятный переход */
 }
НЛО прилетело и опубликовало эту надпись здесь
Компилятор: «Обо всём этом должен заботиться программист! Если программисту класть на это — он плохой, негодный программист; руки бы ему оторвать».
НЛО прилетело и опубликовало эту надпись здесь
К сожалению, это несбыточная мечта. Чтобы принять соответствующие решения — компилятор должен думать как программист, а это уже ИИ.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.