[Перевод] Обгоняем компилятор
Причиной обычно указывают то, что у современного центрального процессора имеется столько конвейеров и конфликтов по управлению, с которыми приходится иметь дело, что простая программа ассемблера не сделает работу хорошо, обращаясь с ними.
Но так ли это? Давайте не будем просто воспринимать на веру слова некоторых парней в интернете, как библейское откровение, а проведём небольшой эксперимент и выясним.
Мы просто возьмём несложный кусок кода и рассмотрим его. Я не собираюсь выбрать пример, который может выиграть, в большой степени, от экзотических встроенных функций. Вместо этого я возьму старый стандартный 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Ничего необычного. Это не самый лучший алгоритм сортировки в мире, а это — даже не самая лучшая реализация, но он простой и делает своё дело неплохо.
Теперь попробуем прямо выполнить простую реализацию такого подхода в ассемблере:
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 — Все коды, использованные в данной статье.
Комментарии (1)
VBKesha
12 декабря 2016 в 17:31
+6↑
↓
Можно было дизассемблировать ещё то что делали компиляторы и сравнить в чем разница между ними и вашим кодом.
