Em busca de desempenho ao construir um compilador JavaScript

Publicado originalmente em https://rustmagazine.org/issue-3/javascript-compiler/

Sobre desempenho

Depois de dois anos escrevendo Rust, desempenho virou disciplina automática: em essência, alocar menos memória e usar menos ciclos de CPU.

Sem domínio do problema e sem saber quais alavancas puxar, atingir o ótimo é difícil.

Nas seções abaixo conto minha jornada de otimização. Aprendo misturando leitura, tentativa e erro — a organização do texto reflete isso.

Parsing

O Oxc é um compilador “clássico”: AST, léxico e parser de descida recursiva.

Abstract Syntax Tree (AST)

A primeira decisão arquitetural de um compilador é a forma da AST.

Todas as ferramentas JavaScript trabalham no nível da AST:

um linter (por ex. ESLint) procura erros na AST;
um formatter (por ex. Prettier) imprime a AST de volta em texto;
um minificador (por ex. terser) transforma a AST;
um bundler liga import/export entre ASTs de arquivos diferentes.

Sem uma AST amigável, construir essas ferramentas dói.

Para JavaScript, a especificação mais usada é estree. Minha primeira AST copiava 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>,
}

Em Rust a árvore cai bem natural com structs e enums.

Alocação de memória

Fiquei meses nessa AST enquanto escrevia o parser. Um dia perfilhei: muito tempo em drop.

💡 Nós da AST vão para a heap via Box ou Vec, um a um, e são liberados em sequência.

Há como suavizar isso?

Estudando outros parsers JS em Rust — principalmente ratel e jsparagus —

ambos declaram AST com lifetime,

rust

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

e trazem um arena.rs junto.

Ignorei isso até ler sobre arenas: bumpalo e toolshed.

Resumo: a arena reserva memória em blocos/páginas e libera tudo de uma vez ao destruí-la. Com AST na arena, o drop fica rápido.

Efeito colateral bom: AST nasce numa ordem previsível e a travessia segue layout linear — ótimo para linha/cache da CPU.

Para iniciantes Rust, parametrizar tudo com lifetimes dói; levei cinco tentativas para encaixar a AST em bumpalo.

Só mudar para arena valeu ~20% de ganho.

Tamanho de enums

Pela recursão precisamos de indireção — senão o compilador grita “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>,

Ou boxamos variantes do enum ou campos das structs.

A mesma discussão já existia em 2017 no fórum: Is there a better way to represent an abstract syntax tree?

Aleksey (matklad) sugeriu boxar variantes para manter Expression pequeno. Por quê?

O layout de memória de um enum Rust depende do maior variante. Exemplo de ~56 bytes (tag + carga + alinhamento):

rust

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

Numa AST JS típica, Expression tem dezenas de variantes, Statement também — 200+ bytes se nada for boxado. Esses bytes viajam a cada matches!(expr, Expression::Variant(_)) — ruim para cache.

Solução: envolver variantes em Box.

O perf-book explica como caçar tipos grandes.

Também copiei testes que limitam tamanho de 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);
}

Boxar variantes rendeu ~10% a mais.

Span

Às vezes economia só aparece olhando os campos com calma.

Folhas da AST carregam “span” — dois offsets no fonte; eu usava dois usize.

rust

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

Apontaram que u32 é seguro na prática (arquivos < 4 GB) e reduz pico de memória.

Trocar para u32 melhorou até ~5% em arquivões.

Strings e identificadores

Tentamos &str apontando para o fonte em literais e nomes.

rust

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

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

Porém em JavaScript há sequências de escape: '\251', '\xA9' e '©' representam o mesmo símbolo.

Precisamos calcular o valor escapado e alocar String nova.

Internamento de strings

Com muitas strings na heap, string interning guarda uma cópia por valor distinto.

string-cache (time Servo) era minha escolha inicial. Parser single-thread voava; ao paralelizar o linter com Rayon, CPU ficou ~50% das cores.

