lexer for programming languages in rust

Question

I'm relatively new to rust, so you don't need to go easy on the criticism.

right now, this lexes 1MB of text (well, trims a 1MB-long word) in 30ms. is there any way I can make this faster?

cursor.rs:

use std::str::Chars;

#[derive(Debug)]
pub struct Cursor<'a> {
    peek: Option<char>,
    pub chars: Chars<'a>,
    pub pos: usize,
    pub row: usize,
    pub col: usize
}

impl<'a> Cursor<'a> {
    pub fn new(text: &'a str) -> Self {
        let mut chars = text.chars();
        Self {
            peek: chars.next(),
            chars,
            pos: 0,
            row: 1,
            col: 0,
        }
    }

    pub fn next(&mut self) -> Option<char> {
        let peek = self.peek?;
        if peek == '\n' {
            self.col = 1;
            self.row += 1;
        } else {
            self.col += 1;
        }
        self.pos += peek.len_utf8();
        self.peek = self.chars.next();
        Some(peek)
    }

    pub fn peek_is<F: FnOnce(char) -> bool>(&mut self, fun: F) -> bool {
        self.peek.map_or(false, fun)
    }

    #[inline]
    pub fn peeking(&mut self, ch: char) -> bool {
        self.peek == Some(ch)
    }

    pub fn next_if<F: FnOnce(char) -> bool>(&mut self, fun: F) -> Option<char> {
        if self.peek_is(fun) {
            self.next()
        } else {
            None
        }
    }
}

lexer.rs:

use crate::cursor::Cursor;

pub enum TokenKind<'a> {
    Ident(&'a str),
    Num(&'a str),
    Str(String)
}

pub struct Lexer<'a> {
    text: &'a str,
    pub cursor: Cursor<'a>
}

impl<'a> Lexer<'a> {
    pub fn new<T: Into<&'a str>>(text: T) -> Self {
        let text = text.into();
        Self {
            text,
            cursor: Cursor::new(text)
        }
    }

    #[inline]
    pub fn token<F: FnOnce(char) -> bool + Copy>(&mut self, fun: F) -> &'a str {
        let pos = self.cursor.pos;
        while self.cursor.peek_is(fun) {
            self.cursor.next();
        }
        &self.text[pos..self.cursor.pos]
    }

    pub fn trim_ident(&mut self) -> &'a str {
        self.token(|x| x.is_alphanumeric() || x == '_')
    }

    pub fn trim_integer(&mut self) -> &'a str {
        self.token(char::is_numeric)
    }
}

// impl<'a> Iterator for Lexer<'a> {
//     type Item = TokenKind<'a>;
//
//     fn next(&mut self) -> Option<TokenKind<'a>> {
//         todo!()
//     }
// }

lib.rs:

#![allow(unused)]

pub mod cursor;
pub mod lexer;
pub use lexer::*;

#[cfg(test)]
mod tests {
    use super::*;
}

main.rs:

use scanner_rs::*;

macro_rules! time {
    ($name:literal, $($test:tt)*) => {
        {
            let start = std::time::Instant::now();
            $($test)*
            println!("{}: {:?}", $name, start.elapsed());
        }
    }
}

fn main() {
    let code = "H".repeat(104_857_6);
    let mut test_time = Lexer::new(&*code);
    time! {
        "init",
        Lexer::new(&*code);
    };
    time! {
        "next",
        lexer.cursor.next();
    };
    time! {
        "ident",
        println!("{}", lexer.trim_ident()); // HHHHHHHHHHHH...
    };
    let mut hello_world = Lexer::new("Hello");
    println!("{}", lexer.trim_ident()); // Hello
}

Answer 1

Let's focus on performance, with general principles first.

Memory Allocations

You did well using an iterator over str, rather than allocating a Vec<char>. This avoids memory allocations, and that's generally a good thing.

On the other hand, your plan to use a String is TokenKind is not great. It would be better to just use a slice. If you plan to have potentially escaped characters, you can just add a variant for string-without-escaped-characters and string-with-escaped-characters. The goal is to defer the memory allocation as long as possible, and if possible to eschew it at the end too.

char is problematic.

From a pure performance point of view, char is fairly problematic. It may be necessary, mind, but it still is problematic.

The problem is that you turn a byte into a char, then query the char, and go back to the byte. From a performance point of view, you'd be better off operating on bytes altogether... although if you want to support Unicode it'll definitely makes things a tad harder.

Byte-wise segmentation is slow by design

Your algorithm is, at its core, operating one byte at a time. That is far from ideal.

The throughput of a lexer is typically expressed as the number of cycles it takes per byte, and the lower the better. You can try to fine-tune the operations performed on each byte to minimize this measure... but that's ignoring two important aspects of the CPU:

• ILP: Instruction Level Parallelism, which consists in performing multiple instructions "in parallel".
• SIMD: Same Instruction Multiple Data, which consists in performing a single instructions on multiple elements at once.

At the moment, a compiler may be able to turn your byte-by-byte algorithm into a vectorized version, or to unlock some ILP, but there are limits to the magic that a compiler is able to perform, and the char intermediary step is making your compiler's life difficult in the first place.

Back to the drawing board

What are you trying to do here? Lex a piece of code.

Code typically looks like:

• 3 * 4
• object.method(item, expr + ession)

If you look closely, you'll realize that you have roughly 3 or 4 categories of characters:

• Identifiers & numbers.
• "Operators" & braces -- aka separators.
• Whitespace.

This is because you can view tokenization as a two-steps processes: Segmentation and Classification.

It's common for text-book lexers to mix the two together: peek at the first non-whitespace character, then parse a number/identifier/... based on it. It's simple, but not necessarily efficient.

If you split the process, you can first segment and then classify. And that's much more mechanically sympathetic.

So, taking object.method(item, expr + ession):

• Segmentation is about splitting into object, ., method, (, item, ,, expr, +, ession, and ).
• Classification is about assigning the kind: object is an identifier, . is (here) a method/field separator, ...

There's two difficulties here:

• Floating point numbers, and their pesky . and - in the middle of those numbers. The tokens can be reassembled in the parsing stage, or in an intermediate stage.
• Strings and comments, which require a "mode switch" regardless.

Fortunately, they are quite rarer than regular tokens.

Implementation-wise, the idea is to use an iterator on chunks of bytes and "mark" each as "identifier-like", whitespace, and other (operator, brace, quote, ...). Chunks of 64 bytes are great because u64 is native on most architectures, even if 16-bytes or 32-bytes SIMD operations need to be used. On the u64, you'll be looking at operations identifying the next set/unset bit, which in Rust are leading_zeros, leading_ones or trailing_zeros, trailing_ones depending on the way you compose the mask.