Статья SIMD | Сверхоптимизация

[quiedcpp]

Если в друх словах: Это возможность (команды), позволяющте выполнять операции на большом количестве данных за одну операцию.
В случае x86 процессоров это инструкции сделанные в расширениях MMX, SSE, SSE2, SSE3, SSE4, SSE4.1, SSE4.2, AVX, AVX2, AVX51

(Далее идёт краткий пересказ одной давней статьи как напоминание что есть такие вещи, хоть и редко используются)

Спойлер: Задача

Дан неупорядоченный массив arr с числами типа uint16_t. Необходимо найти количество вхождений числа v в массив arr.

Класическое решение:

int64_t cnt = 0;
for (int i = 0; i < ARR_SIZE; ++i)
    if (arr[i] == v)
        ++cnt;

Benchmark: Time - 2084ns | Iterations - 333079 (Запомните это)

Что такое SIMD​

SIMD (Single Instruction, Multiple Data) — одиночный поток команд, множественный поток данных. В x86 совместимых процессорах эти команды были реализованы в нескольких поколениях SSE и AVX расширениях процессора. Команд довольно много, полный список от Intel можно посмотреть на странице software.intel.com/sites/landingpage/IntrinsicsGuide. В десктопных процессорах AVX расширения недоступны, поэтому сосредоточимся на SSE.

Для работы с SIMD в C/C++ в код надо добавить

#include <x86intrin.h>

Что же можно ускорить в коде из 3 строк?

Хорошо бы уменьшить количество итераций и проводить сравнение сразу с несколькими элементами за один цикл. Открываем сайт от Intel, выбираем только SSE расширения и категорию «Compare». Первыми в списке идёт семейство функций __m128i _mm_cmpeq_epi* (__m128i a, __m128i b).

Вариант 1​

int64_t cnt = 0;

// Превращаем искомое значение в "массив" из 8 одинаковых элементов
auto sseVal = _mm_set1_epi16(VAL);
for (int i = 0; i < ARR_SIZE; i += 8) {
    // Для каждого блока из 8 элементов помещаем в переменную для сравнения
    auto sseArr = _mm_set_epi16(arr[i + 7], arr[i + 6], arr[i + 5], arr[i + 4], arr[i + 3], arr[i + 2], arr[i + 1], arr[i]);
    // Получаем количество совпадений * 2
    cnt += _popcnt32(_mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr)));
}
// Делим на 2
cnt >>= 1;

Benchmark: Time - 937 ns | Iterations - 746435
Это далеко не предел.

Спойлер: Ассемблер

--------------- Копирование 8 элементов в sseArr ---------------
            auto sseArr = _mm_set_epi16(arr[i + 7], arr[i + 6], arr[i + 5], arr[i + 4], arr[i + 3], arr[i + 2],
  40133a:       48 8b 05 77 1d 20 00    mov    0x201d77(%rip),%rax        # 6030b8 <_ZL3arr>
                                        arr[i + 1], arr[i]);
  401341:       48 63 8d 9c fe ff ff    movslq -0x164(%rbp),%rcx
            auto sseArr = _mm_set_epi16(arr[i + 7], arr[i + 6], arr[i + 5], arr[i + 4], arr[i + 3], arr[i + 2],
  401348:       66 8b 54 48 0e          mov    0xe(%rax,%rcx,2),%dx
  40134d:       66 8b 74 48 0c          mov    0xc(%rax,%rcx,2),%si
  401352:       66 8b 7c 48 0a          mov    0xa(%rax,%rcx,2),%di
  401357:       66 44 8b 44 48 08       mov    0x8(%rax,%rcx,2),%r8w
  40135d:       66 44 8b 4c 48 06       mov    0x6(%rax,%rcx,2),%r9w
  401363:       66 44 8b 54 48 04       mov    0x4(%rax,%rcx,2),%r10w
                                        arr[i + 1], arr[i]);
  401369:       66 44 8b 1c 48          mov    (%rax,%rcx,2),%r11w
  40136e:       66 8b 5c 48 02          mov    0x2(%rax,%rcx,2),%bx
            auto sseArr = _mm_set_epi16(arr[i + 7], arr[i + 6], arr[i + 5], arr[i + 4], arr[i + 3], arr[i + 2],
  401373:       66 89 55 ce             mov    %dx,-0x32(%rbp)
  401377:       66 89 75 cc             mov    %si,-0x34(%rbp)
  40137b:       66 89 7d ca             mov    %di,-0x36(%rbp)
  40137f:       66 44 89 45 c8          mov    %r8w,-0x38(%rbp)
  401384:       66 44 89 4d c6          mov    %r9w,-0x3a(%rbp)
  401389:       66 44 89 55 c4          mov    %r10w,-0x3c(%rbp)
  40138e:       66 89 5d c2             mov    %bx,-0x3e(%rbp)
  401392:       66 44 89 5d c0          mov    %r11w,-0x40(%rbp)
  401397:       44 0f b7 75 c0          movzwl -0x40(%rbp),%r14d
  40139c:       c4 c1 79 6e c6          vmovd  %r14d,%xmm0
  4013a1:       44 0f b7 75 c2          movzwl -0x3e(%rbp),%r14d
  4013a6:       c4 c1 79 c4 c6 01       vpinsrw $0x1,%r14d,%xmm0,%xmm0
  4013ac:       44 0f b7 75 c4          movzwl -0x3c(%rbp),%r14d
  4013b1:       c4 c1 79 c4 c6 02       vpinsrw $0x2,%r14d,%xmm0,%xmm0
  4013b7:       44 0f b7 75 c6          movzwl -0x3a(%rbp),%r14d
  4013bc:       c4 c1 79 c4 c6 03       vpinsrw $0x3,%r14d,%xmm0,%xmm0
  4013c2:       44 0f b7 75 c8          movzwl -0x38(%rbp),%r14d
  4013c7:       c4 c1 79 c4 c6 04       vpinsrw $0x4,%r14d,%xmm0,%xmm0
  4013cd:       44 0f b7 75 ca          movzwl -0x36(%rbp),%r14d
  4013d2:       c4 c1 79 c4 c6 05       vpinsrw $0x5,%r14d,%xmm0,%xmm0
  4013d8:       44 0f b7 75 cc          movzwl -0x34(%rbp),%r14d
  4013dd:       c4 c1 79 c4 c6 06       vpinsrw $0x6,%r14d,%xmm0,%xmm0
  4013e3:       44 0f b7 75 ce          movzwl -0x32(%rbp),%r14d
  4013e8:       c4 c1 79 c4 c6 07       vpinsrw $0x7,%r14d,%xmm0,%xmm0
  4013ee:       c5 f9 7f 45 b0          vmovdqa %xmm0,-0x50(%rbp)
  4013f3:       c5 f9 6f 45 b0          vmovdqa -0x50(%rbp),%xmm0
  4013f8:       c5 f9 7f 85 80 fe ff    vmovdqa %xmm0,-0x180(%rbp)
  4013ff:       ff
--------------- Подсчёт совпавших элементов ---------------
            cnt += _popcnt32(_mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr)));
  401400:       c5 f9 6f 85 a0 fe ff    vmovdqa -0x160(%rbp),%xmm0
  401407:       ff
  401408:       c5 f9 6f 8d 80 fe ff    vmovdqa -0x180(%rbp),%xmm1
  40140f:       ff
  401410:       c5 f9 7f 45 a0          vmovdqa %xmm0,-0x60(%rbp)
  401415:       c5 f9 7f 4d 90          vmovdqa %xmm1,-0x70(%rbp)
  40141a:       c5 f9 6f 45 a0          vmovdqa -0x60(%rbp),%xmm0
  40141f:       c5 f9 6f 4d 90          vmovdqa -0x70(%rbp),%xmm1
  401424:       c5 f9 75 c1             vpcmpeqw %xmm1,%xmm0,%xmm0
  401428:       c5 f9 7f 45 80          vmovdqa %xmm0,-0x80(%rbp)
  40142d:       c5 f9 6f 45 80          vmovdqa -0x80(%rbp),%xmm0
  401432:       c5 79 d7 f0             vpmovmskb %xmm0,%r14d
  401436:       44 89 b5 7c ff ff ff    mov    %r14d,-0x84(%rbp)
  40143d:       44 8b b5 7c ff ff ff    mov    -0x84(%rbp),%r14d
  401444:       f3 45 0f b8 f6          popcnt %r14d,%r14d
  401449:       49 63 c6                movslq %r14d,%rax
  40144c:       48 03 85 b8 fe ff ff    add    -0x148(%rbp),%rax
  401453:       48 89 85 b8 fe ff ff    mov    %rax,-0x148(%rbp)

