Два варианта абстрактного синтаксического дерева (AST) для выражения a * b + c.

Арены, также называемые регионами, повсюду встречаются в современных языках программирования. Есть такая разновидность арен, которая одновременно суперпроста и удивительно эффективна при работе с компиляторами и тому подобными инструментами. Может быть, именно по причине такой простоты эта элементарная техника не попадалась мне во многих курсах по компиляторам — и вообще в теоретическом минимуме по информатике, если уж на то пошло. В этом посте я познакомлю вас с этой идеей, а также с её многочисленными достоинствами.

Многие по-разному понимают, что такое арены или регионы, поэтому здесь я собираюсь называть интересующую меня разновидность этих структур данных «выровненной», а сам процесс — «выравниванием» (flattening). Выровненная арена содержит всего один тип, то есть, в сущности, это обычный массив. В таком массиве можно обойтись индексами, тогда как обычно для работы с массивом требуются указатели. Здесь мы поговорим прежде всего о выравнивании абстрактных синтаксических деревьев (AST), но вообще описанная идея применима с любой структурой данных, отягощённой указателями.

Чтобы изучить выравнивание, мы дважды напишем простейший интерпретатор: сначала как обычно, а затем с применением выравнивания. Логика поста прослеживается по коду из этого репозитория, где можно сравнить две ветки. Здесь важнее всего отметить, что изменения минимальны, но при этом микробенчмарки показывают, что после выравнивания код работает в 2,4 раза быстрее. Благодаря выравниванию не только повышается производительность, но и сам код становится эргономичнее, на чём я также остановлюсь.

Обычное AST

Для начала дадим хрестоматийное определение AST. Перейдём на простейший язык в мире — арифметические выражения. Здесь требуется всего лишь применять четыре базовые арифметические операции к целочисленным литералам. Среди «программ», которые можно написать на этом языке – например, такие:

42, 0 + 14 * 3

и 

(100 - 16) / 2.

Может быть, наиболее понятное описание AST на этом языке выглядело бы как объявление типа на языке разметки:

type binop = Add | Sub | Mul | Div
type expr = Binary of binop * expr * expr
          | Literal of int

Но в этом посте мы будем писать на Rust. Вот эквивалентные типы в Rust:

enum BinOp { Add, Sub, Mul, Div }
enum Expr {
    Binary(BinOp, Box<Expr>, Box<Expr>),
    Literal(i64),
}

Если вы – не завзятый растаман, то Box<Expr> может показаться вам несколько странным. Но на Rust именно так пишется «старый добрый указатель» на Expr. В C мы написали бы Expr*, имея в виду ровно то же самое. В Java, Python или OCaml здесь было бы просто Expr, поскольку по умолчанию всё является ссылкой.

Имея готовое AST, можно написать все те элементы реализации языка, о которых рассказывается в учебниках, в частности, парсер, модуль структурирования печати и интерпретатор. Все они совершенно непримечательны. Весь интерпретатор укладывается всего в один метод в Expr:

fn interp(&self) -> i64 {
    match self {
        Expr::Binary(op, lhs, rhs) => {
            let lhs = lhs.interp();
            let rhs = rhs.interp();
            match op {
                BinOp::Add => lhs.wrapping_add(rhs),
                BinOp::Sub => lhs.wrapping_sub(rhs),
                BinOp::Mul => lhs.wrapping_mul(rhs),
                BinOp::Div => lhs.checked_div(rhs).unwrap_or(0),
            }
        }
        Expr::Literal(num) => *num,
    }
}

В моём языке принята семантика «доведения до конца» (keep-on-truckin’): любое выражение рано или поздно результирует в i64, даже, если вы не такое число хотели.²

Для полноты картины я также написал маленький генератор случайных программ. В нём нет почти ничего интересного. Он просто с рекурсивно возрастающей вероятностью генерирует литерал, после чего, рано или поздно, завершает работу. При работе такой генератор опирается на фиксированные зёрна PRNG, что значительно упрощает микробенчмаркинг. Когда выражение генерируется, а затем сразу же вычисляется, можно измерить производительность операций с AST без затрат на ввод/вывод, возникающих при разборе и структурировании печати.

