Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 61
Отлично. Заставляет пересмотреть написание циклов в лоб. Для нахождения числа Пи, думаю, можно применить сначала разрезание а потом развёртку.
Хотелось бы и дальше видеть Ваши статьи по оптимизации на Хабре.
Хотелось бы и дальше видеть Ваши статьи по оптимизации на Хабре.
Как насчет примеров с числами? Насколько эффективны подобные оптимизации, например, на современных двух/четырех-ядерных процессорах?
Через некоторое время выложу таблицу для примера с числом Пи.
Нет разницы в процессорах, если после оптимизации скорость изменяется в процентном соотношении. +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.
>>>for (int i = 0; i < iN; i+=3){
res *= a[i];
res *= a[i+1];
res *= a[i+2];
}
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];
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-(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) { посчитали оставшуюся; }
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) { посчитали оставшуюся; }
@borisko: вы привели пример 4х кратного разворота, я указывал на 3х кратной, который использовал автор. Более того ваш пример — еще больший бред.
Может так:
for (int i = 0; i < iN & ~3; i += 4) { посчитали осн. часть; }
for (int i = iN & ~3; i < iN; ++i) { посчитали оставшуюся; }
Интересная статья, Спасибо.
Еще можно упомянуть про разницу
for(int i = 0; i < iN; i++){
и
for(int i = 0; i < iN; ++i){
По этому поводу тоже была хорошая статья на Хабре.
Еще можно упомянуть про разницу
for(int i = 0; i < iN; i++){
и
for(int i = 0; i < iN; ++i){
По этому поводу тоже была хорошая статья на Хабре.
В начале таких статей всегда должен быть эпиграф: «Преждевременная оптимизация — корень всех бед».
Следовало бы упомянуть об устройстве Даффа — en.wikipedia.org/wiki/Duff%27s_device.
Исправил линк — 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 x86-only, им можно.
Они оба с поддержкой AMD64.
Вот реритетная цитата, книжицу откопал:
«Процессор в PC и в совместимых моделях использует 16-битовую архитектуру, поэтому он имеет доступ к 16-битовым значениям как в памяти, так и в регистрах. Шестнадцатибитовое (двухбайтовое) поле называется словом» © Язык ассемблера для IBM PC/П.Абель, 1992
Вот еще:
«Несмотря на то, что микропроцессор 80386 является 32-разрядным, наибольшая эффективность достигается в нем при обработке 16-разрядных данных. Два объединенных байта образуют слово.» © Микропроцессор 80386б/К.Паппас, У.Марри, 1993
Вот реритетная цитата, книжицу откопал:
«Процессор в PC и в совместимых моделях использует 16-битовую архитектуру, поэтому он имеет доступ к 16-битовым значениям как в памяти, так и в регистрах. Шестнадцатибитовое (двухбайтовое) поле называется словом» © Язык ассемблера для IBM PC/П.Абель, 1992
Вот еще:
«Несмотря на то, что микропроцессор 80386 является 32-разрядным, наибольшая эффективность достигается в нем при обработке 16-разрядных данных. Два объединенных байта образуют слово.» © Микропроцессор 80386б/К.Паппас, У.Марри, 1993
Устройство Даффа уже не является оптимизацией копирования. Это скорее оптимизация количества строк, которые займет раскрученный вручную цикл. А для современных компиляторов такое «устройство» даже может быть вредным (т.к. имеет очень сложный граф управления). Как пример: «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# такие действия имеют смысл?
>>>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];
}
}
}
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 :) Если раскрутить такой цикл он может не влезть в буфер и получится замедление
Предлагаю определить что значит «большой шаг».
Все ок, до тех пор пока вы не начнете выходить за пределы страницы (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
{
/* Более вероятный переход */
}
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Введение в технику оптимизации циклов