Иногда человек может обнаружить такие возможности оптимизации, которые не видит компилятор. В этой статье мы начнём с цикла, сгенерированного из кода Си с помощью clang, и скорректируем его разными способами, попутно измеряя прирост в скорости.
Эта статья публиковалась на главной странице HackerNews, и к её обсуждению вы можете присоединиться здесь.
Дисклеймер: я не эксперт по оптимизациям. По факту мой опыт касается высокоуровневых, чисто функциональных языков, где программист обычно не думает о том, как программа выполняется.
Листинги кода из этой статьи можно найти на GitHub.
Часть I
▍ Функция
Мы начнём с функции, которая перебирает строку и в зависимости от встречаемых символов инкрементирует либо декрементирует число.
int run_switches(char *input) {
int res = 0;
while (true) {
char c = *input++;
switch (c) {
case '':
return res;
case 's':
res += 1;
break;
case 'p':
res -= 1;
break;
default:
break;
}
}
}
Инкрементирование происходит при встрече s (successor, следующий элемент), а декрементирование при встрече p (predecessor, предыдущий элемент).
Это достаточно небольшая функция, которую gcc и clang должны неплохо оптимизировать. Может, даже оптимально? Изначально я написал её, чтобы увидеть, создаст gcc таблицу переходов или же поиск.
Вот, что выдал clang (заполняющие no-op удалены и комментарии добавлены вручную):
# llvm-objdump -d --symbolize-operands --no-addresses --x86-asm-syntax=intel --no-show-raw-insn loop-1-clang.c.o
run_switches:
xor eax, eax # res = 0
loop: # while (true) {
movsx ecx, byte ptr [rdi] # c = *input
test ecx, ecx # if (c == '')
je ret # return
add rdi, 1 # input++
cmp ecx, 'p' # if (c == 'p')
je p # goto p
cmp ecx, 's' # if (c == 's')
jne loop # continue
add eax, 1 # res++
jmp loop # continue
p: add eax, -1 # res--
jmp loop # }
ret: ret
# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-1-clang.c.o
run_switches:
xor eax, eax
loop:
╭────➤ movsx ecx, byte ptr [rdi]
│ test ecx, ecx
│ ╭─── je ret
│ │ add rdi, 1
│ │ cmp ecx, 'p'
│ │ ╭─ je p
│ │ │ cmp ecx, 's'
├─│─│─ jne loop
│ │ │ add eax, 1
├─│─│─ jmp loop
p: │ │ ╰➤ add eax, -1
╰─│─── jmp loop
ret: ╰──➤ ret
- Время выполнения: 3.23 s
- Скорость: 295.26 MiB/s
Gcc выдал немного больше кода, который выполнился чуть быстрее.
Этот код довольно прост – в нём есть три условных инструкции ветвления (je, je, jne), ведущие к четырём возможным блокам: , s, p, а также блок для всех других символов.
▍ Перестройка ветвлений
Тем не менее об этом цикле мы кое-что знаем. Нам известно, что выход из него происходит только при достижении нуль-терминатора (). Генерируемый clang код сначала выполняет проверку наличия нуль-терминатора, но в этом нет смысла. Максимальное число нуль-терминированных строк, с которыми встретится эта функция, равно 1. Поэтому нам следует оптимизировать функцию так, чтобы сначала выполнялась проверка присутствия p или s и других символов, а не нуль-терминатора.
Немного перестроим наш цикл.
run_switches:
xor eax, eax
loop: ╭─────➤ movsx ecx, byte ptr [rdi]
│ inc rdi
│ cmp ecx, 'p'
│ ╭──── je p
│ │ cmp ecx, 's'
│ │ ╭── je s
│ │ │ test ecx, ecx
├─│─│── jne loop
│ │ │ ret
p: │ ╰─│─➤ dec eax
├───│── jmp loop
s: │ ╰─➤ inc eax
╰────── jmp loop
run_switches:
xor eax, eax
loop: movsx ecx, byte ptr [rdi]
inc rdi
cmp ecx, 'p'
je p
cmp ecx, 's'
je s
test ecx, ecx
jne loop
ret
p: dec eax
jmp loop
s: inc eax
jmp loop
Отлично! Теперь мы выполняем ветвление раньше — при встрече p или s, а не редкого .
- Время выполнения: 3.10 s
- Прирост скорости:: 1.04x
- Скорость: 307.64 MiB/s
▍ Перестановка блоков
Итак, оба типичных случая (p и s) переместились в начало цикла, так почему бы нам не удалить одну из этих ветвей, поместив её целевой блок (или BasicBlock™, для специалистов по компиляторам) в начало цикла?
run_switches:
xor eax, eax
╭───── jmp loop
s: │ ╭──➤ inc eax
loop: ├─│──➤ movsx ecx, byte ptr [rdi]
│ │ inc rdi
│ │ cmp ecx, 'p'
│ │ ╭─ je p
│ │ │ cmp ecx, 's'
│ ╰─│─ je s
│ │ test ecx, ecx
├───│─ jne loop
│ │ ret
p: │ ╰➤ dec eax
╰───── jmp loop
run_switches:
xor eax, eax
jmp loop # This is new
s: inc eax # This is up here now
loop: movsx ecx, byte ptr [rdi]
inc rdi
cmp ecx, 'p'
je p
cmp ecx, 's'
je s
test ecx, ecx
jne loop
ret
p: dec eax
jmp loop
Прекрасно! Теперь наш блок s перескакивает (fall through) в цикл без ветвления. Неплохо.
Вы заметите, что теперь нам нужно переходить в цикл из начала функции, чтобы избежать выполнения блока s. Хотя это довольно хороший компромисс – переход в цикл из функции происходит один раз в то время, как символов s мы встречаем множество.
Но насколько быстрым окажется этот вариант?
- Время выполнения: 2.98 s
- Общее ускорение: 1.08x
- Скорость: 320.02 MiB/s
▍ Замена переходов арифметикой
Условные переходы нежелательны, но как насчёт стандартного безусловного jmp? Что, если попробовать убрать возвращение в цикл p:?
Декремент равнозначен двум декрементам и одному инкременту, правильно? Значит, давайте используем его для перескакивания в s:.
run_switches:
xor eax, eax
╭────── jmp loop
p: │ ╭─➤ sub eax, 2
s: │ ╭─│─➤ inc eax
loop: ├─│─│─➤ movsx ecx, byte ptr [rdi]
│ │ │ inc rdi
│ │ │ cmp ecx, 'p'
│ │ ╰── je p
│ │ cmp ecx, 's'
│ ╰──── je s
│ test ecx, ecx
╰────── jne loop
ret
run_switches:
xor eax, eax
jmp loop
p: sub eax, 2
s: inc eax
loop: movsx ecx, byte ptr [rdi]
inc rdi
cmp ecx, 'p'
je p
cmp ecx, 's'
je s
test ecx, ecx
jne loop
ret
Вот мы и избавились от ещё одной инструкции ветвления, используя простую арифметику. Хорошо. Но будет ли этот код быстрее?
- Время выполнения: 2.87 s
- Общее ускорение: 1.12x
- Скорость: 332.29 MiB/s
Забавный факт. Всё это время мы сравнивали производительность с выводом clang 16, но gcc 12 на деле выдавал более быстрый (хотя и более громоздкий) код. Его версия выполняется также за 2,87 с, так что мы только её догнали. Но при этом наша программа состоит из 13 инструкций, а программа gcc – из 19.
Похоже, что код gcc развернул цикл и до определённой степени повторно использует блоки кейсов.
▍ Без ветвления
Хорошо, но эти условные ветви являются реальной проблемой, не так ли? Как ускорить их прогнозирование? Я не знаю, поэтому давайте просто не будем его использовать.
# rdi: char *input
# eax: output
# r8: 1
# edx: -1
# ecx: char c
# esi: n
run_switches:
xor eax, eax
mov r8d, 1
mov edx, -1
loop:
╭──➤ movsx ecx, byte ptr [rdi]
│ test ecx, ecx
│ ╭─ je ret
│ │ inc rdi
│ │ mov esi, 0
│ │ cmp ecx, 'p'
│ │ cmove esi, edx
│ │ cmp ecx, 's'
│ │ cmove esi, r8d
│ │ add eax, esi
╰─│─ jmp loop
ret: ╰➤ ret
# rdi: char *input
# eax: ouput
# r8: 1
# edx: -1
# ecx: char c
# esi: n
run_switches:
xor eax, eax # res = 0
mov r8d, 1 # need 1 in a register later
mov edx, -1 # need -1 in a register later
loop: # while (true) {
movsx ecx, byte ptr [rdi] # char c = *input
test ecx, ecx # if (c == '')
je ret # return
inc rdi # input++
mov esi, 0 # n = 0
cmp ecx, 'p' # if (c == 'p')
cmove esi, edx # n = -1
cmp ecx, 's' # if (c == 's')
cmove esi, r8d # n = 1
add eax, esi # res += n
jmp loop # }
ret: ret
Вау, мы удалили из графа потока управления множество стрелок…
Вместо условного ветвления/переходов мы, в зависимости от текущего символа, используем для сложения разные значения. Это мы делаем с помощью cmove или «условного перехода согласно равенству».
Правила таковы: по умолчанию использовать ноль, при встрече s использовать 1, а при встрече p использовать -1. При этом всегда выполнять сложение.
Неплохой поворот, но будет ли так быстрее?
- Время выполнения: 0.48 s
- Общее ускорение: 6.73x
- Скорость: 1.94 GiB/s
Да уж, получилось чертовски быстро.
▍ Освобождение регистра
В x86_64 есть ещё один способ условной установки регистра (1 байта) на 0 или 1. Он называется sete. Давайте используем его и избавимся от нашего r8d.
run_switches:
xor eax, eax
mov edx, -1
loop:
╭──➤ movsx ecx, byte ptr [rdi]
│ test ecx, ecx
│ ╭─ je ret
│ │ inc rdi
│ │ mov esi, 0
│ │ cmp ecx, 's'
│ │ sete sil
│ │ cmp ecx, 'p'
│ │ cmove esi, edx
│ │ add eax, esi
╰─│─ jmp loop
ret: ╰➤ ret
run_switches:
xor eax, eax # res = 0
mov edx, -1 # need -1 in a register later
loop: # while (true) {
movsx ecx, byte ptr [rdi] # char c = *input
test ecx, ecx # if (c == '')
je ret # return
inc rdi # input++
mov esi, 0 # n = 0
cmp ecx, 's' # c == 's'?
sete sil # n = 0|1
cmp ecx, 'p' # if (c == 'p')
cmove esi, edx # n = -1
add eax, esi # res += n
jmp loop # }
ret: ret
Но обеспечит ли это ускорение?
- Время выполнения: 0.51 s
- Общее ускорение: 6.33x
- Скорость: 1.83 GiB/s
Что ж, получилось медленнее, чем при использовании cmov. Думаю, нет смысла задействовать меньше регистров или использовать 8-битные операции вместо 32-битных.
▍ Другие попытки
Я попытался развернуть цикл нашей лучшей версии кода. В результате код замедлился.
Тогда я решил выровнять начало цикла по 16-байтовой границе (профессиональный совет: вы можете добавить .align <bytes> перед меткой, и GNU Assembler вставит инструкции nop за вас). Это тоже замедлило код.
▍ Настройка бенчмарка
$ uname -sr
Linux 6.1.33
$ lscpu
...
Model name: AMD Ryzen 5 5625U with Radeon Graphics
CPU family: 25
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
$ clang --version
clang version 16.0.1
$ gcc --version
gcc (GCC) 12.2.0
Версии Си были скомпилированы с использованием -march=native, сообщая компилятору, что нужно создать код, который будет выполняться быстро на конкретно моём процессоре, а не каком-то среднем x86_64.
Этот бенчмарк тысячу раз прогоняет функцию для списка из миллиона символов (со случайными вхождениями p и s).
Для каждой версии я выполнил этот тест несколько раз, выбрав лучшие результаты.
▍ Выводы
Порой можно добиться 6-кратного ускорения путём ручной правки сжатого цикла Си в ассемблере и оптимизации с помощью техник, которые в компиляторы, похоже, ещё не встроили.
Но это ещё не конец, и далее вас ждёт вторая часть моего эксперимента.
Часть II
В первой части мы написали небольшую программу на Си, скомпилировали её, дизассемблировали, а затем скорректировали, добившись шестикратного ускорения. Теперь же мы этот результат улучшим.
Листинги из этой части также лежат на GitHub.
Первая версия нашей программы могла обрабатывать 295.26 MiB/s, а её лучший вариант – 1.94 GiB/s.
Итак, начнём с первой версии:
int run_switches(char *input) {
int res = 0;
while (true) {
char c = *input++;
switch (c) {
case '':
return res;
case 's':
res += 1;
break;
case 'p':
res -= 1;
break;
default:
break;
}
}
}
# llvm-objdump -d --symbolize-operands --no-addresses --x86-asm-syntax=intel --no-show-raw-insn loop-1-gcc.c.o
run_switches:
xor eax, eax # res = 0
loop: # while (true) {
movsx ecx, byte ptr [rdi] # c = *input
test ecx, ecx # if (c == '')
je ret # return
add rdi, 1 # input++
cmp ecx, 'p' # if (c == 'p')
je p # goto p
cmp ecx, 's' # if (c == 's')
jne loop # continue
add eax, 1 # res++
jmp loop # continue
p: add eax, -1 # res--
jmp loop # }
ret: ret
# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-2-gcc.c.o
run_switches:
xor eax, eax
loop:
╭────➤ movsx ecx, byte ptr [rdi]
│ test ecx, ecx
│ ╭─── je ret
│ │ add rdi, 1
│ │ cmp ecx, 'p'
│ │ ╭─ je p
│ │ │ cmp ecx, 's'
├─│─│─ jne loop
│ │ │ add eax, 1
├─│─│─ jmp loop
p: │ │ ╰➤ add eax, -1
╰─│─── jmp loop
ret: ╰──➤ ret
- Время выполнения: 3.23 s
- Скорость: 295.26 MiB/s
▍ Отбрасывание кейсов
Мы выразили задачу логическим образом сверху вниз. В ней мы перебираем входные данные по одному символу и выполняем анализ кейсов для возможных вариантов (иными словами, переключаем символы).
В зависимости от результатов анализа кейсов мы выполняем разный код.
Чтобы этого избежать, мы объединим пути кода, имеющие общую структуру. Оба кейса – p и s – добавляют в аккумулятор число. Может, тогда вместо выполнения анализа кейсов для перехода к следующему пути кода, мы будем с помощью того же анализа получать число для прибавления?
Это число можно искать в массиве:
#include <stdbool.h>
static
int to_add[256] = {
['s'] = 1,
['p'] = -1,
};
int run_switches(const char *input) {
int res = 0;
while (true) {
char c = *input++;
if (c == '') {
return res;
} else {
res += to_add[(int) c];
}
}
}
# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-2-gcc.c.o
run_switches:
movsx rax, byte ptr [rdi]
lea rdx, [rdi+1]
xor ecx, ecx
lea rsi, [rip+0] # <run_switches+0x11>
test al, al
╭─── je ret
│ nop dword ptr [rax]
loop: │ ╭➤ add rdx, 0x1
│ │ add ecx, dword ptr [rsi+rax*4]
│ │ movsx rax, byte ptr [rdx-1]
│ │ test al, al
│ ╰─ jne loop
ret: ╰──➤ mov eax, ecx
ret
# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-2-clang.c.o
run_switches:
mov cl, byte ptr [rdi]
test cl, cl
╭─── je ret
│ add rdi, 0x1
│ xor eax, eax
│ lea rdx, [rip+0x0] # <run_switches+0x13>
│ cs nop word ptr [rax+rax*1+0x0]
│ nop dword ptr [rax]
loop: │ ╭➤ movsx rcx, cl
│ │ add eax, dword ptr [rdx+rcx*4]
│ │ movzx ecx, byte ptr [rdi]
│ │ add rdi, 0x1
│ │ test cl, cl
│ ╰─ jne loop
│ ret
ret: ╰──➤ xor eax, eax
ret
- Время выполнения GCC: 0.47 s
- Скорость GCC: 1.98 GiB/s
- Время выполнения Clang: 0.25 s
- Скорость Clang: 3.72 GiB/s
Неплохо. В случае gcc мы достигли скорости нашей лучшей (cmov) версии из предыдущей части, но вывод clang почти вдвое её опередил.
Между gcc и clang присутствует какое-то реально странное отличие. Насколько сильной может быть разница в быстродействии между этими строками:
movzx ecx, byte ptr [rdi]
movsx rax, byte ptr [rdx-1]
Думаю, что смогу заставить gcc cгенерировать версию с movzx (перемещение и дополнение нулями) вместо movsx (перемещение и дополнение символами), используя в качестве инструкции беззнаковый целочисленный тип, то есть uint8_t или unsigned char вместо char.
Попробуем:
#include <stdbool.h>
#include <stdint.h>
static
int to_add[256] = {
['s'] = 1,
['p'] = -1,
};
int run_switches(const uint8_t *input) {
int res = 0;
while (true) {
uint8_t c = *input++;
if (c == '') {
return res;
} else {
res += to_add[(int) c];
}
}
}
# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-3-gcc.c.o
run_switches:
movzx eax, byte ptr [rdi]
lea rdx, [rdi+0x1]
xor ecx, ecx
lea rsi, [rip+0x0]
test al, al
╭───── je ret
│ nop dword ptr [rax+0x0]
loop: │ ╭─➤ movzx eax, al
│ │ add rdx, 1
│ │ add ecx, dword ptr [rsi+rax*4]
│ │ movzx eax, byte ptr [rdx-1]
│ │ test al, al
│ ╰── jne loop
ret: ╰────➤ mov eax,ecx
ret
# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-3-clang.c.o
run_switches:
mov cl, byte ptr [rdi]
test cl, cl
╭───── je ret
│ add rdi, 1
│ xor eax, eax
│ lea rdx, [rip+0x0]
│ cs nop word ptr [rax+rax*1+0x0]
│ nop dword ptr [rax]
loop: │ ╭─➤ movzx ecx, cl
│ │ add eax, dword ptr [rdx+rcx*4]
│ │ movzx ecx, byte ptr [rdi]
│ │ add rdi, 1
│ │ test cl, cl
│ ╰── jne loop
│ ret
ret: ╰────➤ xor eax,eax
ret
Сработало, но окажется ли этот код быстрее?
- Время выполнения GCC: 0.47 s
- Скорость GCC: 1.98 GiB/s
- Время выполнения Clang: 0.25 s
- Скорость Clang: 3.72 GiB/s
Нет. Всё в точности, как и прежде. Хорошо, тогда в чём отличие между этими вариантами:
loop: ╭─➤ movzx eax, al
│ add rdx, 1
│ add ecx, dword ptr [rsi+rax*4]
│ movzx eax, byte ptr [rdx-1]
│ test al, al
╰── jne loop
loop: ╭─➤ movzx ecx, cl
│ add eax, dword ptr [rdx+rcx*4]
│ movzx ecx, byte ptr [rdi]
│ add rdi, 1
│ test cl, cl
╰── jne loop
Отличия три:
- порядок;
[rdi]вместо[rdx - 1];- выбор регистров.
▍ Пропуск дополнения
Оба компилятора выдали инструкцию movzx для преобразования входного символа в целое число.
Я не думаю, что эта инструкция необходима в каком-либо из этих компиляторов, поскольку 32-битные операции на x86_64 внутренне выполняют дополнение нулями, и я не вижу ни одного пути кода, где старшие биты были бы установлены.
Тем не менее некоторое чутьё подсказывает мне, что можно избавиться от этих инструкций на стороне Си, заменив:
uint8_t c = *input++;На
uint64_t c = *input++;Таким образом мы удаляем всю идентификацию этого значения как 8-битного, требующего дополнения нулями.
loop: /-> add rdx, 1
| add ecx, dword ptr [rsi+rax*4]
| movzx eax, byte ptr [rdx-1]
| test rax, rax
-- jne loop
loop: /-> movzx ecx,cl
| add eax,dword ptr [rdx+rcx*4]
| movzx ecx,byte ptr [rdi]
| add rdi,0x1
| test cl,cl
-- jne <run_switches+0x20>
Что ж, для gcc сработало.
На одну инструкцию меньше без разбирания кода до уровня ассемблера. Весьма неплохо.
- Время выполнения gcc 0.47 s
- Скорость gcc: 1.98 GiB/s
Но…никакого эффекта.
▍ Переписывание asm
Давайте перепишем этот код в ассемблере – это позволит понять, что именно происходит.
Нет, нельзя надёжно пересобрать дизассемблированный код… Потребуется по меньшей мере скорректировать вывод. В данном случае я написал массив, из которого выполняется считывание посредством директив ассемблера gcc, и добавил метки перехода, чтобы сделать его читаемым.
.text
run_switches:
xor eax, eax # res = 0
loop: # while (true) {
/----> movsx rcx, byte ptr [rdi] # char c = *input
| test rcx, rcx # if (c == '')
| /-- je ret # return
| | add eax, dword ptr [arr+rcx*4] # res += arr[c]
| | inc rdi # input++
--|-- jmp loop # }
ret: -> ret
.data
arr:
.fill 'p', 4, 0
.long -1, 0, 0, 1
.fill (256 - 's'), 4, 0Это моё первое выполнение, и тут мы видим буквальный перевод версии Си. Здесь у нас на критическом пути даже два перехода (один дополнительный безусловный) в сравнении с выводом gcc и clang. Как же это скажется на скорости?
- Время выполнения: 0.24 s
- Скорость: 3.88 GiB/s
Что ж, этот вариант с первой попытки превзошёл gcc и clang. Я ожидал, что будет труднее написать более быстрый код, чем создают современные компиляторы со множеством оптимизаций…
▍ Разбираем кодирование
Вывод gcc загружает адрес массива в регистр и использует его для обращения к этому массиву на критическом пути:
lea rsi, [add_arr]
...
add ecx, dword ptr [rsi+rax*4]
Это кажется излишним, так что мы наверняка можем избавиться от лишней инструкции lea, используя адрес массива напрямую.
add ecx, dword ptr [arr+rax*4]
Мы удалили одну инструкцию (lea) из не критического пути, так? Да, но если сопоставить кодировки инструкций, то мы увидим, что увеличили количество байтов, требуемых для кодирования add, а add является инструкцией на критическом пути.
48 8d 34 25 00 00 00 lea rsi,ds:0x0
...
03 0c 86 add ecx,DWORD PTR [rsi+rax*4]
...
03 0c 85 00 00 00 00 add ecx,DWORD PTR [rax*4+0]
Думаю, что загрузка адреса первого элемента массива в rsi является хорошей оптимизацией, если у вас есть свободные регистры. Пока проигнорируем этот момент.
▍ Исправление кода gcc
В действительности мы хотим знать, почему внутренний цикл gcc почти вдвое медленнее clang несмотря на то, что они так похожи. Чтобы это выяснить, я скопировал код gcc в программу ассемблера здесь и внёс изменения, необходимые для того, чтобы он заработал.
Если мы выполним бенчмарк для дизассемблированной версии, то он должен занять столько же времени, что и версия gcc, то есть 0,47 секунды.
Ноооо, он занял 0,26 с, оказавшись почти вдвое быстрее. Думаю, я допустил ошибку? Давайте поищем отличия в выводе.
9: 48 8d 35 00 00 00 00 lea rsi,[rip+0]
10: 48 85 c0 test rax,rax
13: 74 13 je 28 ret
9: 48 8d 34 25 00 00 00 lea rsi,ds:0
10: 00
11: 48 85 c0 test rax,rax
14: 74 13 je 29 ret
Ага! Здесь у нас несколько иная кодировка lea.
Я не совсем уверен, что послужило причиной, так как в обеих версиях массив, похоже, сохраняется в разделе .rodata бинарника. Если кто-то понимает разницу между этими двумя кодировками, отпишите в комментариях или мне на почту.
Итак, поскольку единственное ощутимое отличие находится перед критическим путём, я предполагаю, что на производительность влияет разница в выравнивании.
Безусловно, если добавить перед нашим сжатым циклом пять невинных no-op, то мы вернёмся к быстродействию gcc.
Но мы сделаем лучше и построим график, который отразит связь добавления заполняющих no-op и времени выполнения.
Итак, начиная с пяти no-op (по одному байту каждая), мы получаем 2-кратное замедление, которое сохраняется вплоть до 20 no-op, после чего происходит ускорение. Это повторяющийся паттерн?
Да, он определённо повторяется. С какой периодичностью? Надеюсь, что это удобная степень двойки…
… Это 64 – очень хорошо.
В течение 15 байт заполнения выполнение происходит медленно, после чего в течение 49 оно происходит быстро.
Мой внутренний цикл измеряет ровно 16 байт. Значит, этот повторяющийся паттерн из 15 медленных версий должен быть связан с моментом, когда внутренний цикл gcc распределяется вдоль границы двух кэш-линий. А каков размер кэш-линии на моем процессоре? 64 байта.
Хорошие новости! Мы выяснили причину отличия в скорости.
Итак, как нам убедить gcc выровнять цикл более удачно?
Я попробовал CFLAGS=-falign-jumps= <n> make bench-c-4-gcc при различных значениях n, но ничего не произошло.
Причина, похоже, в том, что верхний сегмент нашего цикла, являясь целью ветвления, также выступает местом, куда происходит переход из кода выше.
Фрагмент из документации gcc:
Цели ветвления, которые могут быть достигнуты только путём перехода, следует выравнивать по величине, равной степени двойки.
К счастью, CFLAGS=-falign-loops=16 работает!
В документации сказано, что -falign-loops активна по умолчанию с оптимизациями, установленными на >= -O2. Но в ней также говорится: «Если n не указано или равно нулю, используйте значение по умолчанию, определяемое машиной». Думаю, что на моей машине это значение меньше 16 :/
Также кажется излишним применять эту опцию для всей компилируемой единицы. В идеале это выравнивание желательно устанавливать вручную только для внутреннего цикла. Gcc предоставляет атрибуты выравнивания, например, __attribute__((aligned(16))), но они не применимы к меткам/инструкциям – только к функциям.
Вся наша функция фактически вписывается в одну кэш-линию и, действительно, установка __attribute__((aligned(64))) для run_switches работает. Думаю, что это самый тонкий контроль, который вы можете получить, не разбирая код до уровня ассемблера. Хотя, возможно, кто-то знает способ получше?
Заключение
- Пожалуй, нет смысла оптимизировать не критические пути.
- Сжатые, выровненные циклы, вписывающиеся в кэш-линию, выполняются молниеносно.
- Сжатые циклы, распределённые по двум кэш-линиям, могут выполняться в 2 раза медленнее своих выровненных альтернатив.
- Похоже, gcc по умолчанию выравнивает код не слишком строго.
- При написании кода GNU Assembler вашим другом окажется
.align <bytes>.
Выиграй телескоп и другие призы в космическом квизе от RUVDS. Поехали? 🚀
Автор: Дмитрий Брайт
