Путь к производительности при сборке компилятора JavaScript

Первоначально опубликовано на https://rustmagazine.org/issue-3/javascript-compiler/

О производительности

Два года на Rust приучили воспринимать производительность как дисциплину: в двух словах — меньше аллокаций и меньше циклов CPU.

Оптимум без понимания предметной области и без знания приёмов достичь трудно.

Ниже — мой путь оптимизаций. Я учусь сочетанием чтения, проб и ошибок — структура разделов отражает это.

Разбор (parsing)

Oxc — обычный компилятор: AST, лексер и рекурсивный спуск.

Абстрактное синтаксическое дерево (AST)

Первое архитектурное решение компилятора — форма AST.

Все инструменты JavaScript работают на уровне AST:

линтер (напр. ESLint) ищет ошибки в AST
форматтер (напр. Prettier) печатает AST обратно в текст
минификатор (напр. Terser) преобразует AST
бандлер связывает import/export между AST разных файлов

Без удобного AST эти инструменты строить больно.

Чаще всего для JavaScript берут спецификацию estree. Моя первая версия AST повторяла estree:

rust

pub struct Program {
    pub node: Node,
    pub body: Vec<Statement>,
}

pub enum Statement {
    VariableDeclarationStatement(VariableDeclaration),
}

pub struct VariableDeclaration {
    pub node: Node,
    pub declarations: Vec<VariableDeclarator>,
}

В Rust дерево задаётся структурами и enum’ами достаточно прямолинейно.

Выделение памяти

Несколько месяцев я жил с этой версией AST, пока писал парсер. Потом включил профилировщик: много времени уходило на drop.

💡 Узлы AST на куче через Box/Vec выделяются по одному и освобождаются по очереди.

Как смягчить?

Параллельно я смотрел другие парсеры JS на Rust — ratel и jsparagus.

У обоих AST с аннотацией времени жизни,

rust

pub enum Statement<'ast> {
    Expression(ExpressionNode<'ast>),
}

и рядом лежит файл arena.rs.

Сначала я не понимал зачем это и игнорировал, пока не прочёл про arena: bumpalo и toolshed.

Кратко: arena резервирует память кусками/страницами и освобождает всё разом при сбросе arena. AST на arena — дроп становится очень быстрым.

Плюс: AST собирается в предсказуемом порядке, обход совпадает с порядком размещения — доступ к памяти линеен и дружественен кешу строк.

Rust-новичкам с lifetime это нелегко: все структуры и функции нужно параметризовать. Пять попыток, прежде чем AST переехал в bumpalo.

Переход на arena дал порядка +20% к скорости.

Размеры перечислений

Из-за рекурсии в AST нужны косвенности, иначе компилятор ругается «recursive without indirection»:

error[E0072]: recursive types `Enum` and `Variant` have infinite size
 --> crates/oxc_linter/src/lib.rs:1:1
  |
1 | enum Enum {
  | ^^^^^^^^^
2 |     Variant(Variant),
  |             ------- recursive without indirection
3 | }
4 | struct Variant {
  | ^^^^^^^^^^^^^^
5 |     field: Enum,
  |            ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
2 ~     Variant(Box<Variant>),
3 | }
4 | struct Variant {
5 ~     field: Box<Enum>,

Два варианта: оборачивать вариант enum или поле структуры.

Тот же вопрос нашёлся на форуме Rust ещё в 2017, Is there a better way to represent an abstract syntax tree?

Aleksey (matklad) советовал упаковать варианты enum в Box, чтобы сам Expression оставался компактным. Что это даёт?

Память Rust-enum зависит от размеров всех вариантов; итог — по самому большому варианту. Например, такой enum занимает 56 байт (тег + полезная нагрузка + выравнивание).

rust

enum Enum {
    A, // 0 byte payload
    B(String), // 24 byte payload
    C { first: String, last: String }, // 48 byte payload
}

В типичном JS-AST у Expression десятки вариантов, у Statement — тоже много. Без boxing это 200+ байт на значение. Эти байты таскаются и читаются при каждом matches!(expr, Expression::Variant(_)) — плохо для кеша.

Эффективнее оборачивать варианты в Box.

В perf-book есть детали про поиск тяжёлых типов.

Я скопировал тест на ограничение размера enum.

rust

#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
#[test]
fn no_bloat_enum_sizes() {
    use std::mem::size_of;
    use crate::ast::*;
    assert_eq!(size_of::<Statement>(), 16);
    assert_eq!(size_of::<Expression>(), 16);
    assert_eq!(size_of::<Declaration>(), 16);
}

Boxing вариантов дал примерно +10% скорости.

Span

Иногда меньший расход памяти виден только после внимательного взгляда на поля.

У листьев AST есть «span» — два смещения в исходнике, у меня это были два usize.

rust

pub struct Node {
    pub start: usize,
    pub end: usize,
}

Подсказали, что безопасно заменить usize на u32, чтобы снизить пик памяти: больше u32 — только если файл тяжелее 4 ГБ.

Переход на u32 дал до ~5% на больших файлах.

Строки и идентификаторы

В AST хочется хранить ссылки &str на исходник для имён и строковых литералов.

rust

pub struct StringLiteral<'a> {
    pub value: &'a str,
}

