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

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

Дата-ориентированное проектирование часто используется при программировании игр, где именно от скорости среды выполнения зависит, что вы сможете и чего не сможете сделать. В последнее время эта парадигма стала активнее применяться и в других предметных областях, например, в разработке компиляторов для Zig и Rust, а также в других проектах, где акцент делается на ускорении среды выполнения, например, в  Mold и Bun.

Эндрю Келли, создатель Zig, выступил с отличной лекцией Practical Data-oriented design, которая служит введением в основные идеи, лежащие в основе DoD. В этой статье я покажу, как мы изменили компилятор roc, переработав его с учётом некоторых из этих идей.

❯ Коллекция – это абстракция

Цель DoD – ускорить работу программ, но также эта парадигма позволяет в интересном ракурсе рассмотреть проектирование программ как таковое.

Наиболее распространённый пример DoD – это массив структур в сравнении со структурой массивов. В большинстве подходов к программированию распространена ситуация, когда у вас накапливается множество значений определённой формы, то есть, структур. Если структур много, то их объединяют в массив. В данном случае структура – это минимальная сущность, которой приходится оперировать; именно в ней определяются методы.

struct Point2d { 
    x: f32, 
    y: f32,
}

type Polygon = Vec<Point2d>;

Это логично, но в DoD практикуется совершенно другой подход. Минимальная сущность, которой предлагается оперировать – это коллекция:

struct Polygon { 
    xs: Vec<f32>,
    ys: Vec<f32>,
}

На этом примере понятна суть произошедшего преобразования, но он не показывает, а каковы преимущества DoD. Давайте воспользуемся DoD и попытаемся применить её при решении реальных задач.

❯ DoD и компиляторы

Принято считать, что работа компилятора напрямую зависит от ЦП. Компилятор преобразует ввод (исходный код) в вывод (исполняемые файлы). Скорость работы компилятора зависит от того, как быстро конкретная машина способна обрабатывать данные.

Но на практике у этой проблемы гораздо больше нюансов. Многие современные приложения зависят не столько от скорости ЦП – сколько времени уходит на выполнение одной команды – сколько от того, как быстро удастся доставить команды и данные в ЦП. Соответственно, скорость компиляторов во многом зависит от работы с памятью.

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

❯ Задача для примера

Парсер roc просматривает файл с исходным кодом roc и выдаёт список определений верхнего уровня, содержащихся в этом файле. Они хранятся как список из Def с указанием той позиции, с которой они начинаются в файле:

// участок файла, полученного на ввод
#[derive(Clone, Eq, Copy, PartialEq, PartialOrd, Ord, Hash)]
pub struct Region {
    start_position: u32,
    end_position: u32,
}

#[derive(Clone, Eq, Copy, PartialEq, PartialOrd, Ord, Hash)]
pub struct Loc<T> {
    pub region: Region,
    pub value: T,
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Def<'a> {
    Type(TypeDef<'a>),
    Value(ValueDef<'a>),

    // Пустое пространство (напр., комментарии, пробелы, переходы на новую строку) до или после def.
    // Эту информацию откладываем до этапа форматирования; при канонизации она игнорируется.
    SpaceBefore(&'a Def<'a>, &'a [CommentOrNewline<'a>]),
    SpaceAfter(&'a Def<'a>, &'a [CommentOrNewline<'a>]), 
}

type Defs<'a> = Vec<Loc<Def<'a>>>

Такое представление после синтаксического разбора используется как для генерации исполняемого кода (программы, которая может работать), так и для форматирования кода roc. С точки зрения инструмента форматирования порядок следования определений важен, а также должны быть сохранены комментарии. Мы не хотим, чтобы при форматировании определения верхнего уровня оказались переупорядочены, а все комментарии – выброшены!

На первый взгляд тип Def кажется красивым представлением. Здесь мы пользуемся перечислениями, поэтому позже можем найти соответствия для всех случаев. Примерно так же эта идея могла быть выражена в haskell или elm.

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

SpaceAfter(SpaceAfter(..., &[ ... ]), &[ ... ])

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

Как в таком случае может помочь дата-ориентированное проектирование?

❯ Подача данных в ЦП

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

В университетских курсах о производительности часто рассказывают в курсе изучения big-O classes. Но мало хорошо спроектировать алгоритм, чтобы программа быстро работала в реальной ситуации. Также нужно уметь воспользоваться сильными сторонами аппаратной части.

В нашем компиляторе, как и в большинстве программ, интенсивно обрабатывающих данные, ограничивающим фактором обычно является не сам ЦП, а то, сколько данных в него можно подать. Большую часть времени ЦП дожидается, пока в него на обработку поступят новые данные. Но мы сразу можем спроектировать нашу программу так, чтобы ЦП использовался более эффективно.

❯ Загрузка данных

