Fast Tokenizers with StringScanner (2023)
tenderlovemaking.com
tenderlovemaking.com
A regex can be translated to a finite state machine. N regex can also be compiled to a (bigger) state machine. The longest-match-wins, ties go to the earlier regex lexer semantic needs a register/int value to track where the current favourite match ended and a second to track which regex matched. Can probably drop one of those registers if preferred.
That takes a pointer into your string, returns the index into your N regex or an indication of failure. Either it moves the pointer along or returns a length as well.
No dynamic allocation. Constant stack space. Couple of machine registers in the interface. Linear time through the input array (slightly handwaving that since some bytes get read multiple times to disambiguate which match is preferred, but it's bounded by a constant factor of the N regex).
Probably read a byte of the input at a time. The C output of re2c is especially clear for seeing why the compiled machine works.
A nice quirk of the above is equivalent regex turn into the same minimal state machine so it doesn't matter how the regex are written. Literals are the same performance as regex specifying that literal.
Which is an important bottleneck; SIMD-based lexers give you another order(s?) of magnitude of speed up. But writing it by hand is just... ugh. The guys behind simdjson did that but not everyone is as great at those things as they are.
I suspect that reading multiple bytes is faster when the number of distinct subsequent states is smallish, and reading one byte (or maybe even four bits) is faster if the number of distinct states is near the upper bound.
It's also relatively likely that optimal involves reading N bytes, where some out edges consume N and others consume fewer than N. E.g. check eight bytes in case they all match some literal sequence you're scanning for, but if they don't, branch on the first two bytes from that word.
This has really strong rabbit hole vibes to it. What exactly is the right cost model for the target architecture, how should one trade icache for dcache, can any of the branches realistically be predicted for the distribution of input data and so forth. Also how many cycles should go on perfect-hashing the input byte(s) before the transition.
But even if you stick with re2c style read-a-byte-then-switch, and compile with something that knows how to do tail calls for your architecture, the code is going to establish a pretty solid performance baseline. Quite a lot of mispredicted branches but no syscalls, no stack or heap usage.
{"a": "bcd", "ef": [{},{},{"a":12,"b":100},{"a":12,"b":100},{"a":12,"b":100}, ...]}
See for example: http://thingsaaronmade.com/blog/a-simple-intro-to-writing-a-...
Only because the escape sequence for a quote is \" instead of, say, \q. Then it'd have been a very straightforward regex "[^"]*" to match a string literal. On a slightly related note, having the escape sequence for a backslash to be \z or something like that instead of \\ mitigates the "leaning toothpick syndrome" quite a lot. Both of these choices are unpopular for no particular reason IMHO other than "it's different from what all the C-like languages do".