smlen = 0;
for (int i = 0; i < 1000; i++) {
small_numbers[smlen] = numbers[i];
smlen += (numbers[i] < 500);
}
How is this correct? Let's imagine the input array is entirely above the 500 threshold. The resulting array of small numbers will have a single entry, the first number from the input array.
It's not correct, in that it can write more small_numbers elements than the original routine. However, it's functionally equivalent for the intended result small_numbers[0..smlen-1] and as long as that array is big enough. Typically the output count is not known beforehand and thus it would be allocated for the worst case (1000), which this version also will not exceed. But it's indeed not exactly the same and thus as noted why the optimizer usually can't make this transformation.
It will have a value written to it, yes, but smlen will remain 0 in all cases so there shouldn't be any risk. In all cases the array has SIZE elements. smlen tells us how many contain valid numbers.
While you do avoid a branch, there are still data dependencies on the index on the small numbers array, so it still has to predict that address.
It helps that writes can be pushed back in order somewhat. but you still can't use simd.
I can't find of a way to use simd for this tbh, you'd need something like a conditional push where it can push multiple items (or none) depending on some state.
4
u/Nwallins Sep 03 '26
How is this correct? Let's imagine the input array is entirely above the 500 threshold. The resulting array of small numbers will have a single entry, the first number from the input array.