Обгоняем компилятор

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

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

Но так ли это? Давайте не будем просто воспринимать на веру слова некоторых парней в интернете, как библейское откровение, а проведём небольшой эксперимент и выясним.

Мы просто возьмём несложный кусок кода и рассмотрим его. Я не собираюсь выбрать пример, который может выиграть, в большой степени, от экзотических встроенных функций. Вместо этого я возьму старый стандартный 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 — Все коды, использованные в данной статье.

Автор: LukinB

Источник