Algorithms
Comments 65
UFO landed and left these words here
+5
Так а ведь Intel C++ Compiler с версии 9.0 уже сам умеет менять вложенность циклов где надо. И еще кучу всего. :) Будущее уже совсем рядом.
0
Покажите мне хоть одну серьезную либу, где используется сортировка пузырьком %)
UFO landed and left these words here
0
Каждому алгоритму своё место. Чтобы отсортировать 10 элементов, использовать какую-нибудь хитрую многопоточную сортировку сродни стрельбе из пушек по комарам.
Тут как раз удобен пузырёк — простой, маленький, не есть стек.
+1
«Ага, скажет подкованный читатель» — привет от русских книг из серии «…для чайников»
0

-хрусть! — сказала японская лесопилка
-АГА! — обрадовались суровые русские мужики
(Ц)анекдот
+6
кстати, из этой же оперы: допустим, нужно делать разные операции над двумя независимыми списками (пусть одинаковой длины).

Казалось бы — время работы будет одинаково в обоих случаях:
— сделать работу за два разных цикла (правильный программистский подход)
— объединить две операции в один цикл («говнокод»)

Так вот, говнокод будет работать ощутимо быстрее, особенно в случае linked list.
В таком случае процессор заказывает данные из памяти для элементов сразу двух списков.
Данные, которые придут раньше и будут обработаны раньше.

Фактически, списки будут обрабатываться параллельно даже на одно-ядерном процессоре из одной нитки.

А «классичекий» подход (если компилятор не перехитрит программиста), будет работать последовательно.
0
По моему, во втором варианте «предсказателю будущего» будет проще принять решение еще и потому что условие выхода из вложенного цикла — сравнение с константой (да и один свободный регист в процессе оптимизации много что дает, хотя не в таком простом случае).
0
Ну, там как раз компилятор малость оптимизирует. Да и это условие достаточно редко происходит.
0
Врятли так уж редко. Сначала цикл на две итерации. Потом 3. И т.д. А на каждую итерацию нужно сравнение…
0
Ой, что-то я не о том подумал. Проверка условия действительно каждую итерацию выполняется, но компилятор может это легко оптимизировать, и привести к виду, аналогичному второму варианту.
+3
десятки тактов, что не так уж и много
Ни хера себе «не так уж много»! С учетом того, что за один такт процессор может исполнить более трех инструкций, если все удачно :)
0
Вообще мне кажется, что правильный вариант компилирования кода «if something then swap» не должен вообще иметь ветвления — есть специальные инструкции compare-and-swap как раз для таких случаев, специально, чтобы избежать перехода и накладных расходов на его предсказание.
В таком случае ошибки branch prediction будут очень редкими — ровно один раз за каждый выход из вложенного цикла (условный jump назад предсказывается происходящим).
0
Угу. На арме вот есть замечательная комманда swp{cond} ({cond} определяет условие при котором команда будет выполнятся). Сия статья заставила меня задуматся над возможным применением этой комманды :)
+4
Что swp, что cmpxchg, предназначены для синхронизации (например для реализации мьютексов).
Команды обеспечивают атомарный доступ к памяти и поэтому являются очень медленными
+1
И кстати SWP это уже устаревшая команда.
Вместо неё используется резервация кешстроки как в других RISC-ах
LDREX / STREX
+1
Ну и последнее. Оптимизация должна идти сверху вниз. Т.е. сначала выбирается оптимальный алгоритм, потом с ним уже занимаемся низкоуровненвым дрочерством. Реквстирую в пост сравнение, как работает на том же механизме 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);
}
+1
Попробовал для интереса переписать сортировку в один цикл, получилось вот что pastebin.com/m6c6397ca

Но в итоге, за счёт сложных вычислений, работает примерно в три раза медленнее обычной версии.
+1
А, я кстати на грабли тут как раз наступил.
Деление по модулю — оно опасное. Если компилятор поставит idiv — то будет привет, у него latency десятки тактов. Поэтому, например
i=(i+1)%N;
может замедлить какой-нибудь простой цикл в 20 раз по сравнению с:
i++;
if (i > N)
  i = 0;
0
Делите на степень двойки. :)
Если ваш компилятор напишет idiv при попытке поделить на константу-степень-двойки — выкиньте его.
0
В принципе, не обязательно степень двойки — умный компилятор будет оптимизировать деление и на другие константы, например, вот так выглядит деление на 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

Но я говорил скорее о случае с не-константами.
+3
Насколько я знаю, Prescott имеет длинный конвеер и ошибки предсказателя переходов для него критичны. На других процессорах, возможно, разница будет меньше. Поправьте пожалуйста, если я не прав
+2
В целом все современные процы x86 имеют длинный конвеер. Слишком сложные инструкции.
+4
У вас алгоритмы не эквивалентны

В первом варианте:
проверка условия в первом цикле — N операций
проверка условия во втором цикле — (N^2-1)/2*3 операций

