4 ms·
Technically a comparison operator would be a form of branching, because you have comparisons and jumps based off flags, same as what happens when you compile an
by partycoder 9y ago
Technically a comparison operator would be a form of branching, because you have comparisons and jumps based off flags, same as what happens when you compile an if statement.
It becomes more evident when you see the generated code. https://godbolt.org/g/Mu9KBY https://godbolt.org/g/Mu9KBY
e.g:
cmp rax, QWORD PTR [rbp-24] ; compare a and b
ja .L2 ; is a above b?, if so jump to .L2, otherwise proceed
In fact this statement:
size_t ret = (haystack[4] <= needle) * 4;
...is 100% equivalent to this once compiled:
register size_t ret;
if (haystack[4] <= needle) {
ret = 4;
} else {
ret = 0;
}
So the code is not really branchless, just if-less.
- partycoder 9y agoTo the trolls that downvoted my post without explaining why, here is the proof: https://godbolt.org/g/xXecW2 https://godbolt.org/g/xXecW2 I rewrote the function using if statements making it compile to exactly the same instructions. If you optimize the code with compiler flags (e.g: -msse, -msse2 for SSE/SSE2, -O3 for optimization) the generated instructions are exactly the same. My point being: the code in the blog post is not branchless. The absence of if statements doesn't mean it's branchless. If you care to disagree here by downvoting I dare you to reply explaining why you think this is wrong.
- grenoire 9y agoYou didn't read the post properly. There is a subsection for a version without ternary operators.
- partycoder 9y agoThe version I compared against was the one using numeric comparison ( <= ) not ternary operators. It's in the link I shared. So I hope you revert your downvote or provide proof of what I am saying is incorrect.
- Atrix256 9y agoYou are completely right, I'll mention this in the post (In that case do a branchless comparison based on subtraction or similar?). Fwiw when doing simd, you'd use intrinsics which wouldn't have this issue, but it is a valid point and completely true. Thanks!
- partycoder 9y ago"You are right!" + no upvote = bad
- Atrix256 9y agoI'm not the one who downvoted you, but I am the one who wrote the article :P