No perf surgia parking_lot::raw_mutex::RawMutex::lock_slow. Não entendia de locks, mas lock global soava estranho — removi string-cache e liberei uso total de CPU.

Tirar string-cache da AST deu ~30% no parse paralelo.

string-cache

Meio ano depois, outro projeto crítico: string-cache voltou a serializar threads no parse de texto.

Estudei o código depois de ler Rust Atomics and Locks (Mara Bos).

Trechos relevantes do lock: dynamic_set e atom (código de 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);

Ou seja: mutex no Set inteiro a cada inserção — chamado o tempo todo no parser, logo sincronização pesa.

Olhando o 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
}

Parece hash map com sondagem — na prática Mutex<HashMap> global.

Levei um mês para enxergar; quando cliquei que era concurrent hashmap, colocar mutex por bucket em vez do mapa inteiro foi óbvio. Em uma hora abri PR feliz 🙂.

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

Internamento de string é campo de batalha no ecossistema Rust. O post String interners in Rust lista libs single-thread (string-interner, lasso, …).

Como parseamos em paralelo, dá para tentar multithread como ustr. Perf de ustr e string-cache melhorado ainda ficou atrás da abordagem abaixo.

Hipóteses do atraso:

hashing para deduplicar;
indireção longe da CPU (cache ruim).

Inlining de string

Voltamos ao problema original: alocar demais. Muitos identificadores e literais são curtos — dá para guardar bytes na pilha (string inlining).

Queremos algo como:

rust

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

Para o enum ficar compacto, InlineRepresentation deve ter o mesmo tamanho que 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>());
}

Há várias crates competindo nesse nicho:

Cada uma troca memória por trade-offs diferentes — clones O(1) em smol_str/flexstr, capacidades de inline distintas, etc.

fasterthanli.me tem mergulho profundo.

Trocar String por compact_str::CompactStr cortou alocações brutalmente.

Lexer

Token

O léxico transforma texto em token estruturado.

rust

pub struct Token {
    pub kind: Kind,
}

Em Rust, Kind costuma ser enum; variantes carregam dados específicos.

rust

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

Esse enum pode pesar 32 bytes; léxicos geram milhões de tokens — cada For/While paga 32 bytes na stack.

Truque: separar Kind (1 byte) dos valores num segundo enum:

rust

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

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

Como controlamos o parser, mantemos invariante kind ↔ value.

Mesmo 32 bytes em TokenValue ainda doem se alocados sem parar.

Seguindo go to definition: 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,
}

Como todo mundo sabe, String é Vec<u8>; Vec traz len e cap. Como não vamos mutar a string do token, podemos economizar memória descartando cap e usando &str.

rust

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

TokenValue cai para 24 bytes.

Trocar String por fatia reduz memória, mas exige lifetime — o borrow checker espalha anotações pelo código. Perdi esse jogo por oito meses até ganhar de vez.

Quando couber, use tipos owned imutáveis compactos, por exemplo Box<str> no lugar de String grande.

Em resumo: sempre dá para apertar estruturas; às vezes o ganho aparece no profiler.

Cow

Vi Cow estudando jsparagus, no AutoCow.

Ao tokenizar string JS, aloque buffer novo só se aparecer escape; senão reuse o fatia original:

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()],
    }
}

Na prática não aloca quase nunca porque escapes são raros.

O texto oficial do Cow (“clone-on-write…”) sempre me confundiu.

The type Cow is a smart pointer providing clone-on-write functionality...

Se você também é iniciante em Rust, isso não esclarece nada 😅.

Foi sugerido pensar menos em clone-on-write e mais RefOrOwned: ou referência ou valor owned — abrange os casos reais.

SIMD

Ao reler blogs antigos de Rust, o Portable SIMD PG chamou atenção. Sempre quis experimentar SIMD; achei cenário plausible com How quickly can you remove spaces from a string?.

RapidJSON já pula espaço com SIMD.

Combinando portable-SIMD + ideias herdadas consegui pular espaços e comentários multilinha — cada um vale alguns pontos percentuais.

