8 ms·

Strategies for Fast Lexers

180 points by xnacly 1y ago

skeptrune 1y ago
I really appreciate the commitment to bench-marking in this one. The memoization speedup for number processing was particularly surprising.
- felineflock 1y ago
  Are you referring to the part where he said "crazy 15ms/64% faster" ?
duped 1y ago
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.
- xnacly 1y ago
  Sadly that was one of the things I did benchmark, but didn't write down the results. I read a lot that naive switch is faster because the compiler knows how to optimise them better, but for my architecture and benchmarks the computed gotos were faster
cratermoon 1y ago
... written in C. Not sure how many of these translate to other languages.
- xnacly 1y ago
  Most of them, jump tables work in rust, mmapping too. deferred numeric parsing, keeping allocations to a minimum, string slices, interning and inline hashing all work in rust, go, c, c++; you name it.
thechao 1y ago
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.
- tempodox 1y ago
  The tragic thing is that you can't do `fgetwc()` on a `FILE *` produced by `fopencookie()` on Linux. glibc will crash your program deliberately as soon as there is a non-ASCII char in that stream (because, reasons?). But it does work with `funopen()` on a BSD, like macOS. I'm using that to read wide characters from UTF-8 streams.
  - o11c 1y ago
    Wide characters are best avoided even on platforms where it doesn't mean UTF-16. It's better to stay in UTF-8 mode, and only verify that it's well-formed.
    - tempodox 1y ago
ummonk 1y ago
Wait do modern compilers not use jump tables for large switch statements?
- packetlost 1y ago
  Some definitely do.
skybrian 1y ago
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.
- xnacly 1y ago
  I havent written a lot, but it needs to be fast so i can be motivated to program more by the fast iteration
sparkie 1y ago
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. You'd replace the JUMP_TARGET macro: #define JUMP_TARGET goto *jump_table[(int32_t)l->input.p[l->pos]] With: #ifdef __clang__ #define musttail [[clang::musttail]] #elif __GNUC__ #define musttail [[gnu::musttail]] #else #define musttail #endif #define JUMP_TARGET return musttail jump_table[(int32_t)l->input.p[l->pos]](l, a, out) Then move the jump table out to the top level and replace each `&&` with `&`. See diff (untested): https://www.diffchecker.com/V4yH3EyF/ 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.
- bestouff 1y ago
  Can't wait for mandatory TCO coming to Rust. But it's not there yet. https://github.com/phi-go/rfcs/blob/guaranteed-tco/text/0000-explicit-tail-calls.md https://github.com/phi-go/rfcs/blob/guaranteed-tco/text/0000...
  - sparkie 1y ago
    Not sure I like the `become` keyword. Seems bizarre - someone encountering this word in code for the first time would have no idea what it's doing. Why don't they just use `tailcall`? That would make it's obvious what it's doing because we've been using the term for nearly half a century, and the entire literature on the subject uses the term "tail call". Even better would be to just automatically insert a tail call - like every other language that has supported tail calls for decades - provided the callee has the same signature as the caller. If it's undesirable because we want a stack trace, then instead have some keyword or attribute to suppress the tail call - such as `no_tail`, `nontail` or `donttail`. Requiring tail calls to be marked will basically mean the optimization will be underutilized. Other than having a stack trace for debugging, there's basically no reason not to have the optimization on by default.
norir 1y ago
Lexing being the major performance bottleneck in a compiler is a great problem to have.
- norskeld 1y ago
  Is lexing ever a bottleneck though? Even if you push for lexing and parsing 10M lines/second [1], I'd argue that semantic analysis and codegen (for AOT-compiled languages) will dominate the timings. That said, there's no reason not to squeeze every bit of performance out of it! [1]: In this talk about the Carbon language, Chandler Carruth shows and explains some goals/challenges regarding performance: https://youtu.be/ZI198eFghJk?t=1462 https://youtu.be/ZI198eFghJk?t=1462
  - munificent 1y ago
    It depends a lot on the language. For a statically typed language, it's very unlikely that the lexer shows up as a bottleneck. Compilation time will likely be dominated by semantic analysis, type checking, and code generation. For a dynamically typed language where there isn't as much for the compiler to do, then the lexer might be a more noticeable chunk of compile times. As one of the V8 folks pointed out to me years ago, the lexer is the only part of the compiler that has to operate on every single individual byte of input. Everything else gets the luxury of greater granularity, so the lexer can be worth optimizing.
    - norskeld 1y ago
      Ah, yes, that's totally fair. In case of JS (in browsers) it's sort of a big deal, I suppose, even if scripts being loaded are not render-blocking: the faster you lex and parse source files, the faster page becomes interactive. P.S. I absolutely loved "Crafting Interpreters" — thank you so much for writing it!
  - SnowflakeOnIce 1y ago
    A simple hello world in C++ can pull in dozens of megabytes of header files. Years back I worked at a C++ shop with a big codebase (hundreds of millions of LOC when you included vendored dependencies). Compile times there were sometimes dominated by parsing speed! Now, I don't remember the exact breakdown of lexing vs parsing, but I did look at it under a profiler. It's very easy in C++ projects to structure your code such that you inadvertently cause hundreds of megabytes of sources to be parsed by each single #include. In such a case, lexing and parsing costs can dominate build times. Precompiled headers help, but not enough...