Видно, что очень много команд процессора занимает копирование элементов массива в sseArr.

Вариант 2​

int64_t cnt = 0;

auto sseVal = _mm_set1_epi16(VAL);
    for (int i = 0; i < ARR_SIZE; i += 8) {
        auto sseArr = _mm_loadu_si128((__m128i *) &arr[i]);
        cnt += _popcnt32(_mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr)));
    }

Benchmark: Time - 454 ns | Iterations - 1548455

Вариант 3​

SSE инструкции работают с выровненной памятью по 16 байт. Функция _mm_loadu_si128 позволяет избежать это ограничение, но если выделять память под массив с помощью функции aligned_alloc(16, SZ), то можно будет напрямую передавать адрес в SSE инструкцию:

int64_t cnt = 0;

auto sseVal = _mm_set1_epi16(VAL);
for (int i = 0; i < ARR_SIZE; i += 8) {
    auto sseArr = *(__m128i *) &allignedArr[i];
    cnt += _popcnt32(_mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr)));
}

Benchmark: Time - 395 ns | Iterations - 1770803


Все приведённые ассемблерные листинги были получены после компиляции с -O0. Если включить -O3, то компилятор довольно хорошо оптимизирует код и такого разделения по времени уже не будет:
BM_Count - 129 ns | Iterations - 5359145
BM_SSE_COUNT_SET_EPI - 70 ns | Iterations - 9936200
BM_SSE_COUNT_LOADU - 49 ns | Iterations - 14187659
BM_SSE_COUNT_DIRECT - 53 ns | Iterations - 13401612

 

[quiedcpp]

То, что компилятор «додумался» сделать на маленькой программке, совсем не гарантирует того, что он это сделает на большой. Поэтому лучше самому понимать, как писать более оптимальные варианты.

 

[Quake3]

Очевидно, это и есть та мега-статья, за которую вы хотели получить эксперта? Материал крутой, да. Не успели тут запостить, как уже скопипастили какие-то школьники https://vk.com/@scienceandlive-uskoryaem-neuskoryaemoe-ili-znakomimsya-s-simd
ничего святого нет для копипастеров.

 

[quiedcpp]

Очевидно, это и есть та мега-статья, за которую вы хотели получить эксперта? Материал крутой, да. Не успели тут запостить, как уже скопипастили какие-то школьники https://vk.com/@scienceandlive-uskoryaem-neuskoryaemoe-ili-znakomimsya-s-simd
ничего святого нет для копипастеров.

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

 

[Quake3]

процетировал

Прейму

Там копипаст, что даже бенчмарки совпали и имена переменных. Удивительно, это с лолза этого самого такие приходят или откуда? За копипаст получить эксперта..