Keyword match

No topo do profile aparece hotspot (~1–2%) casando identificadores com keywords:

rust

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

Com TypeScript são 84 strings candidatas. O post do V8 Blazingly fast parsing, parte 1 descreve o matcher gerado.

Lista estática ⇒ podemos calcular perfect hash que aponta para no máximo uma keyword. V8 usa gperf; o hash combina comprimento + dois primeiros caracteres; comparamos só quando o comprimento bate.

Hash + inteiro soa melhor que 84 comparações — tentamos várias vezes sem vitória (outra PR).

LLVM já havia otimizado o match. Com --emit=llvm-ir aparece algo assim:

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 é a string; %s.1, o comprimento — o compilador ramifica pelo tamanho! Ele é mais esperto 😃.

(Nesse ponto já estávamos lendo LLVM IR e assembly.)

@strager publicou o vídeo Faster than Rust and C++: the PERFECT hash table — ótimo para raciocinar sobre microperf.

No fim, o match simples ficou porque o hotspot era só ~1–2%; não valia dias montando hash perfeito — Rust ainda não entrega todas as peças prontas.

Linter

Um linter vasculha o código procurando problemas.

Versão trivial: visitor pattern anda nó por nó.

rust

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

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

Árvore com ponteiro para o pai

Descemos fácil com visitors; para subir e coletar contexto a coisa quebra — Rust não deixa pendurar ponteiro de pai em cada AST typed sem gambiarra.

Modelo ingênuo com Rc:

rust

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

Mutar assim é trabalhoso e o drop fica fragmentado — caro.

Melhor densidade: Vec + índices.

rust

struct Tree {
    nodes: Vec<Node>
}

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

indextree facilita demais.

Na AST, cada nó do índice aponta para enum “untyped” embrulhando todas as variantes JS.

rust

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

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

Visitors disparam callbacks enter/leave que empilham essa árvore auxiliar:

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();
    }
}

Estrutura final: indextree::Arena<Node<'a>> com AstKind<'a>; parent() sobe níveis sem reimplementar Visit inteiro novamente para cada regra.

rust

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

Exemplo integral na repo.

À primeira vista parece pesado, mas navegar AST em arena empurrando ponteiros mantém sequência linear. Benchmark atual: 84× mais rápido que ESLint — mais que suficiente.

Processar arquivos em paralelo

ignore percorre pastas (gitignore, .eslintignore), mas não exporta iterators paralelos — nada de par_iter em ignore::Walk.

Workaround com Rayon + canais:

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);
        });
    }
});

Lint paralelo, impressão ordenada na thread única dedicada aos diagnósticos.

Imprimir também custa caro

Depois de meses rodando contra monorepos enormes, spammar diagnósticos no console parecia eternidade mesmo com linter rápido.

Issues úteis:

println! re-trava stdout a cada newline (line buffering). Para velocidade máxima, use buffering explícito, guia oficial de CLIs Rust:

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

Ou trave apenas o handle sem BufWriter:

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

Em busca de desempenho ao construir um compilador JavaScript ​

Sobre desempenho ​

Parsing ​

Abstract Syntax Tree (AST) ​

Alocação de memória ​

Tamanho de enums ​

Span ​

Strings e identificadores ​

Internamento de strings ​

string-cache ​

Inlining de string ​

Lexer ​

Token ​

Cow ​

SIMD ​

Keyword match ​

Linter ​

Árvore com ponteiro para o pai ​

Processar arquivos em paralelo ​

Imprimir também custa caro ​

Em busca de desempenho ao construir um compilador JavaScript

Sobre desempenho

Parsing

Abstract Syntax Tree (AST)

Alocação de memória

Tamanho de enums

Span

Strings e identificadores

Internamento de strings

string-cache

Inlining de string

Lexer

Token

Cow

SIMD

Keyword match

Linter

Árvore com ponteiro para o pai

Processar arquivos em paralelo

Imprimir também custa caro