zX41ZdbW 1y ago
I recommend taking a look at the ClickHouse SQL Lexer: https://github.com/ClickHouse/ClickHouse/blob/master/src/Parsers/Lexer.h https://github.com/ClickHouse/ClickHouse/blob/master/src/Par... https://github.com/ClickHouse/ClickHouse/blob/master/src/Parsers/Lexer.cpp 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).
- tuveson 1y ago
  How much of an improvement does SIMD offer for something like this? It looks like it's only being used for strings and comments, but I would kind of assume that for most programming languages, the proportion of code that is long strings / comments is not large. Also curious if there's any performance penalty for trying to do SIMD if most of the comments and strings are short.
  - camel-cdr 1y ago
    Usually lexing isn't part of the performance equation compared to all other parts of the compiler, but SIMD can be used to speedup the number parsing.
  - Sesse__ 1y ago
    Random data point: Implementing SIMD for tokenizing identifiers sped up the Chromium CSS parser (as a whole, not just the tokenizer) by ~2–3%.
o11c 1y ago
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?!?
- dist1ll 1y ago
  You can get pretty far with a branch per byte, as long as the bulk of the work is done w/ SIMD (like character classification). But yeah, LUT lookup per byte is not recommended.
- xnacly 1y ago
  You are somewhat right, I used tagging masks to differntiate between different types of atoms [1]. But yes, interning will be backed by a correct implementation of a hashmap with some collision handling in the future. [1]: https://github.com/xNaCly/purple-garden/blob/master/cc.c#L76-L128 https://github.com/xNaCly/purple-garden/blob/master/cc.c#L76...
- kingstnap 1y ago
  You can go pretty far processing one byte at a time in hardware. You just keep making the pipeline deeper and pushing the frequency. And then to combat dependent parsing you add speculative execution to avoid bubbles. Eventually you land on recreating the modern cpu.
adev_ 1y ago
Cool exercise and thank you for the blog post. 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.
JonChesterfield 1y ago
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.
zahlman 1y ago
Is lexing really ever the bottleneck? Why focus effort here?
s3graham 1y ago
simdjson is another project to look at for ideas. 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).
psanchez 1y ago
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. It was a fun project.
aappleby 1y ago
Lexing is almost never a bottleneck. I'd much rather see a "Strategies for Readable Lexers".
kklisura 1y ago
> 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. [1] https://github.com/postgres/postgres/blob/master/src/tools/PerfectHash.pm https://github.com/postgres/postgres/blob/master/src/tools/P... [2] https://github.com/postgres/postgres/blob/master/src/tools/gen_keywordlist.pl https://github.com/postgres/postgres/blob/master/src/tools/g... [3] https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function
socalgal2 1y ago
I'm sorry I only skimmed but, how to do report line,col numbers for errors?
- pkaye 1y ago
  What I've done in my own implementation is include the line and column number in the token.
  - socalgal2 1y ago
    Yea, that's what I assumed too but the article didn't include them and I assumed it was for speed reasons. I've run into this often where some idealized version doesn't take into account usage ergonomics. A compiler that can't tell me where an error is is not a useful compiler to me so if this lexer doesn't support that then it won't actually be a net positive in development speed for me. I fail compilation more often than I succeed.
anonymoushn 1y ago
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.
userbinator 1y ago
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.
- teo_zero 1y ago
  But the compiler will always add the jump back to the top of the loop, so it's two jumps per cycle. Manual dispatch is one jump per cycle.
