Увеличение скорости путем разделения цикла
ну, например, если у тебя на каждом такте будет что-то вроде АГИ — использование только что вычесленного значения, хотя оптимизатор это может выправить анроллом, но не факт.
ну, например, если у тебя на каждом такте будет что-то вроде АГИ — использование только что вычесленного значения, хотя оптимизатор это может выправить анроллом, но не факт.
Правильно ли я понял, что такой цикл лучше подойдет для разбиения?
xr = 1.0;
for(j=1;j<=10000;j++) {
xr += x1[j]*y1[j]*xr;
xr += x2[j]*y2[j]*xr;
xr += x3[j]*y3[j]*xr;}
ну, например, если у тебя на каждом такте будет что-то вроде АГИ — использование только что вычесленного значения, хотя оптимизатор это может выправить анроллом, но не факт.
В том то и дело, что у меня бывают хитрые циклы с условиями if, которые оптимизатор не разрулит. Поэтому мне нужно самому все оптимально писать.
без оптимизации, обычно, сравнивать бессмысленно, т.к. в этом случае, компилятор не обязан делать даже простейшие оптимизации (хранение в регистрах, а не в памяти, обращение через одну инструкцию, а не через две и т.д.)
например, в данном случае компилятор может переменную x запихать в память, а не в регистр.
например, в данном случае компилятор может переменную x запихать в память, а не в регистр.
без оптимизации, обычно, сравнивать бессмысленно, т.к. в этом случае, компилятор не обязан делать даже простейшие оптимизации (хранение в регистрах, а не в памяти, обращение через одну инструкцию, а не через две и т.д.)
например, в данном случае компилятор может переменную x запихать в память, а не в регистр.
Я про это как-то и не подумал, спасибо. Но оптимизацию я специально выключал, чтобы первый цикл оптимизатор не трогал. Наверное прийдется искать настройки оптимизатора...
проще включить всю оптимизацию (не разбираясь с отдельными настройками и просмотреть ассемблерный листинг - сгенерилось то, что хотелось, или нет
проще включить всю оптимизацию (не разбираясь с отдельными настройками и просмотреть ассемблерный листинг - сгенерилось то, что хотелось, или нет
Если б я еще и в ассемблере что-то понимал - было бы вообще хорошо.
Может есть какие-нибудь книжки по проблемам низкоуровневой оптимизации вычислений?
Вот передо мной доклад одного программиста (комментарии от него я не могу получить в котором есть такая фраза по поводу разкрытия циклов: "Why new code is faster? Each loop iteration uses only two data streams!"
Что это могут быть за "data streams"?
Вот передо мной доклад одного программиста (комментарии от него я не могу получить в котором есть такая фраза по поводу разкрытия циклов: "Why new code is faster? Each loop iteration uses only two data streams!"
Что это могут быть за "data streams"?
тебе кстати необходимо код оптимизировать вообще для произвольного использования? или под конкретную машину/процессор?
У меня в программе есть критические по скорости выполнения части, которые, нужно оптимизировать под конкретный проц.
тогда по хорошему надо ботать asm и архитектуру данного конкретного проца.
data streams - это скорее всего имелись ввиду конвейеры процессора.
data streams - это скорее всего имелись ввиду конвейеры процессора.
Ботать asm конечно нужно.
Но пока я с циклами так и не разобрался.
Но пока я с циклами так и не разобрался.
почитай доки по block-prefetch. лучше с оффсайтов интела/амд
Вот передо мной доклад одного программиста (комментарии от него я не могу получить в котором есть такая фраза по поводу разкрытия циклов: "Why new code is faster? Each loop iteration uses only two data streams!"массивы данных
Что это могут быть за "data streams"?
последовательный доступ к двум блокам оперативной памяти процу (почти любому) легче оптимизировать, чем для трех и более массивов.
Уррра! Я получил пример удачного раскрытия цикла. Причем автоматически оптимизатор не смог это сделать (наверно, так как ассемблерный листинг я не смотрел). Вот код:
testdot - это простое перемножение двух векторов (здесь размера 100000)
Вариант 1:
---------------------------------
xr = 0.0;
for(k=1;k<10;k++) {
xr += x4[k]*testdot(100000, x1, y1);
xr += x4[k]*testdot(100000, x2, y2);
xr += x4[k]*testdot(100000, x3, y3);
}
-------------------------------------------
Вариант 2:
-------------------------------------
xr = 0.0;
for(k=1;k<10;k++) {
xr += x4[k]*testdot(100000, x1, y1);
}
for(k=1;k<10;k++) {
xr += x4[k]*testdot(100000, x2, y2);
}
for(k=1;k<10;k++) {
xr += x4[k]*testdot(100000, x3, y3);}
-------------------------------------
Результаты в обоих случаях получаются одинаковые, но второй вариант примерно на 80% быстрее!
testdot - это простое перемножение двух векторов (здесь размера 100000)
Вариант 1:
---------------------------------
xr = 0.0;
for(k=1;k<10;k++) {
xr += x4[k]*testdot(100000, x1, y1);
xr += x4[k]*testdot(100000, x2, y2);
xr += x4[k]*testdot(100000, x3, y3);
}
-------------------------------------------
Вариант 2:
-------------------------------------
xr = 0.0;
for(k=1;k<10;k++) {
xr += x4[k]*testdot(100000, x1, y1);
}
for(k=1;k<10;k++) {
xr += x4[k]*testdot(100000, x2, y2);
}
for(k=1;k<10;k++) {
xr += x4[k]*testdot(100000, x3, y3);}
-------------------------------------
Результаты в обоих случаях получаются одинаковые, но второй вариант примерно на 80% быстрее!
Присоединюсь, по хорошему, нужно ботать архитектуру процессоров, про такие понятия, как конвеер команд, что регистры fpu, про sse и т.п. И без оптимизации запускать смысла не имеет, потому как иначе код может быть ужасным просто.
В чём главная разница между двумя кусками кода. В первом случае на каждом шаге цикла используется много переменных, и поэтому может возникнуть ситуация, что эти переменные просто не влезают в регистры, из-за чего будут падать скорость вычисления, что особенно актуально, если ты работает с данными вида float/double. С другой стороны, есть такое понятие, как "конвеер команд", а так же параллелизация вычислений. Дело в том, что в этих циклах ты не можешь выполнить следующий шаг цикла, не вычислив предыдущий, так как они зависят друг от друга через переменные xr/yr/zr, а в цикле с большим телом это уже менее актуально. Кроме того, процессор может выполнять несколько инструкций одновременно, но не всяких, и тоже только в случае, что данные независимы.
В чём главная разница между двумя кусками кода. В первом случае на каждом шаге цикла используется много переменных, и поэтому может возникнуть ситуация, что эти переменные просто не влезают в регистры, из-за чего будут падать скорость вычисления, что особенно актуально, если ты работает с данными вида float/double. С другой стороны, есть такое понятие, как "конвеер команд", а так же параллелизация вычислений. Дело в том, что в этих циклах ты не можешь выполнить следующий шаг цикла, не вычислив предыдущий, так как они зависят друг от друга через переменные xr/yr/zr, а в цикле с большим телом это уже менее актуально. Кроме того, процессор может выполнять несколько инструкций одновременно, но не всяких, и тоже только в случае, что данные независимы.
Результаты в обоих случаях получаются одинаковые, но второй вариант примерно на 80% быстрее!Думаю, ту сложнее ситуация, чем просто с разворачиванием циклов. Дело в том, что основная вычислительная работа идёт в testdot, поэтому накладные расходы на сам цикл минимальны. Единственная правдоподобная гипотеза, которая у меня есть, состоит в том, что ты упираешься в нехватку кеш-памяти. Попробуй протестируй свой пример, когда первый параметр у testdot будет другим, от 1000 до 1000000.
Поменял размер векторов на 1000. В L2 все вместе стало легко влазить. Прирост в скорости составил всего 5%.
Но в моих задачках почти никогда массивы не лезут целиком в L2, каким бы он ни был.
Но в моих задачках почти никогда массивы не лезут целиком в L2, каким бы он ни был.
Тогда при оценке того, стоит ли или нет пытаться делать какую-либо оптимизацию следует думать именно о том, что в конкретном случае происходит с кешем, и какие действия могут изменить ситуацию. Можно придумать пример, где именно за счёт кеша код с одним циклом будет работать значительно быстрее. Потому обобщать на "разбиение циклов" смысла не имеет, такое обобщение некорректно. Чему-то разбиение помогает, чему-то оно мешает. О кеше, imho, помнить действительно полезно, свойства кеша часто сказываются, и устроен он на всех процессорах примерно одинаково.
Но в моих задачках почти никогда массивы не лезут целиком в L2, каким бы он ни был.Кстати, возможно стоит изменить алгоритм. Если ты перемножаешь большие матрицы, скажем, то они тоже целиком в кеш не влезают, поэтому пользуются алгоритмами блочного перемножения, которые дают прирост производительности в несколько раз.
В общем я потестировал разные размеры векторов и понял, что если все вектора одновременно помещаются в L2, то никакого достоверного ускорения от второго варианта нет. А вот как только все сразу перестает вмещаться в L2 - то скорость второго варианта растет и улучшеное может достигать примерно 80%. Но! Как только два (а не шесть) массива перестают вмещаться в L2 - опять два вариант одинаковы по скорости!
Т.е. как я понимаю здесь дело исключительно в том, вмещаются ли все данные цикла в L2.
Т.е. как я понимаю здесь дело исключительно в том, вмещаются ли все данные цикла в L2.
Кстати, возможно стоит изменить алгоритм. Если ты перемножаешь большие матрицы, скажем, то они тоже целиком в кеш не влезают, поэтому пользуются алгоритмами блочного перемножения, которые дают прирост производительности в несколько раз.
Я думаю так и сделать. Т.е. при старте программы проверять количество кеша, а потом выбирать тот или иной алгоритм (способ разбиения).
а если testdot вынести за цикл и сохранить его значение в отдельной переменной - во сколько раз будет прирост скорости? 
а если testdot вынести за цикл и сохранить его значение в отдельной переменной - во сколько раз будет прирост скорости?
Ну епт.
Это же только тестовый пример. Не важно что там в testdot, главное чтобы оно лезло в L2 целиком.Рекомендуется почитать
http://www.citforum.ru/book/optimize/
Мое краткое резюме:
1) Факторов скорости дофига.
Насколько данные помещаются в кэш (какого уровня?). Следует учесть принципы адресации. Мегабайтовый кэш может и на 512k переполнится.
Насколько набор команд (тело цикла влезает в коммандный кэш
Что происходит с конвейером при переходе на следующую итерацию цикла (или мб компилятор раскрыл цикл?)
По каким адресам лезешь в оперативку? В какие блоки попадаешь? Выравнивание?
Правильно ли организована предвыборка?
Что удается хранить в регистрах?
Насколько эффективен механизм виртуальной памяти, стратегия размещения страниц?
Насколько ты чередуешь целочисленные операции и операции с плавающей точкой (они могут выполняться параллельно)
2) Хрен ты все эти факторы заботаешь, поэтому
Пиши нормальный понятный код, выбрав достаточно быстрый алгоритм (qsort vs пузырек)
Компилируй хорошим оптимизирующим компилятором
Профилируй и экспериментируй
http://www.citforum.ru/book/optimize/
Мое краткое резюме:
1) Факторов скорости дофига.
Насколько данные помещаются в кэш (какого уровня?). Следует учесть принципы адресации. Мегабайтовый кэш может и на 512k переполнится.
Насколько набор команд (тело цикла влезает в коммандный кэш
Что происходит с конвейером при переходе на следующую итерацию цикла (или мб компилятор раскрыл цикл?)
По каким адресам лезешь в оперативку? В какие блоки попадаешь? Выравнивание?
Правильно ли организована предвыборка?
Что удается хранить в регистрах?
Насколько эффективен механизм виртуальной памяти, стратегия размещения страниц?
Насколько ты чередуешь целочисленные операции и операции с плавающей точкой (они могут выполняться параллельно)
2) Хрен ты все эти факторы заботаешь, поэтому
Пиши нормальный понятный код, выбрав достаточно быстрый алгоритм (qsort vs пузырек)
Компилируй хорошим оптимизирующим компилятором
Профилируй и экспериментируй
Оставить комментарий
domor
Известно, что в некоторых случаях скорость выполнения цикла можно повысить путем его разбиения на несколько более простых циклов. Может мне кто-нибудь показать РЕАЛЬНЫЙ пример такой оптимизации?Я пробовал сравнивать такие варианты:
-------------------------------------
for(j=1;j<=10000;j++) {
xr += x1[j]*y1[j];
yr += x2[j]*y2[j];
zr += x3[j]*y3[j];}
-------------------------------------
и
-------------------------------------
for(j=1;j<=10000;j++) {
xr += x1[j]*y1[j];}
for(j=1;j<=10000;j++) {
yr += x2[j]*y2[j];}
for(j=1;j<=10000;j++) {
zr += x3[j]*y3[j];}
-------------------------------------
Скорость выполнения замерялась несколько раз (для воспроизводимости) по clock.
Скомпилировал MVC 8 без оптимизации.
Вопреки ожиданиям второй вариант несколько (20-30%) медленнее первого (хотя это можно понять - сложений по индексу больше). Размеры массивов x1, y1...,x3, y3 я брал разные, чтобы они вмещались/не вмещались в L2 кеш - все равно второй вариант хуже.
OpenWatcom 1.5 без оптимизации дает второй вариант чуть быстрее (на 5%).
Какие будут комментарии? И может ли кто-то показать пример где разбиение цикла дает большой прирост в скорости?