Rewriting the lexer benchmark in Rust - Eli Bendersky's website

Rust Joins the Lexer Shootout

My long-running experiment with hand-written lexers for the TableGen language has now spanned Python, JavaScript, and Go. In the most recent round, several years of Go compiler improvements plus a few targeted tweaks brought the Go version down to 5.6 ms for a 1 MiB input file. Since I've been getting more comfortable with Rust, it felt like the natural next language to throw at the same problem — and, being the lowest-level option in the set so far, expectations were high.

The complete source for this exercise is on GitHub.

Ownership Shapes the API

Rust's ownership rules force API design decisions early and explicitly. When constructing a lexer over an input string, the question of who owns that string can't be left as an implicit contract (as in C or C++) or deferred to runtime (as in Python, JS, or Go). It has to be encoded in the types themselves.

Given the performance focus of this series, I started with a zero-copy design. The caller keeps ownership of the input; tokens returned by the lexer hold references into it. Rust's lifetime annotations make this relationship explicit:

pub struct Lexer<'source> {
  input: &'source str,
  iter: Peekable<CharIndices<'source>>,

  // c is the last char taken from iter, and ci is its offset in the input.
  c: char,
  ci: usize,

  // error is true iff the lexer encountered and error.
  error: bool,
}

The 'source lifetime ties the lexer's stored string slice to the input's lifetime. The constructor and token-fetching methods carry the same annotation:

impl<'source> Lexer<'source> {
    pub fn new(input: &'source str) -> Self {
      // ...
    }
}

pub fn next_token(&mut self) -> Token<'source> {
  // ...
}

The Token type mirrors this:

#[derive(Debug, PartialEq, Clone, Copy)]
pub struct Token<'source> {
    pub value: TokenValue<'source>,
    pub pos: usize,
}

#[derive(Debug, PartialEq, Clone, Copy)]
pub enum TokenValue<'source> {
    EOF,
    Error,

    Plus,
    Minus,
    Multiply,
    Divide,
    Period,
    Backslash,
    Colon,
    Percent,
    Pipe,
    Exclamation,
    Question,
    Pound,
    Ampersand,
    Semi,
    Comma,
    LeftParen,
    RightParen,
    LeftAng,
    RightAng,
    LeftBrace,
    RightBrace,
    LeftBracket,
    RightBracket,
    Equals,
    Comment(&'source str),
    Identifier(&'source str),
    Number(&'source str),
    Quote(&'source str),
}

Some token variants reference the input directly, and those references are alive exactly as long as the input. The mechanism is clear from the signatures: next_token returns tokens whose lifetime is bounded by the slice passed to the constructor.

Iterating over tokens is clean, too, thanks to the Iterator trait:

// Lexer is an Iterator; it returns tokens until EOF is encountered, when it
// returns None (the EOF token itself is not returned). Note that errors are
// still returned as tokens with TokenValue::Error.
impl<'source> Iterator for Lexer<'source> {
    type Item = Token<'source>;
    fn next(&mut self) -> Option<Self::Item> {
        if self.error {
            // If an error has already been set before we invoke next_token,
            // it means we've already returned TokenValue::Error once and now
            // we should terminate the iteration.
            return None;
        }

        let tok = self.next_token();
        if tok.value == TokenValue::EOF {
            None
        } else {
            Some(tok)
        }
    }
}

That allows collecting every token with a single expression:

pub fn tokenize_all_collect<'source>(data: &'source str) -> Vec<Token<'source>> {
    let lex = Lexer::new(&data);
    lex.collect()
}

Implementation Notes

The core scanning approach mirrors what I've done in the other languages. Two Rust-specific details are worth calling out.

First, Unicode support comes via Rust's string iterators. The lexer tracks position using CharIndices, which yields each char alongside its byte index. Because lookahead is needed in a few places, that iterator is wrapped in Peekable:

iter: Peekable<CharIndices<'source>>,

Second, token extraction is done by sub-slicing the input. In scan_number, for instance:

fn scan_number(&mut self) -> Token<'source> {
    let startpos = self.ci;
    while self.c.is_digit(10) {
        self.scan_char();
    }
    Token {
        value: TokenValue::Number(&self.input[startpos..self.ci]),
        pos: startpos,
    }
}

