3 ms·
buffer_num += (elements[i] < pivot); Is this really branchless though? I'm curious what the generated assembler code looks like.
by codeflo 10y ago
buffer_num += (elements[i] < pivot);
Is this really branchless though? I'm curious what the generated assembler code looks like.
- looki 10y agoIt is. You can use the `setl` instruction to conditionally set a register depending on whether the previous `cmp` was less. Then, you simply do an `add` with the produced value, which is either 0 or 1. EDIT: You can see this here https://godbolt.org/g/ssy4am https://godbolt.org/g/ssy4am
- nightcracker 10y agoYour example is incorrect. But even if it were correct, a much better way of visualizing this is by unrolling the loop (as is done in my pdqsort implementation): https://godbolt.org/g/qWkmG4 https://godbolt.org/g/qWkmG4 The odd writing style of first doing all comparisons is intentional - it increases the parallelism and reduces the data dependency in the generated code. Note how all the colors are mixed through eachother: this is a good sign. Also note that there are no branches at all in the generated code. It's 'straight' code that the CPU can just march through at full speed. This is what makes it so stupidly fast.
- looki 10y agoI think you misunderstood the OP (or maybe I have?) - it wasn't about parallelism, just about that one use of a comparison inside the addition. I showed that CPUs don't need to generate conditional jumps for that, that's all. EDIT: To clarify, my example was completely contrived, I just reused your variable names for some sense of familiarity.
- lgeek 10y agoThat's applicable if you compile for 386 or a newer x86 and your compiler generates the code you expect. On AArch32 (ARM) you could use conditional MOV and on AArch64 you could use CSET. I'm sure that other architectures also have similar instructions, however it's not a guarantee that you'll end up with branchless machine code.