quick-lint-js
quick-lint-js copied to clipboard
12$: Optimize SIMD bitset iteration
Block comment parsing uses a SIMD register. It iterates over each true in the register:
https://github.com/quick-lint/quick-lint-js/blob/bd583a1b34bfa557c99477551af68525d8e77cc2/src/quick-lint-js/fe/lex.cpp#L1942-L1945
We can adapt Kernighan's popcount algorithm to speed up this up: https://www.techiedelight.com/brian-kernighans-algorithm-count-set-bits-integer/
Roughly:
- If the mask is 0, exit.
- Use
countr_zeroto locate the right-most1. - Yield the bit.
- Update the mask:
mask = mask & (mask - 1); - Go to step 1.
(and we'd need to keep track of the index)