4 ms·

> Probably read a byte of the input at a time. Which is an important bottleneck; SIMD-based lexers give you another order(s?) of magnitude of speed up. But wri

> Probably read a byte of the input at a time. 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.

JonChesterfield 2y ago
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.
10000truths 2y ago
That speedup is not unconditional. It only occurs in portions of the input string that don't trigger any state transitions. And the length of those portions has to be some reasonable multiple of the size of your vector register. What constitutes a state transition will depend highly on the structure of your input string and the information you wish to extract from it. As an example, if I want to build a nested array/map of things from this input JSON: {"a": "bcd", "ef": [{},{},{"a":12,"b":100},{"a":12,"b":100},{"a":12,"b":100}, ...]} SIMD will not provide an appreciable performance boost because the data type changes every few characters. There's no string or whitespace or number in that JSON that is large enough to speed up scanning.
hiccuphippo 2y ago
Here's a recent talk of someone experimenting with SIMD to optimize the Zig parser https://www.youtube.com/watch?v=FDiUKafPs0U https://www.youtube.com/watch?v=FDiUKafPs0U

JonChesterfield 2y ago

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.

10000truths 2y ago

That speedup is not unconditional. It only occurs in portions of the input string that don't trigger any state transitions. And the length of those portions has to be some reasonable multiple of the size of your vector register. What constitutes a state transition will depend highly on the structure of your input string and the information you wish to extract from it. As an example, if I want to build a nested array/map of things from this input JSON: {"a": "bcd", "ef": [{},{},{"a":12,"b":100},{"a":12,"b":100},{"a":12,"b":100}, ...]} SIMD will not provide an appreciable performance boost because the data type changes every few characters. There's no string or whitespace or number in that JSON that is large enough to speed up scanning.

hiccuphippo 2y ago

Here's a recent talk of someone experimenting with SIMD to optimize the Zig parser https://www.youtube.com/watch?v=FDiUKafPs0U https://www.youtube.com/watch?v=FDiUKafPs0U