The Number variant of TokenValue is Number(&'source str) — a reference into the original input. Sub-slicing crates a new slice of the same lifetime, at no heap cost, just as in Go.

Benchmark Results

The Rust lexer is fast. Running it on the same large TableGen file used for all prior benchmarks, it finished in 3.7 ms — roughly 33% faster than the best Go version from the previous post.

Profiling Rust is less convenient than Go, but with the right combination of flags and perf invocations it's clear that next_token accounts for the bulk of the runtime, which is exactly where the time should be going.

An Allocating Variant

The zero-copy API made sense for performance, but past Go experiments looked at alternative designs, so I wanted to test analogous options in Rust. Two ownership changes are possible: the lexer could take ownership of the input, or tokens could return owned Strings rather than references.

Owning the input is awkward. The constructor would look like:

pub fn new(input: String) -> Self

But storing an iterator that references a string held in the same struct is something Rust's borrow checker rejects — there's no safe way to move such a struct, since the reference would dangle. Working around that would require opaque indices or unsafe, which I wanted to avoid. When the language resists a design that hard, it's often signaling that the design itself is wrong; better to leave input ownership with the caller.

Returning owned strings, by contrast, is straightforward. The owning.rs variant in the repository uses the same constructor but defines tokens differently:

#[derive(Debug, PartialEq, Clone)]
pub struct Token {
    pub value: TokenValue,
    pub pos: usize,
}

#[derive(Debug, PartialEq, Clone)]
pub enum TokenValue {
    // .. types
    Comment(String),
    Identifier(String),
    Number(String),
    Quote(String),
}

Variants like Identifier now hold a String, so Token needs no lifetime parameters. Scanning code allocates a new string and feeds it characters from the iterator:

fn scan_number(&mut self) -> Token {
    let startpos = self.ci;
    Token {
        value: TokenValue::Number(self.scan_while_true(|c| c.is_digit(10))),
        pos: startpos,
    }
}

// Helper to scan chars while `pred(c)` returns true, into the given `s`.
fn scan_while_true_into<F>(&mut self, s: &mut String, pred: F)
where
    F: Fn(char) -> bool,
{
    while pred(self.c) {
        s.push(self.c);
        self.scan_char();
    }
}

// Helper to scan chars while `pred(c)` returns true and return all scanned
// chars in a new String.
fn scan_while_true<F>(&mut self, pred: F) -> String
where
    F: Fn(char) -> bool,
{
    let mut s = String::with_capacity(8);
    self.scan_while_true_into(&mut s, pred);
    s
}

Costs of Allocation

Initially, this variant was about 30% slower than Go's string-copying version. The cause seems to be the approach: Go determines token boundaries with integer indices and does a single conversion from a byte slice to a string, while the Rust code builds strings by pulling chars one at a time from an iterator. Dynamically grown Strings can also trigger reallocations along the way.

The fix was to allocate with with_capacity, as seen above. That brought runtime roughly level with Go's copy-heavy path.

Which API Wins

The slice-based API is clearly the better design, for several reasons:

1. Performance. Zero-copy access means no extra heap allocations, just slice headers pointing into the input.
2. Clear ownership. The 'source lifetime governs both input and output. Whoever creates the lexer controls the lifetime of everything that flows through it — a symmetry that's easy to reason about.
3. No forced allocation. Good API design doesn't force callers to pay for copies they may not need. With the slice API, a caller who wants an owned string can call to_owned; with the owning API, they can't opt out of the allocation.

Dropping Peekable

After publication, a reader suggested that Peekable wasn't optimal — its next method is slower than that of the underlying iterator, and it sits on the hot path. Instead, the iterator can be cloned when a / is seen; iterators are small, so cloning is cheap.

Applying that patch made the lexer roughly 11% faster, finishing the benchmark in about 3.4 ms. It's a bit disappointing that Peekable doesn't live up to Rust's zero-cost abstraction ideal here, but this may improve in the future.