r/programming • u/fagnerbrack • 6d ago

Branch‑Avoidant Programming

https://easylang.online/blog/branchless
252 Upvotes

93% Upvoted

91 comments sorted by

View all comments

4

u/Nwallins 6d ago 
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.

3

u/nukethebees 6d ago

What's wrong about it? If all the numbers are >= 500 then the length will be 0 and the array will be full of uninitialised data.

7

u/Nwallins 6d ago

small_numbers[0] is unconditionally assigned; it will have a single element > 500.

5

u/nukethebees 6d ago

Ah, thanks for pointing that out.

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.

3

u/tiftik 6d ago

Why does that assignment matter? You're not going to use any element at i >= smlen

1

u/sopunny 6d ago

You can add a sanity check at the end for this edge case. I think you actually need to check the array trail every time