pub struct Identifier<'a> {
    pub name: &'a str,
}

Но в JavaScript у строк и идентификаторов бывают escape-последовательности: '\251', '\xA9' и '©' — один символ копирайта.

Приходится вычислять значение после escape и заводить новый String.

Интернирование строк

Когда строк на куче очень много, пригодится интернирование строк: каждое уникальное значение один раз в кэше.

string-cache от команды Servo распространён. Сначала я использовал его для идентификаторов и строк в AST. В одном потоке парсер летал, но при линтере с несколькими парсерами под rayon загрузка CPU держалась около 50%.

В профиле всплыл parking_lot::raw_mutex::RawMutex::lock_slow. В многопоточности я тогда не разбирался, но глобальный замок выглядел подозрительно — убрал string-cache, чтобы выжать все ядра.

Удаление string-cache из AST дало ~+30% к параллельному парсингу.

string-cache

Полгода спустя в другом проекте string-cache снова тормозил все потоки при разборе текста.

Я разобрался, что он делает, уже после книги Rust Atomics and Locks Мары Бос.

Вот релевантный код вокруг замка (коду около восьми лет, 2015).

rust

pub(crate) static DYNAMIC_SET: Lazy<Mutex<Set>> = Lazy::new(|| {
    Mutex::new({

// ... in another place
let ptr: std::ptr::NonNull<Entry> =
    DYNAMIC_SET.lock().insert(string_to_add, hash.g);

Всё просто: при каждой вставке строки блокируется структура Set. В парсере это вызывается постоянно — синхронизация бьёт по времени.

Посмотрим на Set:

rust

pub(crate) fn insert(&mut self, string: Cow<str>, hash: u32) -> NonNull<Entry> {
    let bucket_index = (hash & BUCKET_MASK) as usize;
    {
        let mut ptr: Option<&mut Box<Entry>> = self.buckets[bucket_index].as_mut();

        while let Some(entry) = ptr.take() {
            if entry.hash == hash && *entry.string == *string {
                if entry.ref_count.fetch_add(1, SeqCst) > 0 {
                    return NonNull::from(&mut **entry);
                }
                entry.ref_count.fetch_sub(1, SeqCst);
                break;
            }
            ptr = entry.next_in_bucket.as_mut();
        }
    }
    debug_assert!(mem::align_of::<Entry>() >= ENTRY_ALIGNMENT);
    let string = string.into_owned();
    let mut entry = Box::new(Entry {
        next_in_bucket: self.buckets[bucket_index].take(),
        hash,
        ref_count: AtomicIsize::new(1),
        string: string.into_boxed_str(),
    });
    let ptr = NonNull::from(&mut *entry);
    self.buckets[bucket_index] = Some(entry);

    ptr
}

Похоже на поиск корзины и вставку, если строки там ещё нет.

💡 Это нечто вроде линейного зондирования? Тогда Set — по сути HashMap. 💡 А Mutex<HashMap> — конкурентная хеш-таблица.

Решение кажется очевидным задним числом, но месяц ушёл, пока я осознал проблему. Когда стало ясно, что это общий mutex на всю таблицу, перенос блокировки на уровень корзин оказался логичным шагом. Через час после правки я отправил PR и остался доволен 😃.

https://github.com/servo/string-cache/pull/268

Интернирование строк в Rust-сообществе — отдельное поле битвы. В этой статье перечислены однопоточные крейты: string-interner, lasso, lalrpop-intern, intaglio, strena.

Мы парсим файлы параллельно; вариант — многопоточный интернер вроде ustr. По профилю и ustr, и улучшенный string-cache всё равно отставали от подхода, о котором ниже.

Вероятные причины:

хеширование при дедупликации
косвенное обращение к строке «далеко» на куче — не дружит с кешем строк

Инлайн строк

Возвращаемся к проблеме массовых строк. Частичное решение — смотреть на данные: короткие имена переменных и короткие литералы. Есть приём string inlining: байты строки хранятся на стеке (внутри маленькой обёртки).

В идеале нужен такой enum:

rust

enum Str {
    Static(&'static str),
    Inline(InlineReprensation),
    Heap(String),
}

Чтобы enum не раздувался, InlineRepresentation по размеру должен совпасть с String.

rust

#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
#[test]
fn test_size() {
    use std::mem::size_of;
    assert_eq!(size_of::<String>(), size_of::<InlineReprensation>());
}

Много крейтов борются за память строк — ещё одно «поле битвы».

Лексер

Токен

Лексер (tokenizer) переводит исходный текст в токены.

rust

pub struct Token {
    pub kind: Kind,
}

Тип токена удобно держать перечислением; варианты несут данные конкретного токена.

rust

pub enum Kind {
    // Keywords
    For,
    While,
    ...
    // Literals
    String(String),
    Num(f64),
    ...
}

Такое перечисление легко разрастается до 32 байт, а лексер строит миллионы экземпляров Kind. Каждый Kind::For тащит эти байты как структура на стеке.

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

rust

pub struct Token<'a> {
    pub kind: Kind,
    pub value: TokenValue
}

pub enum TokenValue {
    None,
    String(String),
    Num(f64),
}

Раз мы контролируем весь разбор, согласованность «вид токена + значение» — на нашей совести.

32 байта у TokenValue уже немного, но при огромном числе конструкторов это всё равно ощущается.

Разберём тип String через переход по определениям: String → Vec → RawVec:

rust

pub struct String {
    vec: Vec<u8>,
}

pub struct Vec {
    buf: RawVec<T, A>,
    len: usize,
}

pub struct RawVec {
    ptr: Unique<T>,
    cap: usize,
    alloc: A,
}

String — по сути Vec<u8> с длиной и ёмкостью. Строку мы не мутируем — можно избавиться от поля cap и взять срез &str.

rust

pub enum TokenValue<'a> {
    None,
    String(&'a str),
    Num(f64),
}

TokenValue сжимается до 24 байт.

Цена — время жизни: заимствование затрудняет заимствование у заимствователя почти всего проекта. В прошлый раз я проиграл заимствователю 8 месяцев, но потом всё же выиграл.

Когда уместно, можно брать владеющие неизменяемые представления без ссылок — например Box<str> вместо String, Box<[u8]> вместо Vec<u8>.

Итого: есть приёмы держать структуры маленькими — иногда это прямо ускоряет.

Cow

Термин Cow впервые увидел в jsparagus, там AutoCow.

При токенизации строки JS: если был escape — выделяем новую строку, иначе возвращаем срез исходника:

rust

fn finish(&mut self, lexer: &Lexer<'alloc>) -> &'alloc str {
    match self.value.take() {
        Some(arena_string) => arena_string.into_bump_str(),
        None => &self.start[..self.start.len() - lexer.chars.as_str().len()],
    }
}

В большинстве случаев escape редкий — аллокации почти нет.

Но официально Cow — «clone-on-write»…

The type Cow is a smart pointer providing clone-on-write functionality: it can enclose and provide immutable access to borrowed data, and clone the data lazily when mutation or ownership is required. The type is designed to work with general borrowed data via the Borrow trait.

Новичку в Rust (как я тогда) такое описание мало помогает (и до сих пор).

Объяснили, что clone-on-write — лишь частный случай. Лучше думать о типе как о RefOrOwned: либо ссылка, либо владение.

SIMD

В архивных постах Rust зацепил Portable SIMD PG. Долго хотел попробовать SIMD.

Нашёл задачу для парсера: How quickly can you remove spaces from a string? (Daniel Lemire). В RapidJSON уже SIMD для пропуска пробелов.

С portable-SIMD и подсказками RapidJSON получилось ускорить пропуск пробелов и многострочных комментариев.

Прирост — несколько процентов.

Сопоставление ключевых слов

На вершине профиля горячий путь около 1–2% времени.

Строку нужно отнести к ключевому слову JS:

rust

fn match_keyword(s: &str) -> Self {
    match s {
        "as" => As,
        "do" => Do,
        "if" => If,
        ...
        "constructor" => Constructor,
        _ => Ident,
    }
}

С TypeScript кандидатов для сравнения стало 84. В статье V8 оптимизация сканера описано сопоставление ключевых слов.

Since the list of keywords is static, we can compute a perfect hash function that for each identifier gives us at most one candidate keyword. V8 uses gperf to compute this function. The result computes a hash from the length and first two identifier characters to find the single candidate keyword. We only compare the identifier with the keyword if the length of that keyword matches the input identifier length.

Казалось, быстрый хеш + проверка длины обгонят 84 строковых сравнения. Пробовали раз и два — толку мало.

Оказалось, LLVM уже оптимизировал наш код. Флаг --emit=llvm-ir у rustc показывает ветвление по длине строки %s.1:

switch i64 %s.1, label %bb6 [
  i64 2, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit.i"
  i64 3, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit280.i"
  i64 4, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit325.i"
  i64 5, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit380.i"
  i64 6, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit450.i"
  i64 7, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit540.i"
  i64 8, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit590.i"
  i64 9, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit625.i"
  i64 10, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit655.i"
  i64 11, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit665.i"
], !dbg !191362

%s — строка, %s.1 — её длина… компилятор ветвит по длине! Компилятор умнее нас 😃.

(Да, мы уже смотрели LLVM IR и ассемблер.)

Позже @strager выложил видео Faster than Rust and C++: the PERFECT hash table — системный подход к микрооптимизациям.

В итоге оставили простой match по ключевым словам: это 1–2% профиля, а дни на «идеальную» хеш-таблицу в Rust не окупились — не хватает кирпичиков из коробки.

Линтер

Линтер анализирует исходник на проблемы.

Простейший вариант — обойти AST и проверять правила. Подойдёт паттерн «посетитель»:

rust

pub trait Visit<'a>: Sized {
    // ... lots of visit functions

    fn visit_debugger_statement(&mut self, stmt: &'a DebuggerStatement) {
        // report error
    }
}

Дерево с указателем на родителя

Визиторами легко спускаться по AST, но как подниматься вверх?

В Rust нельзя просто повесить указатель на родителя в узел AST.

Отвлечёмся: общее дерево, у узла есть индекс родителя. Чтобы тип узла был один, родителя можно держать через Rc:

rust

struct Node {
    parent: Option<Rc<Node>>,
}

С мутациями это утомительно, плюс узлы освобождаются не синхронно — не быстро.

Эффективнее хранить узлы в Vec и ссылаться индексами.

rust

struct Tree {
    nodes: Vec<Node>
}

struct Node {
    parent: Option<usize> // index into `nodes`
}

indextree удобен для этого.

Возвращаясь к AST: строим indextree, где каждый узел указывает на enum, оборачивающий все виды узлов AST. Это «нетипизированный» слой поверх основного AST.

rust

struct Node<'a> {
    kind: AstKind<'a>
}

enum AstKind<'a> {
    BlockStatement(&'a BlockStatement<'a>),
    // ...
    ArrayExpression(&'a ArrayExpression<'a>),
    // ...
    Class(&'a Class<'a>),
    // ...
}

Остаётся в колбэках визитора реально строить дерево.

rust

pub trait Visit<'a> {
    fn enter_node(&mut self, _kind: AstKind<'a>) {}
    fn leave_node(&mut self, _kind: AstKind<'a>) {}

    fn visit_block_statement(&mut self, stmt: &'a BlockStatement<'a>) {
        let kind = AstKind::BlockStatement(stmt);
        self.enter_node(kind);
        self.visit_statements(&stmt.body);
        self.leave_node(kind);
    }
}

impl<'a> Visit<'a> for TreeBuilder<'a> {
    fn enter_node(&mut self, kind: AstKind<'a>) {
        self.push_ast_node(kind);
    }

    fn leave_node(&mut self, kind: AstKind<'a>) {
        self.pop_ast_node();
    }
}

Итог: indextree::Arena<Node<'a>>, у каждого Node — указатель на AstKind<'a>. Через indextree::Node::parent получаем родителя.

Плюс: можно обходить AST без набора своих visitor’ов — линтер становится простым циклом по узлам indextree:

rust

for node in nodes {
    match node.get().kind {
        AstKind::DebuggerStatement(stmt) => {
        // report error
        }
        _ => {}
    }
}

Полный пример здесь.

Свиду кажется дорого, но обход типизированного AST из arena и push указателя в indextree — линейные, «дружественные кешу» паттерны. По нашим замерам такой подход порядка в 84 раза быстрее ESLint — нам достаточно.

Параллельная обработка файлов

Для обхода каталогов линтер использует крейт ignore с поддержкой .gitignore и внешних ignore-листов вроде .eslintignore.

Нет параллельного API: у ignore::Walk::new(".") нет par_iter.

Приходится собирать обход из примитивов (как здесь)

rust

let walk = Walk::new(&self.options);
rayon::spawn(move || {
    walk.iter().for_each(|path| {
        tx_path.send(path).unwrap();
    });
});

let linter = Arc::clone(&self.linter);
rayon::spawn(move || {
    while let Ok(path) = rx_path.recv() {
        let tx_error = tx_error.clone();
        let linter = Arc::clone(&linter);
        rayon::spawn(move || {
            if let Some(diagnostics) = Self::lint_path(&linter, &path) {
                tx_error.send(diagnostics).unwrap();
            }
            drop(tx_error);
        });
    }
});

Так удобно печатать все диагностики в одном потоке — к последней теме статьи.

Вывод на консоль медленный

Печать диагностик сама по себе не «вечность», но на огромном монолите тысячи сообщений каждый прогон ощущаются бесконечностью.

Нашёл тикеты:

Кратко: println! на каждую строку берёт блокировку stdout — построчная буферизация. Быстрее явно использовать блочную буферизацию (заметка в rust-cli book).

rust

use std::io::{self, Write};

let stdout = io::stdout(); // get the global stdout entity
let mut handle = io::BufWriter::new(stdout); // optional: wrap that handle in a buffer
writeln!(handle, "foo: {}", 42); // add `?` if you care about errors here

Или взять эксклюзивную блокировку stdout:

rust

let stdout = io::stdout(); // get the global stdout entity
let mut handle = stdout.lock(); // acquire a lock on it
writeln!(handle, "foo: {}", 42); // add `?` if you care about errors here

Путь к производительности при сборке компилятора JavaScript ​

О производительности ​

Разбор (parsing) ​

Абстрактное синтаксическое дерево (AST) ​

Выделение памяти ​

Размеры перечислений ​

Span ​

Строки и идентификаторы ​

Интернирование строк ​

string-cache ​

Инлайн строк ​

Лексер ​

Токен ​

Cow ​

SIMD ​

Сопоставление ключевых слов ​

Линтер ​

Дерево с указателем на родителя ​

Параллельная обработка файлов ​

Вывод на консоль медленный ​

Путь к производительности при сборке компилятора JavaScript

О производительности

Разбор (parsing)

Абстрактное синтаксическое дерево (AST)

Выделение памяти

Размеры перечислений

Span

Строки и идентификаторы

Интернирование строк

string-cache

Инлайн строк

Лексер

Токен

Cow

SIMD

Сопоставление ключевых слов

Линтер

Дерево с указателем на родителя

Параллельная обработка файлов

Вывод на консоль медленный