Во втором варианте
проверка условия в первом цикле — N-1 операций
проверка условия во втором цикле — (N^2-1)/2*1 операций

При большом N учитываем только старшую степень, общая сложность:
N^2(c+0.5) операций для второго и N^2(c+1.5) операций для первого
+1
Что-то я не понял, откуда в первом варианте *3? Если речь о N — (i+1), то компилятор его посчитает только один раз на весь внутренний цикл.
0
i — переменная, выражения с переменными пересчитываются на каждом проходе, так как ее значение могло измениться в цикле
0
А почему Вы так в этом уверены? Посмотрите ассемблерный код, сгенерированный компилятором при включённой оптимизации — он не только в курсе, что i в цикле не изменилось, он там такие штуки вытворяет ;)
-2
Вам никогда не советовали писать код с выключенным оптимизатором компилятора?

Странные вещи случаются когда пишешь кроссплатформенный код и один компилятор оптимизирует так, а другой иначе, в результате затормоз и быстро уже не поправить, так как глубоко зашит.
+4
Искренне надеюсь, что мне этот совет никогда не пригодится ;)
Не хотелось бы делать работу компилятора самому.
0
Мне вот тут интересно самому стало и я написал маленькую программочку, где массив заполняется случайными числами от 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 раза. Сам не ожидал.
+1
А у меня в 4-6 раз получилось, я вроде писал в статье.
0
ИМХО уменьшение кол-ва промахов L1 — это очень и очень серьёзно :-)
Он быстрее L2 раз в 10 :-)
0
По данным отсюда:
L1 — 4/12 Cycle Latency
L2 — 20/20 Cycle Latency
То есть всё же не в 10 раз :) А вот промах последнего кэша будет стоить раз в 10 дороже.
Но в нашем случае промахов L1 банально слишком мало, чтобы это можно было заметить — меньше одного на 10 тысяч инструкций.
-4
кэш, это конечно круто.
но кнут нас учит тому что скорость сортровки равна n*log(n).

зачем рассматривать пузырек, который имеет эффективность n^2 ???
и его оптимизации, которые имеют эфффективность… n^2, но в три раза круче!
+4
Видимо, потому что статья не о сортировках, а об обращении к памяти в алгоритмах вообще. В паре случаев подобные соображения помогли мне оптимизировать более чем в три раза линейные (!) алгоритмы в узких по производительности местах.

К слову сказать, «логарифмические» сортировки часто обращаются к памяти в случайном порядке, что провоцирует малопредсказуемые переходы — и в самом печальном случае (хотя это, конечно, маловероятно) пузырек на плохой железке может перегнать qsort (слишком случаен, велико худшее время), heapsort (вот этот более предсказуем) и аналоги.
+2
Кто-то должен был это спросить :) Пузырёк здесь просто как пример. Вы же не подумали, что мы тут пузырёк оптимизируем, правда?
-2
пардон-пардон.
а что делаем? ищем алгоритм, который на конкретном процессоре, конкретного производителя, при конкретных даныых дает выигрыш? зачем???
+3
Ну, лично я ничего не ищу.
Собственно, я напискал рассказ о причинах, почему один пример быстрее другого, при том что алгоритмически они не отличаются. И причины эти не в «конкретных процессорах» и не в данных, а в общих подходах, использующихся во всех современных процессорах, которые интересно и полезно знать.
Это здорово, что Вы знаете про асимптотическую сложность различных сортировок, но есть и другие важные вещи.
А что Вы пытаетесь сейчас доказать, так я вообще не понимаю. Может быть, Вы дочитали текст только до хабраката?
0
я имел ввиду, что наблюдение конечно интересное, однако трудноприменимое в реальной жизни.
причины связаны и с конекретным процессором (на процессорах другой архитектуры разница будет меньше), и с данными (т.к. очень большую часть времени алгоритм просто идет по уже отсортированной части массива).
я согласен, что анализ работы блоков процессора часто позволяет достичь существенного ускорения (для этого производитлями собственно выпускаются всяческие optimization guide и профайлеры, показывающие состояния кэшей, конвееров и т.п.), но, может быть, меня смутил выбор примера на котором это демонстрируется. т.е. взяли алгоритм, часть которого состоит из «пустого цикла», и взялись оптимизировать этот самый пустой цикл.
+1
Да не пытались мы ничего оптимизировать, мы просто разбирались, почему одно быстрее другого. Почему автор исходного поста сделал такую «оптимизацию» я точно не знаю — похоже, что он пытался на простом примере показать улучшение за счёт кэша, но чуть промазал :)
Я не знаю, о каких других архитектурах вы говорите, но по-моему Pentium 4, Core2Duo и аналогичные процы от АМД — такой нехилый класс процессоров (сколько процентов от всех десктопов?), и везде будет наблюдаться похожая разница за счёт длинного конвейера и предсказателя переходов. Я ведь не пытаюсь обобщить это на вообще все процессоры.
Насчёт реальной жизни — я, например, до того, как разобрался с этим, считал, что ветвление сильно бьёт по производительности. Где-то я это раньше читал. А в реальности как раз если переход хорошо предсказуем, то влияние на производительность будет минимальным. И мне это знание может помочь при написании реального кода.
0
хм. первую-то фразу статьи я и не заметил. :)
тогда все понятно.
0
Да, размотка цикла — молодец. Но об do вложенный в switch мозги поломать можно :)
+1
Результаты с -funroll-loops:

test1: 20.295
test2: 6.9141
duff_test: 5.82957
ratio(1/2): 2.94
ratio(1/d): 3.48
ratio(2/d): 1.19

0
Ребята, вы упустили важную деталь. Производительность кешей, оптимизации процессора, аппаратные уловки — это все хорошо. Однако, сравнительный анализ тем полезнее, чем более эквивалентны сравниваемые сущности. А данном случае, это — далеко не так!

Несмотря на внешние сходства и общую ассимптотику O(N2), «вставки» и «пузырек» — суть разные подходы. Для ознакомления могу отправить к матчасти (например, Р. Седжвик, «Фундаментальные алгоритмы на С++ [1-4]», часть 3: «Сортировка», стр. 264 :)). А вкратце — «пузырек» ведет себя, скорее, как сортировка «выбором», нежели «вставками». Но с меньшей эффективностью. Впрочем, производительность даже продуманных модификаций «пузырька» (например, Шейкер-сортировки) оставляет желать лучшего. Но в случае «вставок» — все наоборот. Это — очень мощный алгоритм, к которому часто прибегают (привет усомнившимся в применимости квадратичых методов!) для упорядочивания малых или почти отсортированных (с малым количеством инверсий) массивов. Естественно, при этом обычно добляют пару символов и улучшают его быстродействие еще в 1.5 раза.

Напоследок, приведу несколько лемм без доказательства:
1. «Вставки» производит около N2/4 сравнений и обменов в среднем случае, и около N2/2 — в худшем (это — редко).
2. «Пузырек» — около N2/2 операций сравнения и обмена как в среднем, так и в худшем случаях.

Вывод: прежде аппаратных оптимизаций, имеет смысл подумать о программных (алгоритмических). В случае анализа кода — все аналогично. Не смотря на это, автор — молодец :-) Интересный материал.
0
Сразу хочу сказать, что я «в теме» насчёт сложностей алгоритмов и методов сортировок, чтобы избежать излишних объяснений.

Здесь забавно то, что изначально вообще речи не шло о сравнении двух разных методов сортировки, посмотрите исходный пост на который я ссылаюсь в начале — там говорится об «усовершенствованном пузырьке». А на самом деле, о том, что это метод вставок я догадался уже при написании статьи, когда думал про визуализацию исходных алгоритмов. Когда у тебя на глазах «оптимизируют» пузырёк, не сразу и догадаешься, что он вообще-то превратился в другой метод :)

Фокус в том, что несмотря на принципиальную разницу между методом пузырька и вставок, с точки зрения сравнений и обменов здесь всё эквивалентно. За исключением несущественных оптимизаций, сравниваются и переставляются одни и те же ячейки памяти, меняется лишь порядок. И вот именно за счёт изменения порядка операций, а не за счёт разницы в алгоритмах и возникает огромная разница во времени выполнения из-за предсказателя переходов.

Т.е. вывод здесь как раз обратный — теоретическая сложность алгоритма не однозначно задаёт реальное время выполнения, довольно сильная разница может оказаться за счёт технических деталей платформы, и поэтому ими не следует пренебрегать. Но никто, конечно, не спорит, что эта разница, скорее всего, даёт лишь «не очень большую» константу, а в то время как алгоритмическая сложность разных методов может отличаться на порядки.
0
К сожалению, ночью я просмотрел, что ваш алгоритм «вставками» не выполняет break, находя позицию очередного элемента в отсортированном подмассиве. И делает это, соответственно, операциями полного, а не половинного обмена. В этом виде к нему применима та же оценка, что и для «пузырька». Единственная разница — полная упорядоченность данных, на которых работает 1й алгоритм, и почти полное ее отсутствие — во втором случае. Видимо, вы правы касательно оптимизаций. К слову, на моем процессоре (AMD Turion X2 1.6 mobile) первоначальный выигрыш ваших «вставок» по времени не превышал 30%, а после отключения оптимизаций компиллятора (/Od) — сократился до 15% (msvc).
0
Всё верно, только алгоритм не «мой» :)
Неудивительно, что на разных процессорах выигрыш может быть разным (особенно Intel vs AMD) — кэши и предсказатели переходов всюду свои.
0
Т.к. классический алгоритм, для которого справедливы указанные оценки, выглядит чуть иначе — приходится говорить о «ваших вставках» как о реализации, приведенной вами :-)
Only those users with full accounts are able to leave comments., please.