Причиной обычно указывают то, что у современного центрального процессора имеется столько конвейеров и конфликтов по управлению, с которыми приходится иметь дело, что простая программа ассемблера не сделает работу хорошо, обращаясь с ними.
Но так ли это? Давайте не будем просто воспринимать на веру слова некоторых парней в интернете, как библейское откровение, а проведём небольшой эксперимент и выясним.
Мы просто возьмём несложный кусок кода и рассмотрим его. Я не собираюсь выбрать пример, который может выиграть, в большой степени, от экзотических встроенных функций. Вместо этого я возьму старый стандартный quicksort.
Здесь показана простая быстрая сортировка в C++, которую мы протестируем:
struct Item { int key; int value; };
extern "C"
void sortRoutine(Item *items, int count)
{
if (count <= 1)
return; // already sorted if only zero/one element
// Pick the pivot.
Item pivot = items[count-1];
int low = 0;
for (int pos=0;pos<count-1;pos++)
{
if (items[pos].key <= pivot.key) {
// swap elements
Item tmp = items[pos];
items[pos] = items[low];
items[low] = tmp;
low++;
}
}
items[count-1] = items[low];
items[low] = pivot;
sortRoutine(items, low);
sortRoutine(items+low+1, count-1-low);
}Ничего необычного. Это не самый лучший алгоритм сортировки в мире, а это — даже не самая лучшая реализация, но он простой и делает своё дело неплохо.
Теперь попробуем прямо выполнить простую реализацию такого подхода в ассемблере:
sortRoutine:
; rcx = items
; rdx = count
sub rdx, 1
jbe done
; Pick the pivot.
mov r8, [rcx+rdx*8] ; r8 = pivot data
xor r9, r9 ; r9 = low
xor r10, r10 ; r10 = pos
partition:
cmp [rcx+r10*8], r8d
jg noswap
; swap elements
mov rax, [rcx+r10*8]
mov r11, [rcx+r9*8]
mov [rcx+r9*8], rax
mov [rcx+r10*8], r11
inc r9
noswap:
inc r10
cmp r10, rdx
jb partition
; move pivot into place
mov rax, [rcx+r9*8]
mov [rcx+rdx*8], rax
mov [rcx+r9*8], r8
; recurse
sub rdx, r9
lea rax, [rcx+r9*8+8]
push rax
push rdx
mov rdx, r9
call sortRoutine
pop rdx
pop rcx
test rdx, rdx
jnz sortRoutine
done:
retНаписать это оказалось довольно просто, в основном благодаря операторам гибкой адресации к памяти Intel. Что интересно — я не делал никакой реальной попытки обращать внимание на планирование, конвейеризацию и так далее. Я просто написал это как несложную программу на ассемблере.
Теперь давайте оценим затраченное время. Я написал простую тестовую программу, сортирующую массив из 1 000 000 позиций. Тест был выполнен 100 раз и было взято наилучшее значение для всего набора. Версия С++ была скомпилирована с использованием gcc 4.8.1, clang 3.8.0 и MSVC 2013.
Результаты
sort_cpp_recurse_gcc.exe : 99 мс - наилучший результат для 100 прогонов
sort_cpp_recurse_clang.exe : 99 мс - наилучший результат для 100 прогонов
sort_cpp_recurse_ms.exe : 98 мс - наилучший результат для 100 прогонов
sort_asm_recurse.exe : 92 мс - наилучший результат для 100 прогоновНу, это интересно. Различные компиляторы дают, в основном, одинаковый результат с незначительным преимуществом у MSVC. Но версия ассемблера работает явно быстрее — почти на 7% в этом случае.
Дело в том, в C++ не всегда имеется хорошее представление базовой машины. Это нормально, когда речь идёт о переменных, но его представление стека очень ограничено. C++ считает, что мы можем использовать стек только для вызовов, тогда как в действительности — одна из вещей, которые мы можем делать, это использовать его в качестве стека данных.
Попробуем и посмотрим, что получится. Мы удалим рекурсивные обращения к sortRoutine и вместо этого будем извлекать наши диапазоны данных непосредственно из стека. Это позволяет нам работать в едином цикле без необходимости, фактически, обращаться к рекурсии. Часто такой подход может дать значительное преимущество, поскольку устраняет потери времени на каждом входе в функцию / выходе из неё.
Соответствующая программа имеется в архивном файле ниже.
sort_cpp_recurse_gcc.exe : 99 мс - наилучший результат для 100 прогонов
sort_cpp_recurse_clang.exe : 99 мс - наилучший результат для 100 прогонов
sort_cpp_recurse_ms.exe : 98 мс - наилучший результат для 100 прогонов
sort_asm_recurse.exe : 92 мс - наилучший результат для 100 прогонов
sort_cpp_iter_gcc.exe : 106 мс - наилучший результат для 100 прогонов
sort_cpp_iter_clang.exe : 97 мс - наилучший результат для 100 прогонов
sort_cpp_iter_ms.exe : 95 мс - наилучший результат для 100 прогонов
sort_asm_iter.exe : 92 мс - наилучший результат для 100 прогоновИнтересно. Версия ассемблера дала почти тот же результат. Я полагаю, это связано с тем, что, хотя итеративный подход устраняет потери на работу с функциями, но такие потери у нашей написанной вручную версии для x64 на самом деле невелики, поэтому выигрыша не наблюдается.
Но для версий C++ иная ситуация. Большинство продемонстрировало незначительное увеличение скорости, но gcc явно медленнее! Насколько я могу видеть из дизассемблирования, управление построено так, как будто оно пытается запутать само себя. Увеличенные маршруты управления и связанные с этим навороты привели к усложнённому «жонглированию».
Я скомпилировал эти тесты на x64, где соглашением по умолчанию о вызовах является fastcall. Полагаю, что если взамен скомпилировать решение для варианта на 32 бита, использующего соглашение на базе стека cdecl, то нерекурсивная версия дала бы сравнительно лучший результат. Я не пробовал — оставляю как упражнение для читателя.
Заключение
Создаётся впечатление, что старая присказка «современные компиляторы всегда быстрее, чем написанная вами на ассемблере программа» совсем не обязательно является правильной.
Однако правильно то, что компилятор делает достаточно хорошо свою работу, а с кодом легче работать. Поэтому, хотя можно было бы выжать ещё немного скорости, но это вряд ли оправдано из-за появляющихся трудностей, связанных с техобслуживанием.
Версия ассемблера была всё же быстрее. Полагаю, что если в этом посте вы нашли для себя что-то полезное — так это то, что народ в интернете иногда может говорить нечто, совсем не соответствующее действительности.
Материалы
sorttest.zip — Все коды, использованные в данной статье.
Комментарии ()
lorc
12.12.2016 18:40+4quicksort ориентирован на работу с памятью, в любом случае код упирается в скорость работы процессора с памятью. А если взять какой-нибудь вычислительный алгоритм и попытаться обогнать компилятор?
Что-нибудь такое, где вклад памяти небольшой, а нагрузка идет в основном на вычислительные блоки.
Anvol
12.12.2016 21:31эмм… что-то, где дико нагружаются два-три регистра процессора, без памяти?) AES, возможно
lorc
12.12.2016 21:46Ну например да. 10 (кажется) раундов AES для каждого блока или 80 раундов SHA-1. С другой стороны криптография вообще плохо ложится на обычные ALU.
Как насчет численного решения диффуров, например? Или рейтрейсер какой-нибудь. Да хотя бы примитивное сложение 32 битных слов как в недавнем посте схожей тематики. Там, кстати, компилятор победил довольно уверенно.
Понятно, что работа с памятью будет в любом случае. Ну пусть её будет не 75% как в случае quicksort, а хотя бы процентов 20.
DistortNeo
12.12.2016 18:51У меня есть просьба: выложите не только исходники, но и бинарники, чтобы я мог сравнить с другими компиляторами (MSVC2015 и ICL17).
insanny
12.12.2016 18:59Делал достаточно простую задачу по наложению двух восьмибитных FullHD-кадров друг на друга (YUV+YUVA=YUV), с использованием SIMD. Ассемблерная функция в C-программе.
Даже на AVX дает прирост больше чем в 50% при рандомной альфа-маске.
Возможно, я не идеально знаю ключи для оптимизации, компилил при помощи gcc -O3
На AVX2 ассемблер еще быстрее.
Я уже не говорю про то, что он отрабатывает ЗНАЧИТЕЛЬНО быстрее, если в маске у нас 16 следующих друг за другом 0x00 или 0xFF (полностью прозрачный или полностью непрозрачный фрейм), что очень актуально при наложении эффектов типа логотипа.DaylightIsBurning
12.12.2016 21:14А если использовать Eigen или другие готовые решения для работы с массивами чисел?
insanny
13.12.2016 01:49Тогда не было необходимости и достаточного скилла на это всё)
Спасибо за наводку, обязательно буду иметь в виду, как дойдут руки — проверю на деле.
splav_asv
12.12.2016 21:30+1-march=native -Ofast пробовали?
insanny
13.12.2016 01:52и -Ofast, и -O2, и -O3
Лучший результат, которого удалось добиться на том проце (вроде бы, был i3 low power 3 поколения), был 3.2мс, против которого ассемблер выдавал меньше 2мс.
Цифры помню, остальное — увы, уже нет. Надо будет освежить
thatsme
13.12.2016 00:42-pipe -O2 -march=native -mtune=native -fomit-frame-pointer -mfpmath=sse -mavx2 -ftree-vectorize -funroll-loops
isotoxin
12.12.2016 19:05+1Скажу так. Есть у меня в коде одна задача, когда мне нужно было отрисовать в текстуру пиксели с хитрым блендингом (пусть вас не смущает слово «текстура», задача чисто CPU-шная, никаких ускорителей в работе не используется).
Ну так вот. Я написал код на ассемблере с использованием SSE2. Вроде быстро.
Но потом я переписывал это код на AMD64 и решил отказаться от ассемблера. Переписал на интринсики. При чем вообще не заморачивался на скорость. Писал грубо, без каких-либо оптимизаций. Там присутствовали конструкции вида:_mm_storeu_si128( ( __m128i * )dst_argb, _mm_packus_epi16( _mm_add_epi16( _mm_mulhi_epu16( _mm_shuffle_epi8( t4, pta1 ), _mm_shuffle_epi8( tt5, a1l ) ), _mm_mulhi_epu16( _mm_shuffle_epi8( tt5, a1r ), t6 ) ), _mm_add_epi16( _mm_mulhi_epu16( _mm_shuffle_epi8( t4, pta2 ), _mm_shuffle_epi8( tt5, a2l )), _mm_mulhi_epu16( _mm_shuffle_epi8( tt5, a2r ), t6 ) ) ) );
Ну т.е. многоэтажные вызовы интринсиков. И каков результат? А результат таков, что этот код стал работать быстрее того, что был на голом ассемблере. Так что компиляторы нынче действительно очень хороши. Смысла в ассемблере очень мало.
crea7or
12.12.2016 21:08Ради забавы тут кое что ваял и интринсики и вправду оказались быстрее и удобнее. И как я не бился, ассемблерный код всегда вызывался (не инлайнился).
zzzcpan
12.12.2016 23:16Да ну, интринсики — это уже тоже ручная оптимизация. Можно считать, что это тот же ассемблер, только чуть более универсальный.
DistortNeo
12.12.2016 23:29+1А главное — можно писать одинаковый код для х86 и х64.
zzzcpan
13.12.2016 00:29Если бы. Отойти подальше от конкретной архитектуры и уже нужен другой код. Те же x86 инструкции у разных интеловских атомов очень отличаются от не атомов и тот же код, что оптимально работал на хасвеле совсем не оптимален на атомах.
DistortNeo
13.12.2016 08:07В такое случае попробуйте Gentoo.
Никто не будет писать отдельный код для каждого процессора, за очень редким исключением. Обычно вполне устраивает существенное ускорение программы за счёт использования векторных инструкций.
A1ien
12.12.2016 19:11+6Мне кажется что в этой статье есть заблуждение. Когда говорят что компилятор C++ «лучше, выше, быстрее» имеют в виду не конеретный код, работающий с конкретными типами, как в примере приведенном в статье, а имеют в виду гораздо более общие случаи.
А приведенном коде (который кстати совсем не а C++), производится работа по сортировке массивов заданного типа, и именно это дает возможность переписать этот код на ассемблере с выигрыщем в произовдительности и (возможно) свободном от ошибок. А теперь представьте что у вас эти Item разные, имееют разные китерии сравнениия, да и вообще у вас не Item а например Peoples, или еще чтото… На C — вы будете пытаться это обобщить через void* и предикаты (и имеете шанс запутаться), на asm вы уже запутаетесь в косвенной адресации и предикатах, шаблонные же алгоритмы на C++ сгенирируют за вас вполне корректный код, который работает по фиксированным отступам в пямяти, со знанием размеров объектов и членов, именно по тому что КОМПИЛЯТОР ЗНАЕТ ТИП и именно это поможет быть этому коду оптимальным.
akzhan
12.12.2016 20:14+2Забавно смотреть бенчи без описания окружения… Тем более в разных окружениях (здесь явно интересны результаты под разные процессоры и с разными опциями оптимизации).
Да и алгоритм тут не самый обычный (редко исполняется). В 80% случаев в коде идут простые переборы, хэши и вычисления, там уже можно использовать SIMD etc.
crea7or
12.12.2016 21:04
crea7or
12.12.2016 21:09+1Вообще тесты на 99 мс — это фигня ибо очень мало. Надо хоть секунд 10 делать для равномерности.
tyomitch
12.12.2016 21:22+6Для интереса прогнал на своей системе:
- sort_cpp_recurse (GCC) занимает 64мс
- sort_cpp_recurse (clang) занимает 62мс
- sort_asm_recurse занимает 60мс (и потребовало некоторое время на адаптацию к линуксовому ABI)
- std::sort занимает 55мс
Отсюда вывод: чем выпендриваться и писать на ассемблере, лучше взять готовый, переносимый, отлаженный код на C++tyomitch
12.12.2016 21:36+3Кроме того, большое сомнение вызывает методология эксперимента (сравнивать самый быстрый из ста прогонов, и игнорировать все остальные).
Если сравнивать результат по всем ста прогонам вместе, то sort_cpp_recurse (clang) даже слегка обгоняет sort_asm_recurse.
Dark_Daiver
12.12.2016 22:53+1>сравнивать самый быстрый из ста прогонов, и игнорировать все остальные
Слышал такое мнение, что окружение в котором запускается процесс не может заставить его выполняться быстрее. Т.е. если у вас есть 4-е запуска программы с разным временем выполнения, то тот, у которого это время меньше ближе всего к реальному времени исполнения, т.к. ему меньше всего «мешали»tyomitch
13.12.2016 01:10Здесь-то разница по времени между разными прогонами не из-за «внешних помех», а из-за того, что массив заполняется по-разному. Для каких-то вариантов начальных данных ассемблерное решение обгоняет сишное, для каких-то — наоборот, так что умелой подгонкой условий эксперимента можно получить любой нужный результат.
Anton_Menshov
12.12.2016 23:07+1Абсолютно с вами согласен. Есть разные вариации методологии, но чаще делают что то вроде (P+N+2*B) прогонов. P- количество прогонов «на прогрев», B — число лучших и худших прогонов, которые мы выкинем.
И время на один прогон определяем как T\N, где T — общее время за вычетом P «прогревных» прогонов, B лучших и B худших. Так можно минимизировать ошибки и убрать джиттер во времени максимальным образом.
alex_zzzz
12.12.2016 23:16+1народ в интернете иногда может говорить нечто, совсем не соответствующее действительности.
Как вы мягко перевели. :)
johnfound
12.12.2016 23:16-3Такие синтетические тесты типа: "Берем функцию, пишем на C и на ассемблере", совершенно не демонстрируют преимущества ассемблера. Я всегда утверждал, что сравнивать надо реальные, законченные программы, которые делают что то разумное и полезное.
Дело в том, что человек не пишет код на ассемблере так как пишет его на ЯВУ. Некоторые вещи, которые на ассемблере просты и логичны, на C такими не являются. Поэтому, неоптимизированные программы на ассемблере всегда получаются намного быстрее чем неоптимизированные программы на C/C++. Мои тесты (а я проводил такие несколько раз) показывают от 5 до 80 раз большее быстродействие ассемблерных программ.
Далее, если сделать несколько итерации оптимизации, программа на C/C++ можно довести до примерно 20..50% медленнее, чем та же программа на ассемблере. Но только если код на ассемблере известен.
В итоге, код на C получается совершенно нечитаемым, а код на ассемблере вполне читаемым.
Но какая часть программ оптимизируют так глубоко? И как поддерживается так глубоко оптимизированная программа?
tyomitch
13.12.2016 01:13+3Писать на ассемблере «разумную, полезную, законченную программу» целиком — это пальба из БАК-а по воробьям. В реальной жизни никто так делать не будет, так что такие тесты совершенно ничего не доказывают.
johnfound
13.12.2016 01:27-1В реальной жизни никто так делать не будет, так что такие тесты совершенно ничего не доказывают.
Никто? Ведь я именно так и делаю. И знаю многих, которые так делают. И поэтому такие тесты многое доказывают.
AllexIn
13.12.2016 08:39+1А можно посмотреть пример большой современной программы написанной вами на ассемблере?
ElectroGuard
12.12.2016 23:53+2За плюсы не скажу. Но, по многолетнему опыту, на Delphi код по скорости почти догоняет ассемблер. 1-2% что я видел. Если без simd, конечно. Simd может дать выигрыш. Еще большее ускорение дает распараллеливание медленных частей по ядрам, что обычно относительно просто делается.
MacIn
13.12.2016 00:11На новых — не знаю, а у 7ки было много бесполезного жонглирования регистрами. Вроде такого:
mov ebx, [ebp + 8]
mov eax, [ebx + 32]
…
mov ebx, [ebp + 8]
т.е. он чуть плоховато чувствовал, когда регистр не становился «грязным».ElectroGuard
13.12.2016 01:13Самое интересное, что это жонглирование почти никак не сказывается на скорости. Я проверял. Разница, по скорости, как я писал — несколько процентов.
MacIn
13.12.2016 01:50Если это неответственный участок кода — да. А так лишнее обращение к памяти не может быть бесплатным, особенно если в промежутке кеш вымывается.
a_bakshaev
13.12.2016 00:19Если важен каждый процент производительности, то все таки на ассемблере, можно попробовать потягаться с компиляторм — спланировать код по переходам, спаривать инструкции по исполнительным юнитам, выравнивать их по адресу в памяти, расставлять префечи, раскручивать циклы, вычислять на lea, использовать минимальные по длине инструкции и т.д. Это очень кропотливая работа, но если речь идет о коде для крупных заказчиков, то имеет смысл использовать асм. Но если перфоманс не настолько критичен, как время на разработку и компилятор при этом сообщает, что векторизовал написанный код, то можно оставлять и на С, А еще можно грамотно прагмы компилятора использовать для оптимизации.
grossws
13.12.2016 01:27+1И код будет быстро работать на одной микроархитектуре, но запросто может оказаться хуже сишного без оптимизаций на другой.
a_bakshaev
13.12.2016 02:02+1Ну да, это минус ассемблера, под каждый набор инструкций и даже иногда под микроархитектуру код нужен свой. Но опять же, это если код прям супер критичный типа Фурье или gzip сжатия или с ограничениями по размеру. А так, в большинстве случаев, даже у нас, в x86 performance ориентированой библиотеке используются интринсики в последнее время. Те 10% производительности от ассемблера, зачастую не стоят затрат на разработку и главное поддержку в будущем, но за некоторыми исключениями.
immaculate
13.12.2016 15:20+1Помимо уже упомянутых ограничений, есть еще такая проблема: в большинстве проектов сейчас код меняется так быстро, что не успеваешь только оптимизировать. Как только оптимизировал, код становится или ненужен, или требования меняются так, что правки сводят эффект от оптимизации на нет.
Понятно, что у каждого проекта своя специфика, но в современном мире все стараются куда-то бежать как можно быстрее, и если останавливаться ради оптимизации, конкуренты затопчут.
Кроме того, неоптимизированный код подстегивает продажи нового оборудования. Win-win situation! Шутка. :)
homm
13.12.2016 16:54Все же надо понимать, что меняется код проектов, т.е. бизнес-логика, а на ассемблере пишут библиотеки, т.е. базовые алгоритмы вроде той же сортировки. Они не меняются так быстро.
VBKesha
Можно было дизассемблировать ещё то что делали компиляторы и сравнить в чем разница между ними и вашим кодом.
kk86
Статья переводная…
homm
То есть нельзя было дизассемблировать то, что делали компиляторы и сравнить в чем разница между ними и кодом автора?