ptspts 1y ago
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.
sixthDot 1y ago
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.

180 points by xnacly 1y ago

I really appreciate the commitment to bench-marking in this one. The memoization speedup for number processing was particularly surprising.

felineflock 1y ago
Are you referring to the part where he said "crazy 15ms/64% faster" ?

duped 1y ago

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.

xnacly 1y ago
Sadly that was one of the things I did benchmark, but didn't write down the results. I read a lot that naive switch is faster because the compiler knows how to optimise them better, but for my architecture and benchmarks the computed gotos were faster

cratermoon 1y ago

... written in C. Not sure how many of these translate to other languages.

xnacly 1y ago
Most of them, jump tables work in rust, mmapping too. deferred numeric parsing, keeping allocations to a minimum, string slices, interning and inline hashing all work in rust, go, c, c++; you name it.

thechao 1y ago

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.

tempodox 1y ago
The tragic thing is that you can't do `fgetwc()` on a `FILE *` produced by `fopencookie()` on Linux. glibc will crash your program deliberately as soon as there is a non-ASCII char in that stream (because, reasons?). But it does work with `funopen()` on a BSD, like macOS. I'm using that to read wide characters from UTF-8 streams.
- o11c 1y ago
  Wide characters are best avoided even on platforms where it doesn't mean UTF-16. It's better to stay in UTF-8 mode, and only verify that it's well-formed.
  - tempodox 1y ago

ummonk 1y ago

Wait do modern compilers not use jump tables for large switch statements?

packetlost 1y ago
Some definitely do.

skybrian 1y ago

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.

xnacly 1y ago
I havent written a lot, but it needs to be fast so i can be motivated to program more by the fast iteration

sparkie 1y ago

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. You'd replace the JUMP_TARGET macro: #define JUMP_TARGET goto *jump_table[(int32_t)l->input.p[l->pos]] With: #ifdef __clang__ #define musttail [[clang::musttail]] #elif __GNUC__ #define musttail [[gnu::musttail]] #else #define musttail #endif #define JUMP_TARGET return musttail jump_table[(int32_t)l->input.p[l->pos]](l, a, out) Then move the jump table out to the top level and replace each `&&` with `&`. See diff (untested): https://www.diffchecker.com/V4yH3EyF/ 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.

bestouff 1y ago
Can't wait for mandatory TCO coming to Rust. But it's not there yet. https://github.com/phi-go/rfcs/blob/guaranteed-tco/text/0000-explicit-tail-calls.md https://github.com/phi-go/rfcs/blob/guaranteed-tco/text/0000...
- sparkie 1y ago
  Not sure I like the `become` keyword. Seems bizarre - someone encountering this word in code for the first time would have no idea what it's doing. Why don't they just use `tailcall`? That would make it's obvious what it's doing because we've been using the term for nearly half a century, and the entire literature on the subject uses the term "tail call". Even better would be to just automatically insert a tail call - like every other language that has supported tail calls for decades - provided the callee has the same signature as the caller. If it's undesirable because we want a stack trace, then instead have some keyword or attribute to suppress the tail call - such as `no_tail`, `nontail` or `donttail`. Requiring tail calls to be marked will basically mean the optimization will be underutilized. Other than having a stack trace for debugging, there's basically no reason not to have the optimization on by default.

norir 1y ago

Lexing being the major performance bottleneck in a compiler is a great problem to have.

norskeld 1y ago
Is lexing ever a bottleneck though? Even if you push for lexing and parsing 10M lines/second [1], I'd argue that semantic analysis and codegen (for AOT-compiled languages) will dominate the timings. That said, there's no reason not to squeeze every bit of performance out of it! [1]: In this talk about the Carbon language, Chandler Carruth shows and explains some goals/challenges regarding performance: https://youtu.be/ZI198eFghJk?t=1462 https://youtu.be/ZI198eFghJk?t=1462
- munificent 1y ago
  It depends a lot on the language. For a statically typed language, it's very unlikely that the lexer shows up as a bottleneck. Compilation time will likely be dominated by semantic analysis, type checking, and code generation. For a dynamically typed language where there isn't as much for the compiler to do, then the lexer might be a more noticeable chunk of compile times. As one of the V8 folks pointed out to me years ago, the lexer is the only part of the compiler that has to operate on every single individual byte of input. Everything else gets the luxury of greater granularity, so the lexer can be worth optimizing.
  - norskeld 1y ago
    Ah, yes, that's totally fair. In case of JS (in browsers) it's sort of a big deal, I suppose, even if scripts being loaded are not render-blocking: the faster you lex and parse source files, the faster page becomes interactive. P.S. I absolutely loved "Crafting Interpreters" — thank you so much for writing it!
