Как замедлить программу и почему это может быть полезно

Большинство исследований производительности языков программирования задают вариации одного и того же вопроса: как ускорить конкретную программу? Иногда мы ищем способы использовать меньше памяти. Это означает, что многие исследования сосредоточены исключительно на уменьшении объёма ресурсов, необходимых для достижения какой-либо вычислительной цели.

Так зачем же нам тогда замедлять программы?

Замедление программ на удивление полезно

Замедление программ может быть полезно для выявления условий гонки, моделирования ускорения и оценки точности профилировщиков.

Для обнаружения условий гонки можно использовать подход, аналогичный фаззингу. Вместо того, чтобы исследовать реализацию программы, изменяя её входные данные, мы можем исследовать различные чередования инструкций, расписания потоков или событий, замедляя части программы для изменения таймингов. Этот подход позволяет выявлять ошибки параллелизма и используется в CHESS, WAFFLE и NACD.

Профилировщик Coz — пример того, как замедление программ может использоваться для моделирования ускорения. С помощью Coz мы можем оценить, принесёт ли оптимизация пользу, ещё до её реализации. Coz имитирует это, замедляя все остальные части программы. Та часть, которую мы считаем поддающейся оптимизации, остаётся на прежней скорости, но теперь становится (виртуально) быстрее, что позволяет нам понять, даёт ли оптимизация достаточно преимуществ, чтобы оправдать, возможно, длительный проект улучшения.

И, как уже упоминалось, мы также можем использовать Coz для оценки точности профилировщиков. Впрочем, я оставлю это для следующих публикаций в блоге. :)

Текущие подходы к замедлению работы программ для таких сценариев являются довольно грубыми. Для обнаружения гонок часто модифицируют планировщик или используют, например, такие API, как Thread.sleep(). Аналогично, инструмент Coz приостанавливает выполнение остальных потоков. В исследовании, посвящённом анализу эффективности профилировщиков, в Java-программы вставляются байткоды для вычисления чисел Фибоначчи.

Используя более детальное замедление, мы полагаем, что сможем повысить точность обнаружения гонки, оценки ускорения и оценки точности профилировщиков. Таким образом, мы рассмотрели возможность вставки инструкций замедления в базовые блоки.

Какие инструкции x86 позволяют нам последовательно замедлять базовые блоки?

Предположим, что мы работаем на процессоре x86 и рассматриваем программы с точки зрения процессоров.

При запуске бенчмарка, например Towers, виртуальная машина OpenJDK HotSpot JVM может скомпилировать его в инструкции x86 следующим образом:

mov dword ptr [rsp+0x18], r8d
mov dword ptr [rsp], ecx
mov qword ptr [rsp+0x20], rsi
mov ebx, dword ptr [rsi+0x10]
mov r9d, edx
cmp edx, 0x1
jnz 0x... <Block 55>

Это один из базовых блоков, создаваемых компилятором HotSpot C2. Для наших целей достаточно увидеть, что инструкции mov обращаются к памяти, и мы проверяем, содержит ли регистр edx значение 1. Если это не так, мы переходим к Block 55. В противном случае выполнение продолжается в следующем базовом блоке. Ключевым свойством базового блока является отсутствие внутри него потока управления, что означает, что как только он начнет выполняться, все его инструкции будут выполнены.

Но как можно замедлить его?

В x86 есть много различных инструкций, которые можно попытаться вставить в блок, и каждая из них, вероятно, будет потреблять циклы процессора. Однако современные процессоры стараются выполнять как можно больше инструкций одновременно, используя out-of-order выполнение. Это означает, что инструкции в нашем базовом блоке, не зависящие напрямую друг от друга, могут выполняться одновременно. Например, первые три инструкции mov не обращаются к одному и тому же регистру или ячейке памяти. Это означает, что порядок их выполнения здесь не имеет значения. Однако то, какие оптимизации применяет процессор, зависит от программы и конкретного поколения процессора, или, скорее, микроархитектуры.

Чтобы найти подходящие инструкции для замедления базовых блоков, мы экспериментировали только с процессором Intel Core i5-10600 с микроархитектурой Comet Lake-S. На других микроархитектурах ситуация может существенно отличаться.

Для желаемого замедления мы можем использовать инструкции nop или mov regX, regX на Comet Lake-S. В этом случае mov переместит значение из регистра X в себя, то есть, по сути, ничего не сделает. Эти две инструкции дают нам замедление, достаточно небольшое для точного замедления большинства блоков до желаемой скорости, и замедление, по-видимому, влияет только на тот блок, для которого оно предназначено.

В таком случае наш базовый блок, рассмотренный ранее, возможно, будет содержать инструкции nop, перемежающиеся после каждой инструкции. На практике количество инструкций, которые нам нужно вставить, зависит от того, сколько времени занимает базовый блок в программе. Хотя, для наглядности, это может выглядеть так:

mov dword ptr [rsp+0x18], r8d
nop
mov dword ptr [rsp], ecx
nop
mov qword ptr [rsp+0x20], rsi
nop
mov ebx, dword ptr [rsi+0x10]
nop
mov r9d, edx
nop
cmp edx, 0x1
nop
jnz 0x... <Block 55>

Мы попробовали шесть различных вариантов, включая последовательность push-pop, чтобы лучше понять, как Comet Lake-S справляется с ними. Подробнее о том, как и что мы пробовали, можно узнать из нашей короткой статьи, которую мы представим на воркшопе VMIL.

При вставке этих инструкций в базовые блоки, так что каждый отдельный базовый блок занимает примерно вдвое больше времени, чем раньше, мы получаем программу, которая в целом действительно вдвое медленнее, чем можно было бы ожидать. Более того, если посмотреть на бенчмарк Towers с async-profiler для HotSpot и сравнить доли времени выполнения, приходящиеся на каждый метод, то замедленная и обычная версии практически идеально совпадают, как показано ниже. С другими рассмотренными нами вариантами дела обстоят иначе.

Диаграмма рассеяния для каждой инструкции замедления со средним процентом времени выполнения для шести лучших методов Java в Towers. Диагональ X=Y показывает, когда процент времени выполнения метода остаётся неизменным как с замедлением, так и без него.

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

Конечно, эта работа — лишь ступенька к более интересным вещам, которые я рассмотрю более подробно в следующей публикации.

Источник