Раз в несколько лет я устраиваю в нашей исследовательской группе челлендж «Напиши медленный код». Цель – написать код с минимально работоспособным количеством инструкций на цикл (IPC) с условием, чтобы этот код выполнялся на заранее подобранном сервере с архитектурой x86.
На первый взгляд, это абсурд! В сущности, так и есть. Однако, есть в этой безумной задаче и некоторая методическая ценность. Инженеры, проектирующие процессоры, прилагают все усилия ради достижения наивысшего возможного IPC… даже для очень неэффективного кода. Так и задумано, что писать код с очень высоким показателем IPC непросто. Следовательно, челлендж “Напиши медленный код” оказывается заковыристым упражнением, вынуждающим задумываться, как именно работает процессор, и как применить себе на пользу его острые углы.
Правила нашего конкурса довольно зыбкие (он в большей степени вертится вокруг презентации решений, чем касается «спортивного духа»), но я постараюсь их сформулировать. В списке правил точно должны быть следующие пункты:
Однопоточный код
Активно выполняемый код (а не такой, который будет «освобожден от задач» планировщиком ОС или т.д.)
Выполняемый исключительно «на устройстве». То есть, код не должен зависеть от внешних устройств (напр., дожидаться ввода/вывода)
В этой статье обсудим пару различных подходов к преодолению этого челленджа.
Ещё одно замечание: все данные по производительности измерены на 64-ядерном процессоре AMD EPYC 7763 (Zen3).
Python медленный - давайте сразу писать на Python?
Резонный вопрос! Но здесь нужно различать код, медленно достигающий поставленного результата и код, медленно выполняемый на ЦП. Если я напишу на Python решето Эратосфена, то оно будет очень медленно просеивать числа. Но при этом код (речь в основном о коде интерпретатора Python) при исполнении будет щедро расходовать IPC. Я проверил этот процесс, расставив бенчмарки — и на моей машине стабильно выходило почти 5 IPC. При этом важно, что Python такой медленный не из-за низкого показателя IPC, а потому, что на выполнение каждой строки кода ему требуется огромное количество инструкций.
Подход 1: гонка указателей
Есть расхожая мудрость — «Связные списки такие медленные, так как в них возникает гонка указателей». Но что бы это значило?
Рассмотрим следующий код:
Node* root = make_circular_linked_list(...);
Node* cur = root;
while (true) {
cur = cur->next;
}Также представленный на следующей схеме:
Этот код получается таким медленным, поскольку он устроен последовательно и никак иначе. Если в данный момент мы работаем над node0, то не узнаем, какой адрес загрузить дальше, пока не справимся с загрузкой node0. Если на загрузку node0 уходит много времени из-за кэш-промаха, то остаётся только сидеть и ждать. Современные ЦП хорошо оснащены для того, чтобы целенаправленно пользоваться параллелизмом на уровне инструкций (ILP)… но сложно воспользоваться ILP, если он отсутствует в принципе!
Итак, первая идея по замедлению кода — тщательно написать закольцованный связный список, обладающий следующими двумя свойствами:
Он должен быть огромным, таким, чтобы он не умещался в кэш
Те узлы, которые расположены рядом друг с другом в списке, должны быть сильно разнесены в памяти. Таким образом сложатся такие паттерны доступа, при которых локальность кода организована плохо, и при обращении к нему то и дело будут возникать кэш-промахи. Затем можете обходить его вечно, и показатели IPC пробьют дно.
Я написал код для такого связного списка и при помощи вышеприведённого кода организовал такой вечный обход. Затем скомпилировал программу с опцией -O0 (чтобы она получилась исключительно медленной). Вот какие результаты я получил от perf stat:
18.022591244 3,523,728,182 cycles:u
18.022591244 52,440,970 instructions:u # 0.01 инструкций на циклНеплохо. 1/67 IPC — это очень медленно. Но, думаю, это не предел. В частности, можно продвинуться ещё на шаг, скомпилировав код с -O3! Вот как выглядит выполнение того же бесконечного обхода связного списка, но теперь при компиляции с -O3:
16.018577682 3,520,128,798 cycles:u
16.018577682 20,716,958 instructions:u # 0.01 инструкций на цикл1/170 IPC — гораздо медленнее! Здесь можно запутаться, так как кажется, что -O3 — это быстрее, чем O0.
В обоих случаях изучив ассемблер, сгенерированный циклом в результате обхода, видим, что здесь происходит. При -O0 имеем следующий ассемблер:
1528: 48 8b 45 f0 mov -0x10(%rbp),%rax
152c: 48 8b 45 f0 mov -0x10(%rbp),%rax
1530: 48 8b 00 mov (%rax),%rax
1533: 48 89 45 f0 mov %rax,-0x10(%rbp)
1537: eb ef jmp 1528 <main+0x2c>А при -O3:
13e0: 48 8b 1b mov (%rbx),%rbx
13e3: eb fb jmp 13e0 <main+0x20>В обоих случаях в теле цикла наблюдается одиночный неудобный последовательный механизм доступа к памяти, при котором возникают кэш-промахи. Но в случае с -O0 имеем 5 инструкций на цикл, а в случае с -O3 всего 2. Напомню, что в числителе у показателя IPC — его инструкции. Если в нашем цикле 4 быстрые инструкции и 1 медленная (загрузка в ->next), то IPC будет гораздо выше, чем в более оптимизированной версии того же цикла, в которой всего две инструкции.
Вот какой урок можно из этого извлечь: чтобы снизить количество IPC, код должен быть хорошо оптимизирован :)
Подход 2: связный список переходов
Предыдущий подход был направлен в основном на провоцирование промахов в кэше данных. Наш код обходил обширный связный список, но сам этот код представлял собой крошечный цикл из 2 инструкций, который легко помещается в кэше инструкций (iCache). Можно добиться низкого IPC и другим способом: обеспечить частые промахи в iCache. С такой целью можно создать огромный связный список переходов, которые при этом неудачно расположены.
Прямо на ассемблере x86 можно написать примерно такую (демонстрационную) программу:
.global main
main:
jmp l0
l0:
jmp l2
l1:
jmp l3
l2:
jmp l4
l3:
jmp l0
l4:
jmp l1При выполнении этой программы переходы пойдут примерно в таком порядке: main -> l0 -> l2 -> l4 -> l1 -> l3 -> l0 -> ... и так до бесконечности. Чтобы написать такой ассемблер, даю на вход простому скрипту Python два значения: простое число P и меньшее число shift :
with open(f"jmps_{P}_{shift}.s", "w") as f:
f.write(".global main\n")
f.write("main:\n")
f.write("\tjmp l0\n")
for i in tqdm(range(P)):
f.write(f"l{i}:\n")
next_lbl = (i + shift) % P
f.write(f"\tjmp l{next_lbl}\n")Учитывая, что число P простое, я могу выбрать какое угодно значение shift, и тогда цикл обойдёт все метки, прежде, чем вернуться к l0. Это очень важно — так мы максимально увеличиваем место, занимаемое iCache в памяти. Также хочется выбрать достаточно большое значение shift, чтобы последующие метки оказались не только в разных кэш-линиях, но и на разных страницах виртуальной памяти.
Я решил поэкспериментировать со значениями P = 67108859 и shift = 2346, хотя, для наших опытов подошли бы и любые другие подобные числа. Выполнив этот код, получаю следующие результаты:
3.003449075 3,488,476,061 cycles:u
3.003449075 8,124,252 instructions:u # 0.00 инструкций на циклНеплохо! Получается 1/429 IPC– существенно медленнее, чем при предыдущем подходе.
Дело в том, что этот код обладает некоторыми «желательными» (подчеркну, только в рамках этой задачи) качествами вдобавок к тому, что допускает промахи в iCache. Современные процессоры серьёзно оснащаются для того, чтобы программе было проще спрогнозировать, какая инструкция поступит следующей. Эти механизмы позволяют спекулятивно выбирать, декодировать и назначать инструкции задолго до того, как придёт их очередь выполняться, и эти глубокие конвейеры абсолютно необходимо держать заполненными. При таком цикле на 67108859 инструкций перехода мы просто парализуем все эти предикторы.
Например, в процессоре Zen3, с которым я работаю, предусмотрен буфер прогнозирования ветвлений (BTB) на 1024 записи. При помощи этой структуры процессор кэширует «цель» каждой инструкции. Буфер на 1024 записи просто огромен! Но он примерно в 65 000 раз меньше, чем был бы нужен нам для реальной помощи в данной конкретной программе. Постоянные промахи в BTB изрядно способствуют такому низкому IPC, к которому мы стремимся.
Думаю, подход 2 отлично демонстрирует, сколько проблем может возникнуть из-за плохо подобранной компоновки инструкций.
Подход 3: Учёт тактов
Мне приятно отметить, что подходы 1 и 2 демонстрируют (и эксплуатируют) некоторые вполне базовые аспекты архитектуры компьютера. А подход 3 – это трюк, который пройдёт только на архитектуре x86.
В x86 много инструкций. Некоторые из них могут сопровождаться префиксом rep. rep многократно повторяет инструкцию и на каждой итерации уменьшает значение регистра rcx на единицу (и одновременно увеличивая на единицу как rdi, так и rsi). Он останавливается, только когда rcx достигнет 0.
Фактически, зачастую memcpy реализуется именно с применением rep movsb: повторяющейся инструкции mov. На современных машинах с архитектурой x86 rep movsb (аппаратно) оптимизируется так, чтобы она показывала повышенную эффективность при больших значениях memcpy.
Однако в таком случае также очень удобно взвалить на «единственную инструкцию» очень много работы. В программе, которую мы разбираем, установим rcx в INT_MAX и станем просто снова и снова копировать одни и те же данные:
#define N ((1ul << 31) - 1)
char src[N];
char dst[N];
inline void memcpy_rep(char *dst, char *src, size_t n) {
__asm__ volatile (
"cld\n\t"
"rep movsb\n\t" // <------------ сама инструкция rep movsb
: "+S"(src), "+D"(dst), "+c"(n)
:
: "memory"
);
}
int main() {
while (1) {
memcpy_rep(dst, src, N);
}
}Итак, «ради учёта» эта единственная инструкция выполняет более 2 миллиардов итераций. На практике, конечно же, мы не стремимся к IPC в 1 / 2 миллиарда. На это есть две причины: 1) как упоминалось выше, rep movsb очень эффективна на аппаратном уровне, поэтому она будет копировать данные такими фрагментами, каждый из которых умещается в кэш-линию. Поэтому, фактически, мы получим 2 миллиарда / 64 ~ 33,6 миллиона рабочих циклов. 2) В теле нашего цикла присутствует не только rep movsb, там также нужны ещё некоторые служебные инструкции, которые сбрасывали бы регистры rdi, rsi и rcx в их исходные значения, сбрасывали флаг направления (упоминаю об этой операции, так как без неё не обойтись, и она будет нам стоить 1 инструкцию на каждой итерации цикла), а затем возвращались к началу. Так что, фактически, мы выполняем по 6 инструкций на каждую итерацию цикла и получаем ожидаемые IPC в 33,6 миллионов / 6 = ~ 5,6 миллионов.
Выполняя программу, видим, что она без малого стоит как вкопанная:
25.027657535 3,523,022,380 cycles:u
25.027657535 598 instructions:u # 0.00 инструкций на циклIPC = 1 / 5,9 миллиона!
Я считаю такой подход жульничеством – в конце концов, это просто фокус с учётом инструкций. Если бы счётчики производительности процессора фиксировали каждую итерацию rep movsb как отдельную инструкцию (что, на мой взгляд, было бы естественнее), то этот код достиг бы весьма высокого показателя IPC. Поэтому я считаю, что это решение очень отличается от остальных. Оно забавное, но скорее в жанре “ахаха, x86”, а не в качестве фундаментального свойства архитектуры компьютера как таковой.
Заключение
В этой статье мы рассмотрели 3 разных подхода, позволяющих написать исключительно медленный код. Если у вас были идеи о том, как добиться абсурдно низкого значения IPC (на любой архитектуре!), пожалуйста, поделитесь ими в комментариях :)