- SnowflakeOnIce 1y ago
  A simple hello world in C++ can pull in dozens of megabytes of header files. Years back I worked at a C++ shop with a big codebase (hundreds of millions of LOC when you included vendored dependencies). Compile times there were sometimes dominated by parsing speed! Now, I don't remember the exact breakdown of lexing vs parsing, but I did look at it under a profiler. It's very easy in C++ projects to structure your code such that you inadvertently cause hundreds of megabytes of sources to be parsed by each single #include. In such a case, lexing and parsing costs can dominate build times. Precompiled headers help, but not enough...

zX41ZdbW 1y ago

I recommend taking a look at the ClickHouse SQL Lexer: https://github.com/ClickHouse/ClickHouse/blob/master/src/Parsers/Lexer.h https://github.com/ClickHouse/ClickHouse/blob/master/src/Par... https://github.com/ClickHouse/ClickHouse/blob/master/src/Parsers/Lexer.cpp 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).

tuveson 1y ago
How much of an improvement does SIMD offer for something like this? It looks like it's only being used for strings and comments, but I would kind of assume that for most programming languages, the proportion of code that is long strings / comments is not large. Also curious if there's any performance penalty for trying to do SIMD if most of the comments and strings are short.
- camel-cdr 1y ago
  Usually lexing isn't part of the performance equation compared to all other parts of the compiler, but SIMD can be used to speedup the number parsing.
- Sesse__ 1y ago
  Random data point: Implementing SIMD for tokenizing identifiers sped up the Chromium CSS parser (as a whole, not just the tokenizer) by ~2–3%.

o11c 1y ago

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?!?

dist1ll 1y ago
You can get pretty far with a branch per byte, as long as the bulk of the work is done w/ SIMD (like character classification). But yeah, LUT lookup per byte is not recommended.
xnacly 1y ago
You are somewhat right, I used tagging masks to differntiate between different types of atoms [1]. But yes, interning will be backed by a correct implementation of a hashmap with some collision handling in the future. [1]: https://github.com/xNaCly/purple-garden/blob/master/cc.c#L76-L128 https://github.com/xNaCly/purple-garden/blob/master/cc.c#L76...
kingstnap 1y ago
You can go pretty far processing one byte at a time in hardware. You just keep making the pipeline deeper and pushing the frequency. And then to combat dependent parsing you add speculative execution to avoid bubbles. Eventually you land on recreating the modern cpu.

adev_ 1y ago

Cool exercise and thank you for the blog post. 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.

JonChesterfield 1y ago

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.

zahlman 1y ago

Is lexing really ever the bottleneck? Why focus effort here?

s3graham 1y ago

simdjson is another project to look at for ideas. 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).

psanchez 1y ago

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. It was a fun project.

aappleby 1y ago

Lexing is almost never a bottleneck. I'd much rather see a "Strategies for Readable Lexers".

kklisura 1y ago

> 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. [1] https://github.com/postgres/postgres/blob/master/src/tools/PerfectHash.pm https://github.com/postgres/postgres/blob/master/src/tools/P... [2] https://github.com/postgres/postgres/blob/master/src/tools/gen_keywordlist.pl https://github.com/postgres/postgres/blob/master/src/tools/g... [3] https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function

socalgal2 1y ago

I'm sorry I only skimmed but, how to do report line,col numbers for errors?

pkaye 1y ago
What I've done in my own implementation is include the line and column number in the token.
- socalgal2 1y ago
  Yea, that's what I assumed too but the article didn't include them and I assumed it was for speed reasons. I've run into this often where some idealized version doesn't take into account usage ergonomics. A compiler that can't tell me where an error is is not a useful compiler to me so if this lexer doesn't support that then it won't actually be a net positive in development speed for me. I fail compilation more often than I succeed.

anonymoushn 1y ago

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.

userbinator 1y ago

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.

teo_zero 1y ago
But the compiler will always add the jump back to the top of the loop, so it's two jumps per cycle. Manual dispatch is one jump per cycle.

ptspts 1y ago

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.

sixthDot 1y ago

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.