Можете посмотреть соответствующий репозиторий и попробовать сами:

$ echo '(29 * 3) - 9 * 5' | cargo run
$ cargo run gen_interp  # Сгенерировать и сразу же выполнить случайную программу.

Выравнивание AST

Идея выравнивания является двухчастной:

• Не будем принудительно выделять в куче объекты Expr, а упакуем их в единый непрерывный массив.

• Не будем ссылаться на дочерние объекты через указатели. Вместо этого Exprs будут сами ссылаться на своих потомков через их индексы в том же массиве.

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

Если вам кажется, что этот план прост — пожалуй, он даже проще, чем вы думаете. Ключевой момент здесь в том, что нам требуется массив Exprs. Воспользуемся принятой в Rust идиомой newtype, при помощи которой объявим тип нашей арены — ExprPool. Это будет сокращённая запись вектора Expr:

struct ExprPool(Vec<Expr>);

Чтобы было красиво, также придумаем имя для обычных целых чисел, из которых мы будем собирать индекс для поиска по ExprPool:

struct ExprRef(u32);

Идея такова: везде, где мы ранее использовали указатель на Expr (т.e., Box<Expr> или иногда &Expr), будем ставить ExprRef. ExprRef — это просто 32-разрядные беззнаковые целые, но, придумав для них отдельное имя, мы сможем не путать их с другими u32. Здесь важнее, что нам потребуется изменить определение самого Expr:

 enum Expr {
-    Binary(BinOp, Box<Expr>, Box<Expr>),
+    Binary(BinOp, ExprRef, ExprRef),
     Literal(i64),
 }

Далее потребуется добавить вспомогательные процедуры к ExprPool, чтобы создавать Expr (выделение) и искать их (разыменование). В моей реализации эти маленькие функции называются add и get, и их реализации крайне скучны. Чтобы ими воспользоваться, нужно как следует просмотреть наш код и найти все те места, где мы либо создаём новые Expr, либо проходим к Expr по указателю. Например, наша функция parse раньше была методом в Expr, но мы вместо этого сделаем её методом в ExprPool:

