Обганяємо компілятор

На форумах і в інших місцях спілкування розробників зараз часто повторюється, що пристойний оптимізуючий компілятор завжди буде перевершувати жалюгідні, майже людські потуги програми, написаної вручну на асемблері. Є рідкісні випадки, як, наприклад, MPEG-декодери, де хороше використання SIMD інструкцій може дозволити ассемблированию повністю перевершити компілятор. Але зазвичай, і скрізь, ми чуємо, що компілятор завжди працює краще.

Причиною зазвичай вказують на те, що у сучасного центрального процесора є стільки конвеєрів і конфліктів по керуванню, з якими доводиться мати справу, що проста програма асемблера не зробить роботу добре, звертаючись з ними.

Але чи це так? Давайте не будемо сприймати на віру слова деяких хлопців в інтернеті, як біблійне одкровення, а проведемо невеличкий експеримент і з'ясуємо.

Ми просто візьмемо нескладний шматок коду і розглянемо його. Я не збираюся вибрати приклад, який може виграти, у великій мірі, від екзотичних вбудованих функцій. Замість цього я візьму старий стандартний quicksort.

Тут показана проста швидка сортування в C++, яку ми протестуємо:

struct Item { int key; int value; };

extern "С" 
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 — Всі коди, використані в даній статті.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.