When writing an interpreter in Rust, does using Vec<char> or String for the scanner make a difference in terms of performance? Which one would be the better choice?
I'm a hobbyist programmer, and I've always been very interested in compilers. I want to dive deeper into this area as a hobby, so I started with Crafting Interpreters. Along the way, I've also gained a much better understanding of Rust's borrow checker and some other concepts.
My goal with Rust is to design a very minimal, interpreted, type-safe programming language focused solely on the backend. I'm not sure if it's necessary for this, but I've also decided to start studying mathematics from scratch for the project.
Any advantage you might possibly get from Vec<char> -- and TBH I don't even think there is one -- would be more than offset by the cost of converting your text into Vec<char> in the first place.
Just work on the UTF-8 directly. That's what regex does, and it's part of why it's so fast.
for a typical lexer, you mainly look for keywords, whitespaces, digits, and punctuations. keywords are fixed, and programming languages usually only uses ascii whitespaces, digts, and puncutations, these can all be efficiently implemented over the raw bytes of a utf8 string.
on the other hand, if, for some reason, you want to be fully unicode aware, then you'll have to work in grapheme clusters, a.k.a. user perceived "character"s, and Vec<char> (a sequence of codepoints) gives you no advantages over the utf8 encoding.
so either way, Vec<char> is a no go, just stick to String (or &'a str, if your source text is stored separately from the lexer/scanner itself).
Differently from other suggestions I propose to switch into char array or char iterator. Rust does not even allow integer indexing into strings, because the n'th char cannot be easily obtained without counting from beginning in UTF-8 string.
Regular expression crate is not so well implemented for Rust at the time of writing. It is slow and very heavy. It is okay if it solves the complete task but I would not recommend as a part of more complex parser.
This is why you either work on bytes or use a wrapper like:
fn next_char(&mut self) -> Option<char> {
let c = self.source[self.pos..].chars().next()?;
self.pos += c.len_utf8();
Some(c)
}
Edit: be aware this ends up generating quite a bit of code, though I'm not sure how much worse than "ideal" UTF-8 handling code would be. Directly handling bytes tends to "just work" most of the time with UTF-8, the only distinction is if you want to properly handle unicode identifiers really
In most languages, the characters with special meaning for the parser are part of ASCII. So your parser can easily operate on the bytes underlying the UTF-8 string (str.bytes()). For the functionality where accessing the actual string is useful (e.g. string literals), you can simply slice the string, since the offsets into the byte-slice and the string are the same.
So UTF-8 is generally the right representation. For some exotic languages, like APL, a different representation could make sense.
All APL symbols can be encoded in Unicode and hence in UTF-8. You can tokenize a multi-byte Unicode symbol encoded in UTF-8 just like you can tokenize a multi-character ASCII token (such as <<= in Rust): by matching the byte sequences.
Would you care to elaborate or do you have any data backing this claim? Slow in what way? Compile time? Search time? In the benchmarks I'm aware of, regex is regularly one, if not the fastest, search engine benchmarked:
Of course you can represent APL as UTF-8. But it's one of the few cases where I'd consider a different in-memory encoding (i.e. one byte per symbol). Though I guess, string literals ruin that approach, and make UTF-8 the best choice again.
I don't know much about this topic, so I may be misunderstanding things. I'm just sharing a beginner's thought based on what I've learned so far wouldn't a one-byte-per-symbol encoding become problematic if you wanted to support emojis or arbitrary Unicode characters in string literals? In that case, wouldn't you still need some form of UTF-8 for string contents?
Received a merge request to my project removing that crate. Build time reduction followed showing the crate was indeed heavy. It may be others are even worse.
The crate is heavy because the priorities are "correct unicode handlling" > "runtime performance" > "everything else" as described here in the readme.
However, it is fast for a regex engine. For cases like the one you linked manual code not only compiles faster but also has better runtime performance.
Just wanted to highlight because this is why working on the UTF-8 is fine. A lexer is just a finite automaton that goes through states. Matching the 3 bytes that make up a ∛ is no different from matching the 3 bytes that make up for.
Going to Vec<char> makes the ∛ be 1 char, but that doesn't really help since you still need to match the 3 chars for the for.
Or, more abstractly, the point of the lexer is to chunk things up into useful units for the parser. You don't need to chunk the bytes up into chars to then chunk them into real tokens.
You'd still use a string as input. But your parser would operate on s.as_bytes(). For a typical string literal, all the parser cares about are \ as escape and " as closing delimiter, all of which consist of a single byte. Then you can return a Cow<str> for the decoded string. If it didn't contain any escape sequences, you slice with s[start_index..end_index]. If it contains escape sequences, decode them and produce a string.
Another option that's sometimes nicer for highlighting or handling fancier escapes is to treat parsing a string as a parsing level issue, return "open string", any number of "raw string content" "string escape" tokens, then a "close string". That works a bit nicer with templates, too.
because this is why working on the UTF-8 is fine. A lexer is just a finite automaton that goes through states. Matching the 3 bytes that make up a