Чтобы выполнить команду, нужно предварительно сделать две вещи. Сначала необходимо загрузить команду и её аргументы, а потом ЦП должен фактически обработать эту команду.

На современном железе большая часть задержек приходится именно на загрузку команды и её аргументов, чем на выполнение команды. Как ни парадоксально, это означает, что иногда получается быстрее многократно выполнить одно и то же вычисление, чем кэшировать эту операцию. Иными словами, ЦП – совсем не самое узкое место. Так было не всегда, но за прошедшие десятилетия скорость работы процессоров улучшилась гораздо сильнее, чем скорость памяти.

Чтобы справиться с (относительно) медленным извлечением данных из памяти, ЦП обычно кэшируют те данные, которые недавно использовались. Высока вероятность, что эти данные снова потребуются. В ЦП предусмотрено несколько уровней кэша:

> lscpu  | grep "cache:"
Кэш L1d:                       256 KiB
Кэш L1i:                       512 KiB
Кэш L2:                        4 MiB
Кэш L3:                        16 MiB

Кэш уровня 1 (L1) существует в двух разновидностях. В одном кэшируются команды из вашей программы, а в другом – те данные, которыми оперирует программа. Уровни кэша 2 и 3 в таком отношении не отличаются. В этих кэшах приходится выигрывать скорость за счёт размера: кэш L1 крошечный, но хранящиеся там данные очень быстрые. Кэш L3 значительно больше, но работает медленнее (впрочем, работать с ним всё равно несколько быстрее, чем с основной памятью).

Память в кэшах содержит не просто коллекцию байт: они разделены по кэш-линиям. В современных процессорах такие линии обычно имеют 64 байта в ширину. Когда значение загружается из памяти, на самом деле загружается объемлющая его кэш-линия. Например,  my_vector[0] загрузит из основной памяти не только этот элемент, но и всю кэш-линию. Если затем мы воспользуемся my_vector[1], то это значение, вероятно, окажется в той же кэш-линии, которая уже загружена и сохранена в кэше процессора. Следовательно, вторая операция поиска пройдёт очень, очень быстро.

Но размер кэша ограничен, поэтому, если вы записываете в него какую-то новую информацию, что-то старое из него нужно выбросить. Соответственно, существующую кэш-линию нужно вытеснить.

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

❯ Структура массивов

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

Обычно при переборе коллекции мы используем всего по паре полей из элементов. Но при этом загружается весь элемент целиком – следовательно, в кэш-линии оказывается не так много полезной информации.

Вернемся к нашему примеру:

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Def<'a> {
    Type(TypeDef<'a>),
    Value(ValueDef<'a>),

    // Пустое пространство (напр., комментарии, пробелы, переходы на новую строку) до или после def.
    // Эту информацию откладываем до этапа форматирования; при канонизации она игнорируется.

    SpaceBefore(&'a Def<'a>, &'a [CommentOrNewline<'a>]),
    SpaceAfter(&'a Def<'a>, &'a [CommentOrNewline<'a>]),
}

type Defs<'a> = Vec<Loc<Def<'a>>>
The idea is to represent the Defs as several arrays.
struct Defs<'a> { 
    defs: Vec<Def<'a>>,
    regions: Vec<Region>,
}

Теперь определения (Def) и регионы хранятся по отдельности, в параллельных массивах. Например, регион с индексом 12 соответствует определению с индексом 12. Теперь нам придётся ссылаться на определения по их индексу. Ссылка Rust работать больше не будет, поскольку по ссылке на Def больше не содержится Region.

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

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

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Def<'a> {
    Type(TypeDef<'a>),
    Value(ValueDef<'a>),
}

struct Defs<'a> { 
    defs: Vec<Def<'a>>,
    regions: Vec<Region>,

    space_before: Vec<&'a [CommentOrNewline<'a>]>,
    space_after: Vec<&'a [CommentOrNewline<'a>]>,
}

При проверке типов пробелы значения не имеют, поэтому мы просто не рассматриваем массивы space_*, и нам вообще не приходится беспокоиться, есть ли в коде пробелы. При форматировании мы легко можем посмотреть их, имея индекс того Def, которое мы сейчас обрабатываем.

Такое преобразование мы выполнили из соображений производительности, но на самом деле при этом также удаётся устранить ещё одну ошибку: двойные пробелы SpaceAfter. Наш код стал только лучше!

❯ Ещё один шаг

Давайте внесём ещё одно изменение в структуру данных. На этапе форматирования важен лишь порядок определений. Но в большинстве других мест требуется обрабатывать определения типов и определения значений по отдельности.

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum DefTag<'a> {
    Type { type_defs_index : u32 },
    Value { value_defs_index: u32 },
}

