Векторизация

Рассмотрим следующую программу, в которой считается сумма одномерного целочисленного массива:

#pragma GCC optimize("O3")
// ^ включает самый "агрессивный" уровень оптимизации
// то же самое, что добавить флаг "-O3" при компиляции из консоли

#include <iostream>
using namespace std;

const int n = 1e5;
int a[n], s = 0;

int main() {
    for (int t = 0; t < 100000; t++)
        for (int i = 0; i < n; i++)
            s += a[i];

    return 0;
}

Если скомпилировать этот код под GCC без всяких дополнительных настроек и запустить, он отработает за 2.43 секунды.

Добавим теперь следующую магическую директиву в самое начало программы:

#pragma GCC target("avx2")
// ...остальное в точности как было

Скомпилировавшись и запустившись при тех же условиях, программа завершается уже за 1.24 секунды. Это почти в два раза быстрее, при том, что сам код и уровень оптимизации мы не меняли.

Всё дело в том, что в современных процессорах есть специальные «векторные» инструкции, которые могут применять какую-то одну операцию сразу к блоку из скольки-то последовательных элементов, а не только к одному скаляру за раз. Такая модель называется SIMD-параллелизмом (англ. single instruction, multiple data).

На разных микроархитектурах поддержка SIMD-инструкций разная. Помимо самого набора инструкций, различаются ещё и размеры векторных регистров — сейчас это может быть 128, 256 или 512 бит.

На архитектуре x86 (которая используется на подавляющем большинстве десктопных и серверных CPU) все SIMD-расширения в основном сохраняют обратную совместимость: более новое подразумевает все более старые. По умолчанию в компиляторах C++ предполагается только то, что таргет (компьютер, на котором должна исполняться программа) поддерживает набор инструкций «SSE2» — что должно быть верно для почти всех CPU, появившихся в этом веке.

На большинстве же современных CPU есть поддержка AVX2, ключевое отличие которого заключается в том, что векторные регистры, с которыми он работает, увеличились в два раза — с 128 до 256 бит — и соответственно за одну операцию можно сложить уже не 4, а целых 8 int-ов. Соответственно, когда мы сообщаем оптимизирующему компилятору дополнительную информацию о микроархитектуре (через #pragma GCC target("avx2") или флаги вроде -mavx2 или -march=native), он получает доступ к более широким регистрам и ускоряет нашу программу в ожидаемые два раза.

Однако векторизация имеет гораздо больше нюансов, чем просто добавление прагм — для более основательного подхода автор рекомендует соответствующую главу «Algorithms for Modern Hardware».