Do you have benchmarks that show the hand rolled jump table has a significant impact?
The only reason this raises an eyebrow is that I've seen conflicting anec/data on this, depending pretty hard on target microarchitecture and the program itself.
I like to have my lexers operate on `FILE*`, rather than string-views. This has some real-world performance implications (not good ones); but, it does mean I can operate on streams. If the user has a c-string, the string can be easily wrapped by `funopen()` or `fopencookie()` to provide a `FILE*` adapter layer. (Most of my lexers include one of these, out-of-the-box.)
Everything else, I stole from Bob Nystrom: I keep a local copy of the token's string in the token, aka, `char word[64]`. I try to minimize "decision making" during lexing. Really, at the consumption point we're only interested in an extremely small number of things: (1) does the lexeme start with a letter or a number?; (2) is it whitespace, and is that whitespace a new line?; or, (3) does it look like an operator?
The only place where I've ever considered goto-threading was in keyword identification. However, if your language keeps keywords to ≤ 8 bytes, you can just bake the keywords into `uint64_t`'s and compare against those values. You can do a crapload of 64b compares/ns.
The next level up (parsing) is slow enough to eat & memoize the decision making of the lexer; and, materially, it doesn't complicate the parser. (In fact: there's a lot of decision making that happens in the parser that'd have to be replicated in the lexer, otherwise.)
The result, overall, is you can have a pretty general-purpose lexer that you can reuse for a any old C-ish language, and tune to your heart's content, without needing a custom rewrite, each time.
This is fun and all, but I wonder what’s the largest program that’s ever been written in this new language (purple garden)? Seems like it will be a while before the optimizations pay off.
As an alternative to the computed gotos, you can use regular functions with the `[[musttail]]` attribute in Clang or GCC to achieve basically the same thing - the call in the tail position is replaced with a `jmp` instruction to the next function rather than to the label, and stack usage remains constant because the current frame is reutililzed for the called function. `musttail` requires that the calling function and callee have the same signature, and a prototype.
This approach has the advantage that it will work everywhere and not only on compilers that support the computed gotos - it just won't optimize it on compilers that don't support `musttail`. (Though it has been proposed to standardize it in a future version of C).
It might also work better with code navigation tools that show functions, but not labels, and enables modularity as we can split rules over multiple translation units.
Performance wise should basically be the same - though it's been argued that it may do better in some cases because the compiler's register allocator doesn't do a great job in large functions with computed gotos - whereas in musttail approach each function is a smaller unit and optimized separately.
Unfortunately, operating a byte at a time means there's a hard limit on performance.
A truly performant lexer needs to jump ahead as far as possible. This likely involves SIMD (or SWAR) since unfortunately the C library fails to provide most of the important interfaces.
As an example that the C library can handle tolerably, while lexing a string, you should repeatedly call `strcspn(input, "\"\\\n")` to skip over chunks of ordinary characters, then only special-case the quote, backslash, newline and (implicit!) NUL after each jump. Be sure to correctly distinguish between an embedded NUL and the one you probably append to represent EOF (or, if streaming [which requires quite a bit more logic], end of current chunk).
Unfortunately, there's a decent chance your implementation of `strcspn` doesn't optimize for the possibility of small sets, and instead constructs a full 256-bit bitset. And even if it does, this strategy won't work for larger sets such as "all characters in an identifier" (you'd actually use `strspn` since this is positive), for which you'll want to take advantage of the characters being adjacent.
Edit: yikes, is this using a hash without checking for collisions?!?
Byte at a time means not-fast but I suppose it's all relative. The benchmarks would benefit from a re2c version, I'd expect that to beat the computed goto one. Easier for the compiler to deal with, mostly.
I found it quite tricky to apply its ideas to the more general syntax for a programming language, but with a bunch of hacking and few subtle changes to the language itself, the performance difference over one-character-at-a-time was quite substantial (about 6-10x).
The jump table is interesting, although I guess the performance of switch will be similar if properly optimized with the compiler, but would not be able to tell without trying. Also different compilers might take different approaches.
A few months ago I built a toy boolean expression parser as a weekend project. The main goal was simple: evaluate an expression and return true or false. It supported basic types like int, float, string, arrays, variables, and even custom operators.
The syntax and grammar were intentionally kept simple. I wanted the whole implementation to be self-contained and compact, something that could live in just a .h and .cc file. Single pass for lexing, parsing, and evaluation.
After having the first version working, I kind of challenged myself to make it faster and tried many things.
Once the first version was functional, I challenged myself to optimize it for speed. Here are some of the performance-related tricks I remember using:
- No string allocations: used the input *str directly, relying on pointer manipulation instead of allocating memory for substrings.
- Stateful parsing: maintained a parsing state structure passed by reference to avoid unnecessary copies or allocations.
- Minimized allocations: tried to avoid heap allocations wherever possible. Some were unavoidable during evaluation, but I kept them to a minimum.
- Branch prediction-friendly design: used lookup tables to assist with token identification (mapping the first character to token type and validating identifier characters).
- Inline literal parsing: converted integer and float literals to their native values directly during lexing instead of deferring conversion to a later phase.
I think all the tricks are mentioned in the article already.
For what is worth, here is the project:
https://github.com/pausan/tinyrulechecker
I used this expression to assess the performance on an Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz (launched Q3 2018):
myfloat.eq(1.9999999) || myint.eq(32)
I know it is a simple expression and likely a larger expression would perform worse due to variables lookups, ... I could get a speed of 287MB/s or 142ns per evaluation (7M evaluations per second). I was gladly surprised to reach those speeds given that 1 evaluation is a full cycle of lexing, parsing and evaluating the expression itself.
The next step I thought was also to use SIMD for tokenizing, but not sure it would have helped a lot on the overall expression evaluation times, I seem to recall most of the time was spent on the parser or evaluation phases anyway, not the lexer.
> As introduced in the previous chapters, all identifers are hashed, thus we can also hash the known keywords at startup and make comparing them very fast.
One trick that postgres uses [1][2] is perfect hashing [3]. Since you know in advance what your keywords are, you can design such hashing functions that for each w(i) in list of i keywords W, h(w(i)) = i. It essentially means no collisions and it's O(i) for the memory requirement.
Well, when it's this fast already, there may not be much point in vectorizing it.
For integer parsing, this is a pretty cheap operation, so I wonder if it is worthwhile to try to avoid doing it many times. For double parsing, it is expensive if you require the bottom couple bits to be correct, so the approach in the blog post should create savings.
Replacing the switch with an array index and a jump.
Compilers will compile switches to a branch tree, two-level jump table, or single-level jump table depending on density and optimisation options. If manually using a jump table is faster, you either have a terrible compiler or just haven't explored its optimisation settings enough.
The Str_to_double code in the article produces inaccurate results in the last few bits. (What is the use of parsing a double inaccurately?) Accurate parsing of a double is really tricky (and memory-hungry and slow). The strtod(3) function provided by a decent libc (such as glibc and musl, and also the FreeBSD libc) can do it correctly.
A problem I see with talking exclusively about lexing is that when you separate lexing from parsing you miss the point that is that a lexer is an iterator consumed by the parser.
24 comments
[ 3.2 ms ] story [ 33.4 ms ] threadThe only reason this raises an eyebrow is that I've seen conflicting anec/data on this, depending pretty hard on target microarchitecture and the program itself.
Not sure how many of these translate to other languages.
Everything else, I stole from Bob Nystrom: I keep a local copy of the token's string in the token, aka, `char word[64]`. I try to minimize "decision making" during lexing. Really, at the consumption point we're only interested in an extremely small number of things: (1) does the lexeme start with a letter or a number?; (2) is it whitespace, and is that whitespace a new line?; or, (3) does it look like an operator?
The only place where I've ever considered goto-threading was in keyword identification. However, if your language keeps keywords to ≤ 8 bytes, you can just bake the keywords into `uint64_t`'s and compare against those values. You can do a crapload of 64b compares/ns.
The next level up (parsing) is slow enough to eat & memoize the decision making of the lexer; and, materially, it doesn't complicate the parser. (In fact: there's a lot of decision making that happens in the parser that'd have to be replicated in the lexer, otherwise.)
The result, overall, is you can have a pretty general-purpose lexer that you can reuse for a any old C-ish language, and tune to your heart's content, without needing a custom rewrite, each time.
You'd replace the JUMP_TARGET macro:
With: Then move the jump table out to the top level and replace each `&&` with `&`.See diff (untested): https://www.diffchecker.com/V4yH3EyF/
This approach has the advantage that it will work everywhere and not only on compilers that support the computed gotos - it just won't optimize it on compilers that don't support `musttail`. (Though it has been proposed to standardize it in a future version of C).
It might also work better with code navigation tools that show functions, but not labels, and enables modularity as we can split rules over multiple translation units.
Performance wise should basically be the same - though it's been argued that it may do better in some cases because the compiler's register allocator doesn't do a great job in large functions with computed gotos - whereas in musttail approach each function is a smaller unit and optimized separately.
I was excited when it was introduced but quickly ran into issues.
Here is a silent miscompilation involving `[[musttail]]` that I reported in 2022 and is still open: https://github.com/llvm/llvm-project/issues/56435
https://github.com/ClickHouse/ClickHouse/blob/master/src/Par...
https://github.com/ClickHouse/ClickHouse/blob/master/src/Par...
It supports SIMD for accelerated character matching, it does not do any allocations, and it is very small (compiles to a few KB of WASM code).
A truly performant lexer needs to jump ahead as far as possible. This likely involves SIMD (or SWAR) since unfortunately the C library fails to provide most of the important interfaces.
As an example that the C library can handle tolerably, while lexing a string, you should repeatedly call `strcspn(input, "\"\\\n")` to skip over chunks of ordinary characters, then only special-case the quote, backslash, newline and (implicit!) NUL after each jump. Be sure to correctly distinguish between an embedded NUL and the one you probably append to represent EOF (or, if streaming [which requires quite a bit more logic], end of current chunk).
Unfortunately, there's a decent chance your implementation of `strcspn` doesn't optimize for the possibility of small sets, and instead constructs a full 256-bit bitset. And even if it does, this strategy won't work for larger sets such as "all characters in an identifier" (you'd actually use `strspn` since this is positive), for which you'll want to take advantage of the characters being adjacent.
Edit: yikes, is this using a hash without checking for collisions?!?
I did a similar thing (for fun) for the tokenizer associated to a Swift derivates language written in C++.
My approach was however very different of yours:
- No macro, no ASM, just explicit vectorization using std.simd
- No hand rolled allocator. Just std::vector and SOA.
- No hashing for keyword. They are short. A single SIMD load / compare is often enough for a comparison
- All the lookup tables are compile time generated from the token list using constexpr to keep the code small and maintainable.
I was able to reach around 8 Mloc/s on server grade hardware, single core.
I found it quite tricky to apply its ideas to the more general syntax for a programming language, but with a bunch of hacking and few subtle changes to the language itself, the performance difference over one-character-at-a-time was quite substantial (about 6-10x).
A few months ago I built a toy boolean expression parser as a weekend project. The main goal was simple: evaluate an expression and return true or false. It supported basic types like int, float, string, arrays, variables, and even custom operators.
The syntax and grammar were intentionally kept simple. I wanted the whole implementation to be self-contained and compact, something that could live in just a .h and .cc file. Single pass for lexing, parsing, and evaluation.
After having the first version working, I kind of challenged myself to make it faster and tried many things.
Once the first version was functional, I challenged myself to optimize it for speed. Here are some of the performance-related tricks I remember using:
I think all the tricks are mentioned in the article already.For what is worth, here is the project:
I used this expression to assess the performance on an Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz (launched Q3 2018): I know it is a simple expression and likely a larger expression would perform worse due to variables lookups, ... I could get a speed of 287MB/s or 142ns per evaluation (7M evaluations per second). I was gladly surprised to reach those speeds given that 1 evaluation is a full cycle of lexing, parsing and evaluating the expression itself.The next step I thought was also to use SIMD for tokenizing, but not sure it would have helped a lot on the overall expression evaluation times, I seem to recall most of the time was spent on the parser or evaluation phases anyway, not the lexer.
It was a fun project.
One trick that postgres uses [1][2] is perfect hashing [3]. Since you know in advance what your keywords are, you can design such hashing functions that for each w(i) in list of i keywords W, h(w(i)) = i. It essentially means no collisions and it's O(i) for the memory requirement.
[1] https://github.com/postgres/postgres/blob/master/src/tools/P...
[2] https://github.com/postgres/postgres/blob/master/src/tools/g...
[3] https://en.wikipedia.org/wiki/Perfect_hash_function
For integer parsing, this is a pretty cheap operation, so I wonder if it is worthwhile to try to avoid doing it many times. For double parsing, it is expensive if you require the bottom couple bits to be correct, so the approach in the blog post should create savings.
Compilers will compile switches to a branch tree, two-level jump table, or single-level jump table depending on density and optimisation options. If manually using a jump table is faster, you either have a terrible compiler or just haven't explored its optimisation settings enough.