I'm still obsessing about that one. If you read a byte, there's one or two unlikely branches and then a tail call to one of up to 256 distinct subsequent states

I'm still obsessing about that one. If you read a byte, there's one or two unlikely branches and then a tail call to one of up to 256 distinct subsequent states (or equivalently a read of a table of size up to 256). If you read two bytes, up to 64k subsequent states. 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.