struct Defs<'a> { 
    tags: Vec<DefTag<'a>>,
    regions: Vec<Region>,

    space_before: Vec<&'a [CommentOrNewline<'a>]>,
    space_after: Vec<&'a [CommentOrNewline<'a>]>,

    value_defs: Vec<ValueDef<'a>>
    type_defs: Vec<TypeDef<'a>>
}

Можно и на этом не останавливаться, а сохранить метку как i32, а далее при помощи знака указывать, с чем мы имеем дело: с типом или значением. Может быть, получилось бы скомбинировать векторы space_before и space_after. Дата-ориентированное проектирование может подбрасывать очень интересные головоломки.

❯ Результаты

Мы серьёзно перекомпоновали код, но удалось ли сделать его лучше? Измерять производительность всегда непросто, но я проверил несколько бенчмарков. Код для них находится здесь.

Этот бенчмарк разбирает очень простую последовательность токенов в две наши структуры данных. Первым делом я попытался провести тест cargo bench с критерием. Не сработало, поскольку standard::parser расходует всю свою память. В свою очередь, dod::parser работает нормально. Это, как минимум, показывает, что при подходе DoD экономнее используется память.

Расход памяти удобнее всего отобразить при помощи valgrind:

> valgrind ./target/release/standard
...
==197038==   total heap usage: 46 allocs, 46 frees, 75,499,477 bytes allocated
...
> valgrind ./target/release/dod
...
==197006==   total heap usage: 99 allocs, 99 frees, 67,110,853 bytes allocated
...

В данном примере мы использовали примерно 8 Мб, то есть, на 12% меньше памяти. Приятно!

Что касается среды выполнения, можно откатиться обратно к hyperfine:

> hyperfine target/release/standard target/release/dod
Benchmark #1: target/release/standard
  Time (mean ± σ):      26.6 ms ±   1.6 ms    [User: 14.9 ms, System: 11.8 ms]
  Range (min … max):    24.1 ms …  33.8 ms    91 runs
 
Benchmark #2: target/release/dod
  Time (mean ± σ):      23.6 ms ±   1.1 ms    [User: 14.3 ms, System: 9.5 ms]
  Range (min … max):    21.3 ms …  27.8 ms    108 runs
 
Summary
  'target/release/dod' ran
    1.12 ± 0.09 times faster than 'target/release/standard'

Здесь разница не так велика.

❯ В сравнении с упакованным вариантом

Мы немного улучшили показатели предыдущего бенчмарка, так как уже в начальном варианте кода использовали выделение арен. Что было бы, если воспользоваться более стандартным Box<Def>, а не &'a Def, вот так?

#[derive(Debug, Clone)]
pub enum Def<'a> {
    Type(TypeDef<'a>),
    Value(ValueDef<'a>),

    // Было 
    // SpaceBefore(&'a Def<'a>, &'a [CommentOrNewline<'a>]),
    // SpaceAfter(&'a Def<'a>, &'a [CommentOrNewline<'a>]),
    SpaceBefore(Box<Def<'a>>, &'a [CommentOrNewline<'a>]),
    SpaceAfter(Box<Def<'a>>, &'a [CommentOrNewline<'a>]),
}

С Box получается гораздо хуже, поскольку на каждый тип, значение или обёртку пробела требуется своя маленькая операция выделения памяти:

==196475==   total heap usage: 399,862 allocs, 399,862 frees, 71,516,421 bytes allocated

В итоге получается примерно на 70% медленнее:

> hyperfine target/release/standard target/release/boxed
Benchmark #1: target/release/standard
  Time (mean ± σ):      25.1 ms ±   1.8 ms    [User: 14.3 ms, System: 10.8 ms]
  Range (min … max):    23.0 ms …  35.4 ms    82 runs
 
Benchmark #2: target/release/boxed
  Time (mean ± σ):      42.5 ms ±   2.3 ms    [User: 28.3 ms, System: 14.2 ms]
  Range (min … max):    38.9 ms …  49.9 ms    70 runs
 
Summary
  'target/release/standard' ran
    1.69 ± 0.15 times faster than 'target/release/boxed'

❯ Заключение

Как видите, идеи, взятые из дата-ориентированного подхода к проектированию, помогают и ускорить, и улучшить код. Как упоминает в своей лекции Эндрю Келли, экспериментируя с этими идеями сам ощущаешь, как (снова) улучшаются твои навыки программирования. Не всегда стоит прибегать к DoD, поскольку она может вносить путаницу в массивы и индексы, а операции с временами жизни и изменяемостью становятся опасными. Но такой инструмент просто очень интересно иметь в арсенале.

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩

? Читайте также:

• ➤ Компиляторные оптимизации сложны, так как компиляторы забывчивы;

• ➤ Откройте для себя весь потенциал AbortController;

• ➤ STM32. Процесс компиляции и сборки прошивки;

• ➤ Можно ли доверить компилятору оптимизацию вашего кода?;

• ➤ TypeScript: разрабатываем WebAssembly-компилятор.