В процессе разработки компилятора 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-канале ↩
? Читайте также:
ссылка на оригинал статьи https://habr.com/ru/articles/850066/
Добавить комментарий