State machines are great for complex situations, but when it comes to performance, it's not at all clear to me that they're the most scalable approach with modern systems.
The data dependency between a loop iteration for each character might be pipelined really well when executed, and we can assume large enough L1/L2 cache for our lookup tables. But we're still using at least one lookup per character.
Projects like https://github.com/simdjson/simdjson?tab=readme-ov-file#abou... are truly fascinating, because they're based on SIMD instructions that can process 64 or more bytes with a single instruction. Very much worth checking out the papers at that link.
In the context of State Machines and Automatas - Intel HyperScan might be a better reference point. But the idea is the same. With a trivial PoC using Python wrappers over SIMD libraries one can get a 3x boost over the native `wc` CLI on a modern CPU, memory-mapping a very average SSD: https://github.com/ashvardanian/StringZilla/tree/main/cli
My understanding of the article's use of scalable was "fixed overhead more or less regardless of the complexity of the state machine and input" not "fastest implementation available"
The data dependency between a loop iteration for each character might be pipelined really well when executed, and we can assume large enough L1/L2 cache for our lookup tables. But we're still using at least one lookup per character.
Projects like https://github.com/simdjson/simdjson?tab=readme-ov-file#abou... are truly fascinating, because they're based on SIMD instructions that can process 64 or more bytes with a single instruction. Very much worth checking out the papers at that link.