-fn parse(tree: Pair<Rule>) -> Self {
+fn parse(&mut self, tree: Pair<Rule>) -> ExprRef {

А там, где мы ранее напрямую возвращали только что выделенное Expr, мы будем обёртывать его в self.add(), так, чтобы возвращать вместо него ExprRef. Вот условие match, при помощи которого создаётся литеральное выражение:

 Rule::number => {
     let num = tree.as_str().parse().unwrap();
-    Expr::Literal(num)
+    self.add(Expr::Literal(num))
 }

С интерпретатором будем поступать так же. Он также становится методом ExprPool, и нам придётся добавить self.get(), чтобы перейти от ExprRef к Expr и для дальнейшего сопоставления с шаблоном:

-fn interp(&self) -> i64 {
+fn interp(&self, expr: ExprRef) -> i64 {
-    match self {
+    match self.get(expr) {

Вот и всё. Думаю, вас впечатляет, насколько мало изменений потребовалось внести — вот полное сравнение, посмотрите сами. Заменяем Box<Expr> на ExprRef, вставляем вызовы add и get в самых очевидных местах — и получаем выровненную версию нашего кода. Симпатично!

Но зачем?

У выровненных абстрактных синтаксических деревьев целый ряд достоинств. По классике принято цитировать те из них, которые связаны с повышением производительности:

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

• Меньшие ссылки. В обычных структурах данных в качестве ссылок используются указатели. В современных архитектурах их размер всегда составляет 64 бит. После выравнивания можно обходиться более мелкими целыми числами. Если вы можете уверенно полагать, что вам никогда не понадобится более 4 294 967 295 узлов AST, то вам хватит и 32-разрядных ссылок — именно так мы и поступили в нашем примере. В результате экономится 50% пространства, затрачиваемого на ссылки, а значит, существенно снижается и общий расход памяти при работе со столь тяжеловесными структурами данных как абстрактные синтаксические деревья (они перегружены указателями). Чем меньше след в памяти, тем меньшую ширину полосы пропуска данных требуется обеспечивать, и даже расположить информацию удаётся качественнее. Такая экономия будет ещё значительнее, если при работе с особенно мелкими структурами данных вы сможете обойтись 16-разрядными или даже 8-разрядными ссылками.

• Дешёвое выделение ресурсов. Во Флатландии не требовалось бы при создании нового узла AST всякий раз вызывать malloc. Напротив, при условии, что у вас заранее выделено достаточно много памяти, где уместится всё необходимое, аллокация может сводиться просто к выбиванию хвостового указателя, чтобы тем самым освободить место ещё для одного Expr. Даже при таком подходе может быть сложно тягаться с по-настоящему быстрым malloc —  но по показателю простоты как таковой с выбивающей аллокацией просто невозможно тягаться.

• Дешёвое высвобождение. Такой подход к выравниванию подразумевает, что вам никогда не потребуется высвобождать отдельные Expr. Пожалуй, это справедливо для многих языковых реализаций, но не для всех. Возможно, вам постоянно придётся достраивать новые поддеревья, но при этом не потребуется высвобождать пространство из-под многих старых. AST обычно «умирают вместе» — то есть обычно бывает достаточно высвободить память сразу из-под целого AST. Тогда как для высвобождения обычного AST требуется обойти все указатели, чтобы освободить каждое Expr в отдельности, выровненное AST можно высвободить одним махом, просто освободив весь ExprPool.

Мне кажется интересным, что во многих вводных материалах по выделению арен именно дешевизна высвобождения (#4) позиционируется как основное достоинство этого метода. Например, в статье Википедии на эту тему пока (вообще!) не упоминается расположение (#1 или #2). Можно утверждать, что фактор #4, пожалуй, наименее важен среди всех настроек компилятора. Поскольку обычно AST существуют на протяжении всего процесса компиляции, вам, возможно, вообще не потребуется их высвобождать.

Здесь мы выигрываем не только в производительности, но и в эргономичности кода:

• Проще ситуация с временами жизни. Подобно тому, как компьютеру проще разом освободить выровненное абстрактное синтаксическое дерево целиком, так и человеку проще судить об управлении памятью с детализацией на уровне целого AST У абстрактного синтаксического дерева с n узлов всего одно значение времени жизни, а не n, где программисту пришлось бы держать в голове все n. Такое упрощение кратно ценнее в Rust, где времена жизни заложены не только в голове у программиста, но и в самом коде. Передача u32 туда‑сюда куда менее хлопотна, чем тщательное управление временами жизни всех ваших &Expr: в коде можно положиться на значительно более простой механизм ExprPool, отвечающий за времена жизни. Подозреваю, именно поэтому такая техника настолько популярна в проектах на Rust. Но, будучи сторонником Rust, настаиваю, что такие же достоинства, связанные с простотой, присущи и C++, и любому другому языку с ручным управлением памятью — правда, они там латентные, а не явные.

• Удобная дедупликация. При работе с двумерным массивом, состоящим из Expr, можно легко и интересно реализовать cons с хешированием или даже более простые приёмы, позволяющие не дублировать идентичные выражения. Например, если мы заметим, что обильно используем выражения‑литералы (Literal) для первых 128 неотрицательных чисел, то можем зарезервировать первые 128 ячеек в нашем ExprPool как раз для них. Тогда, как только кому‑то понадобится целочисленное литеральное выражение 42, нашему ExprPool вообще не придётся конструировать новое Expr — вместо него можно просто произвести ExprRef(42). Такие фокусы возможны и с обычным представлением, основанным на указателях, но, вероятно, потребуют какую‑то вспомогательную структуру данных.

Производительность: результаты

Поскольку теперь у нас есть две реализации на одном и том же языке, давайте измерим их обе с точки зрения производительности и посмотрим, какая лучше. Я случайным образом сгенерировал программу с абстрактным синтаксическим деревом примерно на 100 миллионов узлов и подал её прямо в интерпретатор (парсер и инструмент структурирования печати при этом не использовались). Бенчмарк получился не слишком реалистичным. Всё, что он делает — это генерирует, а затем немедленно выполняет колоссальную программу. Вот некоторые оговорки:

• Я зарезервировал в Vec<Expr> достаточно пространства, чтобы там могла содержаться целая программа. В реалистичном сценарии придётся немало гадать, чтобы правильно подобрать размер арены.

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

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

Но всё-таки чему-то этот пример нас может научить.

Я вооружился Hyperfine, сравнив среднее время выполнения для 10 с лишним прогонов у меня на ноутбуке. Вот график этих прогонов (пока не обращайте внимания на столбик «extra‑flat»; о нём мы поговорим далее). Усы на графике демонстрируют стандартное отклонение на 10+ прогонов. В данном эксперименте обычная версия выполнилась за 3,1 секунды, а выровненная — за 1,3 секунды. Ускорение в 2,4 раза. Неплохо, учитывая, какое тривиальное изменение было внесено в код!

Далее мне стало интересно, какие доли из этого 2,4-кратного выигрыша приходятся на каждую из четырёх выигрышных сторон, которые я упоминал выше. К сожалению, не знаю, как выделить большинство из этих эффектов — но #4, дешёвое высвобождение, особенно хочется рассмотреть отдельно от остальных. Поскольку наш интерпретатор настолько прост, кажется глупым вообще тратить время на высвобождение Expr после того, как выполнение закончится. Программа так или иначе завершится, поэтому мы ничем не рискуем, если эта память потеряется через утечку.

Итак, давайте соберём оба наших интерпретатора в версиях, полностью пропускающих этап высвобождения памяти — и посмотрим, сколько времени они сэкономят. Неудивительно, что версия выровненного интерпретатора «без высвобождения» тратит на работу примерно столько же времени, сколько и стандартная. Из этого можно сделать вывод, что на высвобождение в любом случае время почти не тратится. Но что касается обычного интерпретатора — оказывается, при пропуске высвобождения время работы сокращается с 3,1 до 1,9 секунд. То есть он тратит около 38% рабочего времени просто на высвобождение памяти!

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

Бонус: как выгодно использовать плоское представление

Выше мы рассматривали лишь выравнивание, происходящее «под капотом»: арены и целочисленные сдвиги служили нам импровизированными заменами для обычного выделения и для указателей. Что получится, если сломать этот уровень абстракции — то есть использовать те составляющие двумерного представления, которые не соблюдаются в AST обычной конфигурации?

Давайте напишем третий интерпретатор, в котором используется ещё одно свойство ExprPool, проистекающее именно из того, как мы их строим. Поскольку Expr неизменяемы, состоящие из них деревья приходится собирать снизу вверх. То есть перейти к конструированию родительского выражения можно только после того, как будут собраны все его дочерние Expr. Если собрать выражение a b, a и b должны появиться в своём ExprPool раньше, чем  сошлётся на них. Вернёмся к нашему рисунку: представьте себе, что стрелки ссылок в массиве всегда направлены назад, тогда как данные всегда движутся вперёд. 

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

fn flat_interp(self, root: ExprRef) -> i64 {
    let mut state: Vec<i64> = vec![0; self.0.len()];
    for (i, expr) in self.0.into_iter().enumerate() {
        let res = match expr {
            Expr::Binary(op, lhs, rhs) => {
                let lhs = state[lhs.0 as usize];
                let rhs = state[rhs.0 as usize];
                match op {
                    BinOp::Add => lhs.wrapping_add(rhs),
                    BinOp::Sub => lhs.wrapping_sub(rhs),
                    BinOp::Mul => lhs.wrapping_mul(rhs),
                    BinOp::Div => lhs.checked_div(rhs).unwrap_or(0),
                }
            }
            Expr::Literal(num) => num,
        };
        state[i] = res;
    }
    state[root.0 as usize]
}

Воспользуемся плотной таблицей state, в которой будем хранить по одному результирующему значению на каждое Expr. В строке state[i] = res этот вектор заполняется сразу же, как только мы завершаем работу с выражением. Самое важное, что рекурсии здесь нет — бинарные выражения могут узнать значения своих подвыражений, просто посмотрев их в state. В конце концов, когда state целиком заполнится результатами, нам всего‑то и потребуется, что вернуть результат, соответствующий запрошенному выражению, root.

Этот «сверхплоский» интерпретатор потенциально выигрывает по производительности у рекурсивного сразу в двух отношениях. Во‑первых, не приходится вести учёт состояния стека, поскольку мы не работаем с рекурсивными вызовами. Во‑вторых, обход ExprPool — линейный, и это хорошо сказывается на расположении данных. С другой стороны, в таком интерпретаторе приходится в случайном порядке обращаться к по‑настоящему крупному вектору state, что может повредить расположению данных.

Чтобы проверить, выигрывает ли эта версия в целом, вернёмся к той столбчатой диаграмме, которая была выше. На обход плоского абстрактного синтаксического дерева у сверхплоского интерпретатора уходит 1,2 секунды против 1,3 секунды у рекурсивного интерпретатора. Это совсем мало по сравнению с тем, насколько выравнивание как таковое позволяет выиграть у версии на основе указателей, но повышение производительности на 8,2% — уже что‑то.

Моё любимое наблюдение по поводу этой техники связано с этим комментарием на Reddit от Боба Найстрома и заключается в том, что здесь, фактически, переизобретается байт‑кодовый интерпретатор. Структуры Expr — это инструкции в байт‑коде, и содержащиеся в них ссылки на переменные закодированы как u32. Можно ещё сильнее улучшить этот интерпретатор, заменив нашу простую таблицу state на какой‑либо стек. В таком случае результат в самом деле не будет отличаться от байт‑кодового интерпретатора, который можно спроектировать с нуля. Мне кажется очень изящным, что в этой статье мы «всего лишь» изменили наше абстрактное синтаксическое дерево как структуру данных — и попали из страны обхода деревьев прямиком в страну байт‑кода.

Дополнительные материалы

В своё время я задал на Mastodon вопрос по поводу указателей и другого материала, связанного с выравниванием структур данных — и люди действительно откликнулись (спасибо каждому!) Вот ещё некоторые источники, в которых эта тема всплывала в контексте компиляторов:

• По мнению Майка Полла, производительность LuaJIT отчасти связана с его «линейным промежуточным представлением, в котором нет указателей». В нём нет указателей именно потому, что оно выровнено.

• В том же ключе написан пост, в котором объясняется производительность Sorbet — инструмента проверки типов для Ruby. Автор превозносит достоинства упакованных массивов и рассказывает, как здорово заменять 64-разрядные указатели на 32-разрядные индексы.

• В проекте оболочки Oil собрана большая коллекция ресурсов, посвящённых «компактному представлению AST». Суть многих этих статей сводится к выравниванию.

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

• Есть такая серия работ из университета Пердью и университета штата Индиана. Они рассказывают о компиляции программ, которые непосредственно работали бы с сериализованными данными. В частности, инструмент Gibbon очень похож на переводчик с «нормального» кода на выровненные реализации тех же программ.

• Идеи вроде выравнивания широко встречаются в дата-ориентированном проектировании — это обширная тема, которую я понимаю лишь частично. Например, Эндрю Келли в лекции на эту тему агитирует использовать индексы вместо указателей.

• Посмотрите этот обзор аренных библиотек для Rust и обсуждаемую в нём эргономику времён жизни, связанных с использованием арен.

• Вот пост, в котором сравнивается использование дескрипторов и указателей в разработке игр. Автор выступает за упаковку однотипных объектов в массивы и за дальнейшее использование индексов для ссылок на эти объекты.

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

Уже после публикации оригинала этого поста читатели указали на статью Инанны Малик, где продемонстрированы те же приёмы на примере игрушечного «калькуляторного» языка, реализованного на основе Rust. В том посте также используются схемы рекурсии — красивая идея, позаимствованная из мира Haskell. С её помощью удобно делать абстракции, охватывающие различные конкретные представления. Настоятельно рекомендую изучить этот пост.