Comments 65
Теперь надо обновить компиляторы, чтобы препроцессор автоматом заменял пузырьки на этот метод и сделать build world тем самым оградив на год производителей железа от надобности соблюдения закона Мура
Думая, что Дядя Дима ака ddima внезапно удивится наплыву посетителей на геймдефф и свой блог :)
«Ага, скажет подкованный читатель» — привет от русских книг из серии «…для чайников»
кстати, из этой же оперы: допустим, нужно делать разные операции над двумя независимыми списками (пусть одинаковой длины).
Казалось бы — время работы будет одинаково в обоих случаях:
— сделать работу за два разных цикла (правильный программистский подход)
— объединить две операции в один цикл («говнокод»)
Так вот, говнокод будет работать ощутимо быстрее, особенно в случае linked list.
В таком случае процессор заказывает данные из памяти для элементов сразу двух списков.
Данные, которые придут раньше и будут обработаны раньше.
Фактически, списки будут обрабатываться параллельно даже на одно-ядерном процессоре из одной нитки.
А «классичекий» подход (если компилятор не перехитрит программиста), будет работать последовательно.
Казалось бы — время работы будет одинаково в обоих случаях:
— сделать работу за два разных цикла (правильный программистский подход)
— объединить две операции в один цикл («говнокод»)
Так вот, говнокод будет работать ощутимо быстрее, особенно в случае linked list.
В таком случае процессор заказывает данные из памяти для элементов сразу двух списков.
Данные, которые придут раньше и будут обработаны раньше.
Фактически, списки будут обрабатываться параллельно даже на одно-ядерном процессоре из одной нитки.
А «классичекий» подход (если компилятор не перехитрит программиста), будет работать последовательно.
По моему, во втором варианте «предсказателю будущего» будет проще принять решение еще и потому что условие выхода из вложенного цикла — сравнение с константой (да и один свободный регист в процессе оптимизации много что дает, хотя не в таком простом случае).
десятки тактов, что не так уж и много
Ни хера себе «не так уж много»! С учетом того, что за один такт процессор может исполнить более трех инструкций, если все удачно :)
Ни хера себе «не так уж много»! С учетом того, что за один такт процессор может исполнить более трех инструкций, если все удачно :)
Вообще мне кажется, что правильный вариант компилирования кода «if something then swap» не должен вообще иметь ветвления — есть специальные инструкции compare-and-swap как раз для таких случаев, специально, чтобы избежать перехода и накладных расходов на его предсказание.
В таком случае ошибки branch prediction будут очень редкими — ровно один раз за каждый выход из вложенного цикла (условный jump назад предсказывается происходящим).
В таком случае ошибки branch prediction будут очень редкими — ровно один раз за каждый выход из вложенного цикла (условный jump назад предсказывается происходящим).
Угу. На арме вот есть замечательная комманда swp{cond} ({cond} определяет условие при котором команда будет выполнятся). Сия статья заставила меня задуматся над возможным применением этой комманды :)
Ну и последнее. Оптимизация должна идти сверху вниз. Т.е. сначала выбирается оптимальный алгоритм, потом с ним уже занимаемся низкоуровненвым дрочерством. Реквстирую в пост сравнение, как работает на том же механизме qsort или вставка.
еще можно (раз уж мы тут про дрочерство) сделать loop unrolling — замена цикла на многократное повторение тела. Опять задача та же — избавление от переходов. Если N не статично, то можно сделать так:
for (int i = 0; i < N / 2; i+=2)
{
do_something(i);
do_something(i+1);
}
if (N mod 2 <> 0)
{
do_something (N);
}
еще можно (раз уж мы тут про дрочерство) сделать loop unrolling — замена цикла на многократное повторение тела. Опять задача та же — избавление от переходов. Если N не статично, то можно сделать так:
for (int i = 0; i < N / 2; i+=2)
{
do_something(i);
do_something(i+1);
}
if (N mod 2 <> 0)
{
do_something (N);
}
Попробовал для интереса переписать сортировку в один цикл, получилось вот что pastebin.com/m6c6397ca
Но в итоге, за счёт сложных вычислений, работает примерно в три раза медленнее обычной версии.
Но в итоге, за счёт сложных вычислений, работает примерно в три раза медленнее обычной версии.
А, я кстати на грабли тут как раз наступил.
Деление по модулю — оно опасное. Если компилятор поставит idiv — то будет привет, у него latency десятки тактов. Поэтому, например
может замедлить какой-нибудь простой цикл в 20 раз по сравнению с:
Деление по модулю — оно опасное. Если компилятор поставит idiv — то будет привет, у него latency десятки тактов. Поэтому, например
i=(i+1)%N;может замедлить какой-нибудь простой цикл в 20 раз по сравнению с:
i++;
if (i > N)
i = 0;
Делите на степень двойки. :)
Если ваш компилятор напишет idiv при попытке поделить на константу-степень-двойки — выкиньте его.
Если ваш компилятор напишет idiv при попытке поделить на константу-степень-двойки — выкиньте его.
В принципе, не обязательно степень двойки — умный компилятор будет оптимизировать деление и на другие константы, например, вот так выглядит деление на 123456 (MSVC):
Но я говорил скорее о случае с не-константами.
mov ecx, DWORD PTR _x$[esp+8]
mov eax, 142497619 ; 087e5753H
imul ecx
sar edx, 12 ; 0000000cH
mov ecx, edx
shr ecx, 31 ; 0000001fH
add ecx, edx
Но я говорил скорее о случае с не-константами.
Насколько я знаю, Prescott имеет длинный конвеер и ошибки предсказателя переходов для него критичны. На других процессорах, возможно, разница будет меньше. Поправьте пожалуйста, если я не прав
В целом все современные процы x86 имеют длинный конвеер. Слишком сложные инструкции.
Длина конвеера
Core 2 Duo — 14 www.overclockers.ru/lab/22660.shtml
Prescott — 31 ru.wikipedia.org/wiki/Pentium_4
Core 2 Duo — 14 www.overclockers.ru/lab/22660.shtml
Prescott — 31 ru.wikipedia.org/wiki/Pentium_4
Как минимум на E5200 и E6700 тот же самый эффект.
У вас алгоритмы не эквивалентны
В первом варианте:
проверка условия в первом цикле — N операций
проверка условия во втором цикле — (N^2-1)/2*3 операций
Во втором варианте
проверка условия в первом цикле — N-1 операций
проверка условия во втором цикле — (N^2-1)/2*1 операций
При большом N учитываем только старшую степень, общая сложность:
N^2(c+0.5) операций для второго и N^2(c+1.5) операций для первого
В первом варианте:
проверка условия в первом цикле — N операций
проверка условия во втором цикле — (N^2-1)/2*3 операций
Во втором варианте
проверка условия в первом цикле — N-1 операций
проверка условия во втором цикле — (N^2-1)/2*1 операций
При большом N учитываем только старшую степень, общая сложность:
N^2(c+0.5) операций для второго и N^2(c+1.5) операций для первого
Что-то я не понял, откуда в первом варианте *3? Если речь о N — (i+1), то компилятор его посчитает только один раз на весь внутренний цикл.
i — переменная, выражения с переменными пересчитываются на каждом проходе, так как ее значение могло измениться в цикле
А почему Вы так в этом уверены? Посмотрите ассемблерный код, сгенерированный компилятором при включённой оптимизации — он не только в курсе, что i в цикле не изменилось, он там такие штуки вытворяет ;)
Сразу не понять вас, можно попробоватьтег возведения в степень
Мне вот тут интересно самому стало и я написал маленькую программочку, где массив заполняется случайными числами от 0 до 10и. И потом программка пробегается по массиву с условием if эл-т > некоторого порога (от 0 до 10). И мне было интересно, как производительность меняется как функция порога.
Вот кусочек программки:
for(i=0; i < 100000;i++){
xx[i]=1.*(10.*rand()/RAND_MAX);
}
for (i=0;i<1000;i++){
for(j=0;j<100000;j++){
if (xx[j]>val){
sum+=1;
}
else{
sum+=2;
}
}
}
И вот как производительность меняется, как функция порога(переменная val) (картинку не смог вставить):
val Time(sec):
0 6.5
1 8.6
2 10.6
3 12.1
4 12.5
5 12.0
6 10.7
7 8.7
8 6.6
9 4.6
Видно что максимальная производительность при val=0 или 10, когда все if-ы срабатывают одинаково. Также интересно, что разница в производительности (по сравнению с worst case) составила ровно 2 раза. Сам не ожидал.
Вот кусочек программки:
for(i=0; i < 100000;i++){
xx[i]=1.*(10.*rand()/RAND_MAX);
}
for (i=0;i<1000;i++){
for(j=0;j<100000;j++){
if (xx[j]>val){
sum+=1;
}
else{
sum+=2;
}
}
}
И вот как производительность меняется, как функция порога(переменная val) (картинку не смог вставить):
val Time(sec):
0 6.5
1 8.6
2 10.6
3 12.1
4 12.5
5 12.0
6 10.7
7 8.7
8 6.6
9 4.6
Видно что максимальная производительность при val=0 или 10, когда все if-ы срабатывают одинаково. Также интересно, что разница в производительности (по сравнению с worst case) составила ровно 2 раза. Сам не ожидал.
опечатка в тегах: «пердсказатель»
вот :)
вот :)
ИМХО уменьшение кол-ва промахов L1 — это очень и очень серьёзно :-)
Он быстрее L2 раз в 10 :-)
Он быстрее L2 раз в 10 :-)
По данным отсюда:
L1 — 4/12 Cycle Latency
L2 — 20/20 Cycle Latency
То есть всё же не в 10 раз :) А вот промах последнего кэша будет стоить раз в 10 дороже.
Но в нашем случае промахов L1 банально слишком мало, чтобы это можно было заметить — меньше одного на 10 тысяч инструкций.
L1 — 4/12 Cycle Latency
L2 — 20/20 Cycle Latency
То есть всё же не в 10 раз :) А вот промах последнего кэша будет стоить раз в 10 дороже.
Но в нашем случае промахов L1 банально слишком мало, чтобы это можно было заметить — меньше одного на 10 тысяч инструкций.
кэш, это конечно круто.
но кнут нас учит тому что скорость сортровки равна n*log(n).
зачем рассматривать пузырек, который имеет эффективность n^2 ???
и его оптимизации, которые имеют эфффективность… n^2, но в три раза круче!
но кнут нас учит тому что скорость сортровки равна n*log(n).
зачем рассматривать пузырек, который имеет эффективность n^2 ???
и его оптимизации, которые имеют эфффективность… n^2, но в три раза круче!
Видимо, потому что статья не о сортировках, а об обращении к памяти в алгоритмах вообще. В паре случаев подобные соображения помогли мне оптимизировать более чем в три раза линейные (!) алгоритмы в узких по производительности местах.
К слову сказать, «логарифмические» сортировки часто обращаются к памяти в случайном порядке, что провоцирует малопредсказуемые переходы — и в самом печальном случае (хотя это, конечно, маловероятно) пузырек на плохой железке может перегнать qsort (слишком случаен, велико худшее время), heapsort (вот этот более предсказуем) и аналоги.
К слову сказать, «логарифмические» сортировки часто обращаются к памяти в случайном порядке, что провоцирует малопредсказуемые переходы — и в самом печальном случае (хотя это, конечно, маловероятно) пузырек на плохой железке может перегнать qsort (слишком случаен, велико худшее время), heapsort (вот этот более предсказуем) и аналоги.
Кто-то должен был это спросить :) Пузырёк здесь просто как пример. Вы же не подумали, что мы тут пузырёк оптимизируем, правда?
пардон-пардон.
а что делаем? ищем алгоритм, который на конкретном процессоре, конкретного производителя, при конкретных даныых дает выигрыш? зачем???
а что делаем? ищем алгоритм, который на конкретном процессоре, конкретного производителя, при конкретных даныых дает выигрыш? зачем???
Ну, лично я ничего не ищу.
Собственно, я напискал рассказ о причинах, почему один пример быстрее другого, при том что алгоритмически они не отличаются. И причины эти не в «конкретных процессорах» и не в данных, а в общих подходах, использующихся во всех современных процессорах, которые интересно и полезно знать.
Это здорово, что Вы знаете про асимптотическую сложность различных сортировок, но есть и другие важные вещи.
А что Вы пытаетесь сейчас доказать, так я вообще не понимаю. Может быть, Вы дочитали текст только до хабраката?
Собственно, я напискал рассказ о причинах, почему один пример быстрее другого, при том что алгоритмически они не отличаются. И причины эти не в «конкретных процессорах» и не в данных, а в общих подходах, использующихся во всех современных процессорах, которые интересно и полезно знать.
Это здорово, что Вы знаете про асимптотическую сложность различных сортировок, но есть и другие важные вещи.
А что Вы пытаетесь сейчас доказать, так я вообще не понимаю. Может быть, Вы дочитали текст только до хабраката?
я имел ввиду, что наблюдение конечно интересное, однако трудноприменимое в реальной жизни.
причины связаны и с конекретным процессором (на процессорах другой архитектуры разница будет меньше), и с данными (т.к. очень большую часть времени алгоритм просто идет по уже отсортированной части массива).
я согласен, что анализ работы блоков процессора часто позволяет достичь существенного ускорения (для этого производитлями собственно выпускаются всяческие optimization guide и профайлеры, показывающие состояния кэшей, конвееров и т.п.), но, может быть, меня смутил выбор примера на котором это демонстрируется. т.е. взяли алгоритм, часть которого состоит из «пустого цикла», и взялись оптимизировать этот самый пустой цикл.
причины связаны и с конекретным процессором (на процессорах другой архитектуры разница будет меньше), и с данными (т.к. очень большую часть времени алгоритм просто идет по уже отсортированной части массива).
я согласен, что анализ работы блоков процессора часто позволяет достичь существенного ускорения (для этого производитлями собственно выпускаются всяческие optimization guide и профайлеры, показывающие состояния кэшей, конвееров и т.п.), но, может быть, меня смутил выбор примера на котором это демонстрируется. т.е. взяли алгоритм, часть которого состоит из «пустого цикла», и взялись оптимизировать этот самый пустой цикл.
Да не пытались мы ничего оптимизировать, мы просто разбирались, почему одно быстрее другого. Почему автор исходного поста сделал такую «оптимизацию» я точно не знаю — похоже, что он пытался на простом примере показать улучшение за счёт кэша, но чуть промазал :)
Я не знаю, о каких других архитектурах вы говорите, но по-моему Pentium 4, Core2Duo и аналогичные процы от АМД — такой нехилый класс процессоров (сколько процентов от всех десктопов?), и везде будет наблюдаться похожая разница за счёт длинного конвейера и предсказателя переходов. Я ведь не пытаюсь обобщить это на вообще все процессоры.
Насчёт реальной жизни — я, например, до того, как разобрался с этим, считал, что ветвление сильно бьёт по производительности. Где-то я это раньше читал. А в реальности как раз если переход хорошо предсказуем, то влияние на производительность будет минимальным. И мне это знание может помочь при написании реального кода.
Я не знаю, о каких других архитектурах вы говорите, но по-моему Pentium 4, Core2Duo и аналогичные процы от АМД — такой нехилый класс процессоров (сколько процентов от всех десктопов?), и везде будет наблюдаться похожая разница за счёт длинного конвейера и предсказателя переходов. Я ведь не пытаюсь обобщить это на вообще все процессоры.
Насчёт реальной жизни — я, например, до того, как разобрался с этим, считал, что ветвление сильно бьёт по производительности. Где-то я это раньше читал. А в реальности как раз если переход хорошо предсказуем, то влияние на производительность будет минимальным. И мне это знание может помочь при написании реального кода.
Небольшая модификация, дающая еще процентов 30% ускорения (второй вариант, для включенной оптимизации).
Ребята, вы упустили важную деталь. Производительность кешей, оптимизации процессора, аппаратные уловки — это все хорошо. Однако, сравнительный анализ тем полезнее, чем более эквивалентны сравниваемые сущности. А данном случае, это — далеко не так!
Несмотря на внешние сходства и общую ассимптотику O(N2), «вставки» и «пузырек» — суть разные подходы. Для ознакомления могу отправить к матчасти (например, Р. Седжвик, «Фундаментальные алгоритмы на С++ [1-4]», часть 3: «Сортировка», стр. 264 :)). А вкратце — «пузырек» ведет себя, скорее, как сортировка «выбором», нежели «вставками». Но с меньшей эффективностью. Впрочем, производительность даже продуманных модификаций «пузырька» (например, Шейкер-сортировки) оставляет желать лучшего. Но в случае «вставок» — все наоборот. Это — очень мощный алгоритм, к которому часто прибегают (привет усомнившимся в применимости квадратичых методов!) для упорядочивания малых или почти отсортированных (с малым количеством инверсий) массивов. Естественно, при этом обычно добляют пару символов и улучшают его быстродействие еще в 1.5 раза.
Напоследок, приведу несколько лемм без доказательства:
1. «Вставки» производит около N2/4 сравнений и обменов в среднем случае, и около N2/2 — в худшем (это — редко).
2. «Пузырек» — около N2/2 операций сравнения и обмена как в среднем, так и в худшем случаях.
Вывод: прежде аппаратных оптимизаций, имеет смысл подумать о программных (алгоритмических). В случае анализа кода — все аналогично. Не смотря на это, автор — молодец :-) Интересный материал.
Несмотря на внешние сходства и общую ассимптотику O(N2), «вставки» и «пузырек» — суть разные подходы. Для ознакомления могу отправить к матчасти (например, Р. Седжвик, «Фундаментальные алгоритмы на С++ [1-4]», часть 3: «Сортировка», стр. 264 :)). А вкратце — «пузырек» ведет себя, скорее, как сортировка «выбором», нежели «вставками». Но с меньшей эффективностью. Впрочем, производительность даже продуманных модификаций «пузырька» (например, Шейкер-сортировки) оставляет желать лучшего. Но в случае «вставок» — все наоборот. Это — очень мощный алгоритм, к которому часто прибегают (привет усомнившимся в применимости квадратичых методов!) для упорядочивания малых или почти отсортированных (с малым количеством инверсий) массивов. Естественно, при этом обычно добляют пару символов и улучшают его быстродействие еще в 1.5 раза.
Напоследок, приведу несколько лемм без доказательства:
1. «Вставки» производит около N2/4 сравнений и обменов в среднем случае, и около N2/2 — в худшем (это — редко).
2. «Пузырек» — около N2/2 операций сравнения и обмена как в среднем, так и в худшем случаях.
Вывод: прежде аппаратных оптимизаций, имеет смысл подумать о программных (алгоритмических). В случае анализа кода — все аналогично. Не смотря на это, автор — молодец :-) Интересный материал.
Сразу хочу сказать, что я «в теме» насчёт сложностей алгоритмов и методов сортировок, чтобы избежать излишних объяснений.
Здесь забавно то, что изначально вообще речи не шло о сравнении двух разных методов сортировки, посмотрите исходный пост на который я ссылаюсь в начале — там говорится об «усовершенствованном пузырьке». А на самом деле, о том, что это метод вставок я догадался уже при написании статьи, когда думал про визуализацию исходных алгоритмов. Когда у тебя на глазах «оптимизируют» пузырёк, не сразу и догадаешься, что он вообще-то превратился в другой метод :)
Фокус в том, что несмотря на принципиальную разницу между методом пузырька и вставок, с точки зрения сравнений и обменов здесь всё эквивалентно. За исключением несущественных оптимизаций, сравниваются и переставляются одни и те же ячейки памяти, меняется лишь порядок. И вот именно за счёт изменения порядка операций, а не за счёт разницы в алгоритмах и возникает огромная разница во времени выполнения из-за предсказателя переходов.
Т.е. вывод здесь как раз обратный — теоретическая сложность алгоритма не однозначно задаёт реальное время выполнения, довольно сильная разница может оказаться за счёт технических деталей платформы, и поэтому ими не следует пренебрегать. Но никто, конечно, не спорит, что эта разница, скорее всего, даёт лишь «не очень большую» константу, а в то время как алгоритмическая сложность разных методов может отличаться на порядки.
Здесь забавно то, что изначально вообще речи не шло о сравнении двух разных методов сортировки, посмотрите исходный пост на который я ссылаюсь в начале — там говорится об «усовершенствованном пузырьке». А на самом деле, о том, что это метод вставок я догадался уже при написании статьи, когда думал про визуализацию исходных алгоритмов. Когда у тебя на глазах «оптимизируют» пузырёк, не сразу и догадаешься, что он вообще-то превратился в другой метод :)
Фокус в том, что несмотря на принципиальную разницу между методом пузырька и вставок, с точки зрения сравнений и обменов здесь всё эквивалентно. За исключением несущественных оптимизаций, сравниваются и переставляются одни и те же ячейки памяти, меняется лишь порядок. И вот именно за счёт изменения порядка операций, а не за счёт разницы в алгоритмах и возникает огромная разница во времени выполнения из-за предсказателя переходов.
Т.е. вывод здесь как раз обратный — теоретическая сложность алгоритма не однозначно задаёт реальное время выполнения, довольно сильная разница может оказаться за счёт технических деталей платформы, и поэтому ими не следует пренебрегать. Но никто, конечно, не спорит, что эта разница, скорее всего, даёт лишь «не очень большую» константу, а в то время как алгоритмическая сложность разных методов может отличаться на порядки.
К сожалению, ночью я просмотрел, что ваш алгоритм «вставками» не выполняет break, находя позицию очередного элемента в отсортированном подмассиве. И делает это, соответственно, операциями полного, а не половинного обмена. В этом виде к нему применима та же оценка, что и для «пузырька». Единственная разница — полная упорядоченность данных, на которых работает 1й алгоритм, и почти полное ее отсутствие — во втором случае. Видимо, вы правы касательно оптимизаций. К слову, на моем процессоре (AMD Turion X2 1.6 mobile) первоначальный выигрыш ваших «вставок» по времени не превышал 30%, а после отключения оптимизаций компиллятора (/Od) — сократился до 15% (msvc).
Прочитал эту статью после шума с Meltdown https://habrahabr.ru/post/346026/
Какие интересные порой связи находятся.
Какие интересные порой связи находятся.
Sign up to leave a comment.
Пузырьки, кэши и предсказатели переходов