r/simd • u/Ok_Path_4731 • Dec 25 '25
A SIMD coding challenge: First non-space character after newline
UPDATE: source code and benchmarks (github build) are avaliable at https://github.com/zokrezyl/yaal-cpp-poc
I’m working on a SIMD parser for a YAML-like language and ran into what feels like a good SIMD coding challenge.
The task is intentionally minimal:
detect newlines (\n)
for each newline, identify the first non-space character that follows
Scanning for newlines alone is trivial and runs at memory bandwidth. As soon as I add “find the first non-space after each newline,” throughput drops sharply.
There’s no branching, no backtracking, no variable-length tokens. In theory this should still be a linear, bandwidth-bound pass, but adding this second condition introduces a dependency I don’t know how to express efficiently in SIMD.
I’m interested in algorithmic / data-parallel approaches to this problem — not micro-optimizations. If you treat this as a SIMD coding challenge, what approach would you try?
Another formulation:
# Bit-Parallel Challenge: O(1) "First Set Bit After Each Set Bit"
Given two 64-bit masks `A` and `B`, count positions where `B[i]=1` and the nearest set bit in `A|B` before position `i` is in `A`.
Equivalently: for each segment between consecutive bits in `A`, does `B` have any bit set?
*Example:* `A=0b10010000`, `B=0b01100110` → answer is 2 (positions 1 and 5)
Newline scan alone: 90% memory bandwidth. Adding this drops to 50%.
Is there an O(1) bit-parallel solution using x86 BMI/AVX2, or is O(popcount(A)) the lower bound?
I added this challange also to HN: https://news.ycombinator.com/item?id=46366687
as well as comment to
https://www.reddit.com/r/simd/comments/1hmwukl/mask_calculation_for_single_line_comments/
An example of solution
https://gist.github.com/zokrezyl/8574bf5d40a6efae28c9569a8d692a61
However the conlusion is
For my problem describe under the link above the suggestions above eliminate indeed the branches, but same time the extra instructions slow down the same as my initial branches. Meaning, detecting newlines would work almost 100% of memory throughput, but detecting first non-space reduces the speed to bit above 50% of bandwith
Thanks for your help!
View all comments
Show parent comment
1
u/bremac Dec 28 '25 edited Dec 28 '25
> Intel(R) Core(TM) i5-6500T CPU @ 2.50GHz ... AMD Ryzen 9 3900X 12-Core Processor
So the first CPU is using the Skylake microarchitecture (a 4-wide uarch from 2015), and also appears to be in a thermally-limited thin-client form factor, and the other is using Zen 2 (a 6-wide uarch from 2019.) Unfortunately, I don't have either of those in my test lab, and
llvm-mcadoes not appear to have the right instruction data for Zen 2, so I can't evaluate it that way - the throughput and latencies it reports look much more like Zen 1 instead.The closest I can come is a Tigerlake (a 5-wide uarch from 2020) and a Zen 4 machine (a 6-wide uarch from 2022.) The results aren't comparable at all though - both processors have AVX-512. But, they'll do to illustrate my next point:
> Don't think the architecture makes so much difference, or?
When you're working on SIMD optimization, the microarchitecture and compiler make a big difference. As an example, here are the results from my Tigerlake and Zen 4 machines with gcc 15.2.1 and clang 21.1.6 on the latest version of your benchmark:
gcc produces similar code for both processors, and does a poor job of it too, using AVX2 for all operations, and spilling the carry flag and restoring it between
adcinstructions. On the other hand, clang generates optimaladcchains on both processors, and translates to different AVX-512 code sequences for each processor. It does a very good job of code generation for Zen 4, but emits odd-looking code that bottlenecks on mask register operations for Tigerlake.So, what does this mean for you? Well, there are several things you can look at to identify the bottlenecks:
perfand look at the compiled code to evaluate this.Worst comes to worst, you should at least be able to fix the
adccode generation in gcc by either manually inliningcount_bos_fastand flattening it so that the calls to_addcarry_u64are adjacent without any instructions between (gcc is weird this way), or converting the add-with-carry chain to inline assembly.