3 ms·

Without SIMD, that would probably the optimal way to implement it. And this bit vector idea really isn't doing SIMD at all, it's just (ab)using the vector regis

Without SIMD, that would probably the optimal way to implement it. And this bit vector idea really isn't doing SIMD at all, it's just (ab)using the vector registers to store 128 bits. I think the Zig code would also compile to better output, and be a lot simpler, if it was using an array of u1, instead of doing the bit shifting manually.

MobiusHorizons 2y ago
The bit vector does give a nice compression compared to the jump table. But I believe the main thing to do for speeding up string parsing is to consume more than one character at a time. I personally found the techniques in https://tia.mat.br/posts/2018/02/01/more_on_string_switch_in_c.html https://tia.mat.br/posts/2018/02/01/more_on_string_switch_in... very helpful to explain these issues. EDIT: I especially like this statement from the conclusion: > The good thing about the switch statement in C is that it is maybe the highest level statement in the language: the compiler can get really creative in how its code is generated. It's not uncommon for it to generate jump tables or even binary searches.
dragontamer 2y ago
Bit processing is always SIMD. A 64-bit register being processed 64-bits at a time is, from a mental and programmers perspective, a 64-wide SIMD computer over 1-bit AND, OR, and NOT instructions. If you aren't using SIMD / parallel programming concepts while thinking about 64-parallel bits (or even in this case, parallel processing of 8-bit bytes or 7-bits of ASCII), then you are making life much harder for yourself. ------- I believe in the 90s, some people called 32-bit parallelism as SIMD Within A Register (SWAR). Some guy wrote 3DES encryption with 64-bit AND/OR/NOTs and progressed bit-by-bit (but in parallel), achieving absurdly efficient encryption back in the day. And of course, Chess Programmers with all their 64-bit boards for their 8x8 game constantly think in terms of SIMD inside of 64-bits. ------- Once you learn to think in SIMD, you can extend these concepts out to 128-bits (SSE), 256-bits (AVX) or 512-bit (AVX512) or beyond (GPU 1024-bits and greater).
- selimthegrim 2y ago
  http://lamport.azurewebsites.net/pubs/multiple-byte.pdf http://lamport.azurewebsites.net/pubs/multiple-byte.pdf

MobiusHorizons 2y ago

The bit vector does give a nice compression compared to the jump table. But I believe the main thing to do for speeding up string parsing is to consume more than one character at a time. I personally found the techniques in https://tia.mat.br/posts/2018/02/01/more_on_string_switch_in_c.html https://tia.mat.br/posts/2018/02/01/more_on_string_switch_in... very helpful to explain these issues. EDIT: I especially like this statement from the conclusion: > The good thing about the switch statement in C is that it is maybe the highest level statement in the language: the compiler can get really creative in how its code is generated. It's not uncommon for it to generate jump tables or even binary searches.

dragontamer 2y ago

Bit processing is always SIMD. A 64-bit register being processed 64-bits at a time is, from a mental and programmers perspective, a 64-wide SIMD computer over 1-bit AND, OR, and NOT instructions. If you aren't using SIMD / parallel programming concepts while thinking about 64-parallel bits (or even in this case, parallel processing of 8-bit bytes or 7-bits of ASCII), then you are making life much harder for yourself. ------- I believe in the 90s, some people called 32-bit parallelism as SIMD Within A Register (SWAR). Some guy wrote 3DES encryption with 64-bit AND/OR/NOTs and progressed bit-by-bit (but in parallel), achieving absurdly efficient encryption back in the day. And of course, Chess Programmers with all their 64-bit boards for their 8x8 game constantly think in terms of SIMD inside of 64-bits. ------- Once you learn to think in SIMD, you can extend these concepts out to 128-bits (SSE), 256-bits (AVX) or 512-bit (AVX512) or beyond (GPU 1024-bits and greater).

selimthegrim 2y ago
http://lamport.azurewebsites.net/pubs/multiple-byte.pdf http://lamport.azurewebsites.net/pubs/multiple-byte.pdf