Loop unrolling. Simd
#опытным

У современных процессоров есть возможность выполнять операции над несколькими значениями одновременно. Достигается это с помощью векторных регистров - специальных длинных регистров процессора, куда могут помещаться 128 бит (SSE), 256 бит (AVX), 512 бит (AVX-512) данных. Например в 256-битном регистре помещается 4 double, 8 float, 16 short, 32 char.

После того, как мы загрузили данные в регистры, мы можем с помощью специальных инструкций(Single Instruction Multiple Data - SIMD) обрабатывать разом все значения в регистре.

Например есть такой незамысловатый код:

for (int i = 0; i < 1024; ++i) {
    arr[i] += 5;
}

Здесь мы по очереди увеличиваем элементы массива.

Но их можно увеличивать сразу пачками с помощью SIMD интринсиков компилятора:

__m128i five = _mm_set1_epi32(5);

for (int i = 0; i < 1024; i += 4) {
    __m128i data = _mm_loadu_si128((__m128i*)&arr[i]);
    data = _mm_add_epi32(data, five);
    _mm_storeu_si128((__m128i*)&arr[i], data);
}

Векторные регистры работают только друг с другом, поэтому в начале помещаем число 5 в каждую 32-битную ячейку в 128-битном регистре. А потом загружаете элементы массива в другой регистр, одной операцией складываете 4 интовых значения и затем выгружаете получившиеся числа обратно в массив.

Эту ситуацию называют по-разному - и векторизация цикла и развертка цикла с использованием векторных инструкций. Количество итераций в цикле мы все равно снизили.

Вот примерчик чуть по-сложнее - полноценная функция, суммирующая 2 float массива переменной длины:

void sum_arrays_sse(const float* a, const float* b, float* c, size_t n) {
    size_t i = 0;
    for (; i + 3 < n; i += 4) {
        // Load 4 floats from a and b
        __m128 va = _mm_loadu_ps(&a[i]);
        __m128 vb = _mm_loadu_ps(&b[i]);
        // Add them all
        __m128 vc = _mm_add_ps(va, vb);
        // Store results
        _mm_storeu_ps(&c[i], vc);
    }
    // Handle tail
    for (; i < n; ++i) {
        c[i] = a[i] + b[i];
    }
}

Опять же. Важно понимать, что компилятор за вас может такие простые вычисления векторизировать в том числе и с simd инструкциями. Поэтому самостоятельно используйте их только там, где компилятор бессилен.

Зато в подходящей для применения simd нетривиальной задаче вы можете получить ускорение в 2-10 раз по сравнению с ванильной версией алгоритма. Когда-то давно я работал в Intel перформанс библиотеках, так там почти все алгоритмы ускорялись интринсиками. И в отдельных случаях ускорение было на порядок(например алгоритмы блочных шифров).

Поэтому SIMD - это мощная штука. Но применять их надо применять с умом. И всегда мерять производительность кода бэнчмарками, чтобы не наоптимизировать чего лишнего.

Learn to do things simultaneously. Stay cool.

#compiler #optimization #performance