quick-lint-js icon indicating copy to clipboard operation
quick-lint-js copied to clipboard

12$: Optimize SIMD bitset iteration

Open strager opened this issue 3 years ago • 1 comments

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/

strager avatar Jul 24 '22 02:07 strager

Roughly:

  1. If the mask is 0, exit.
  2. Use countr_zero to locate the right-most 1.
  3. Yield the bit.
  4. Update the mask: mask = mask & (mask - 1);
  5. Go to step 1.

(and we'd need to keep track of the index)

strager avatar Jul 24 '22 03:07 strager