11 ms·

> jumps are a lot slower than conditional arithmetic. This statement is true if the jumps are unpredictable. If the jumps are predictable, then jumps will be

> jumps are a lot slower than conditional arithmetic. This statement is true if the jumps are unpredictable. If the jumps are predictable, then jumps will be faster. Linus had a whole rant about this back in the day, arguing that cmov is not useful if branches are predictable: https://yarchive.net/comp/linux/cmov.html https://yarchive.net/comp/linux/cmov.html

torstenvl 3y ago
I haven't run any benchmarks, but jump-if-equal and set-if-equal would seem to have the same level of predictability. My naive, untested intuition is that there's only one meaningful difference: the former has to dump the entire pipeline on a miss, and the latter only has to nop a single instruction on a miss. But maybe I'm missing something. I'll re-read his rant. EDIT: Linus rants a lot, but makes one concrete claim: You can always replace it by j<negated condition> forward mov ..., %reg forward: and assuming the branch is AT ALL predictable (and 95+% of all branches are), *the branch-over will actually be a LOT better for a CPU.* So, I decided to test that. [18:50:14 user@boxer ~/src/looptest] $ diff -u loop2.s loop4.s --- loop2.s 2023-07-06 18:40:11.000000000 -0400 +++ loop4.s 2023-07-06 18:46:58.000000000 -0400 @@ -17,11 +17,15 @@ incq %rdi xorl %edx, %edx cmpb $115, %cl - sete %dl + jne _run_switches_jmptgt1 + mov $1, %dl +_run_switches_jmptgt1: addl %edx, %eax xorl %edx, %edx cmpb $112, %cl - sete %dl + jne _run_switches_jmptgt2 + mov $1, %dl +_run_switches_jmptgt2: subl %edx, %eax testb %cl, %cl jne LBB0_1 [18:50:29 user@boxer ~/src/looptest] $ gcc -O3 bench.c loop2.s -o l2 [18:50:57 user@boxer ~/src/looptest] $ gcc -O3 bench.c loop4.s -o l4 [18:51:02 user@boxer ~/src/looptest] $ time ./l2 1000 1 449000 ./l2 1000 1 0.69s user 0.00s system 99% cpu 0.697 total [18:51:09 user@boxer ~/src/looptest] $ time ./l4 1000 1 449000 ./l4 1000 1 4.53s user 0.01s system 99% cpu 4.542 total I feel pretty confident that Linus has made a poor prediction about poor prediction here. Jumps are indeed slower. To be fair to Linus, since Clang and I are using sete here, not cmov, I also tested cmov, and the difference was insignificant: [19:53:12 user@boxer ~/src/looptest] $ time ./l2 1000 1 449000 ./l2 1000 1 0.69s user 0.00s system 99% cpu 0.700 total [19:53:15 user@boxer ~/src/looptest] $ time ./l5 1000 1 449000 ./l5 1000 1 0.68s user 0.00s system 99% cpu 0.683 total Jumps are slower.
- haberman 3y ago
  > jump-if-equal and set-if-equal would seem to have the same level of predictability. The difference is that branches have dedicated hardware (branch predictors) that will speculatively execute subsequent instructions based on their best guess about which way the branch will go. Whereas conditional moves cannot execute any subsequent instructions until the correct value is available. Put another way, CPUs have control flow speculation, but not conditional move speculation. I don't know if conditional move speculation would be a feasible thing to implement or not, but I'm pretty sure that no mainstream CPUs have such a feature.
  - Lk7Of3vfJS2n 3y ago
    I'd be curious to learn why CPUs don't have conditional move speculation.
    - Tuna-Fish 3y ago
      Because modern CPUs as a rule don't speculate on values to arithmetic, only on control flow, and CMOV acts like arithmetic. That is, if there is an add instruction on rax and rbx, no matter what, the add instruction will not execute until both rbx and rbx are available. If the result went into rax, and there is an another instruction that uses that as a source, no matter what that instruction will not execute until the add has completed. CMOV is implemented as an ALU instruction that always writes into it's output, and either writes the value that is already in there (which is why it depends on the value of it's output) or the value provided, depending on flags.
      - sitkack 3y ago
        I hope you work on compiler backends.
        epcoa 3y ago
        With all due respect this is quite literally the level of stuff covered in an undergrad EE architecture course and is covered in an elementary text like Patterson and Hennessy.
EVa5I7bHFq9mnYK 3y ago
Is this the reason I dont usually see any speed up if I eliminate array boundary checking in C#? The jump condition is almost always false, is this what "predictable" means?
- gpderetta 3y ago
  Indeed. The cost of bound checking is second order effects like making vectorization harder, slightly higher instruction (and possibly data) cache pressure, or requiring higher decode bandwidth. For the vast majority of programs these bottlenecks do not really matter.
  - EVa5I7bHFq9mnYK 3y ago
    I mean, if the innermost loop is something like 3 assembly instructions, two extra instructions cmp and jg do not make any difference, if jg never executes?
    - kaba0 3y ago
      I am by no means an expert, but I believe what you have in mind would likely fit in i-cache without a problem, so you wouldn’t see a significant difference. There is an interesting talk titled ‘the death of optimizing compilers’ that argues that for most code these optimizations are almost completely meaningless, and in the hot loops where it actually matters, they are not good compared to humans (and sometimes 100x or more improvements are possible and left on the table). While I don’t completely agree with its points, it is a good talk/slides to read through.
      - EVa5I7bHFq9mnYK 3y ago
        Its not that compilers are stupid, they just dont know what humans know about their data, it's ranges, invariants, symmetries etc. They work on most general case, which can be horribly inefficient.
    - gpderetta 3y ago

torstenvl 3y ago

I haven't run any benchmarks, but jump-if-equal and set-if-equal would seem to have the same level of predictability. My naive, untested intuition is that there's only one meaningful difference: the former has to dump the entire pipeline on a miss, and the latter only has to nop a single instruction on a miss. But maybe I'm missing something. I'll re-read his rant. EDIT: Linus rants a lot, but makes one concrete claim: You can always replace it by j<negated condition> forward mov ..., %reg forward: and assuming the branch is AT ALL predictable (and 95+% of all branches are), *the branch-over will actually be a LOT better for a CPU.* So, I decided to test that. [18:50:14 user@boxer ~/src/looptest] $ diff -u loop2.s loop4.s --- loop2.s 2023-07-06 18:40:11.000000000 -0400 +++ loop4.s 2023-07-06 18:46:58.000000000 -0400 @@ -17,11 +17,15 @@ incq %rdi xorl %edx, %edx cmpb $115, %cl - sete %dl + jne _run_switches_jmptgt1 + mov $1, %dl +_run_switches_jmptgt1: addl %edx, %eax xorl %edx, %edx cmpb $112, %cl - sete %dl + jne _run_switches_jmptgt2 + mov $1, %dl +_run_switches_jmptgt2: subl %edx, %eax testb %cl, %cl jne LBB0_1 [18:50:29 user@boxer ~/src/looptest] $ gcc -O3 bench.c loop2.s -o l2 [18:50:57 user@boxer ~/src/looptest] $ gcc -O3 bench.c loop4.s -o l4 [18:51:02 user@boxer ~/src/looptest] $ time ./l2 1000 1 449000 ./l2 1000 1 0.69s user 0.00s system 99% cpu 0.697 total [18:51:09 user@boxer ~/src/looptest] $ time ./l4 1000 1 449000 ./l4 1000 1 4.53s user 0.01s system 99% cpu 4.542 total I feel pretty confident that Linus has made a poor prediction about poor prediction here. Jumps are indeed slower. To be fair to Linus, since Clang and I are using sete here, not cmov, I also tested cmov, and the difference was insignificant: [19:53:12 user@boxer ~/src/looptest] $ time ./l2 1000 1 449000 ./l2 1000 1 0.69s user 0.00s system 99% cpu 0.700 total [19:53:15 user@boxer ~/src/looptest] $ time ./l5 1000 1 449000 ./l5 1000 1 0.68s user 0.00s system 99% cpu 0.683 total Jumps are slower.

haberman 3y ago
> jump-if-equal and set-if-equal would seem to have the same level of predictability. The difference is that branches have dedicated hardware (branch predictors) that will speculatively execute subsequent instructions based on their best guess about which way the branch will go. Whereas conditional moves cannot execute any subsequent instructions until the correct value is available. Put another way, CPUs have control flow speculation, but not conditional move speculation. I don't know if conditional move speculation would be a feasible thing to implement or not, but I'm pretty sure that no mainstream CPUs have such a feature.
- Lk7Of3vfJS2n 3y ago
  I'd be curious to learn why CPUs don't have conditional move speculation.
  - Tuna-Fish 3y ago
    Because modern CPUs as a rule don't speculate on values to arithmetic, only on control flow, and CMOV acts like arithmetic. That is, if there is an add instruction on rax and rbx, no matter what, the add instruction will not execute until both rbx and rbx are available. If the result went into rax, and there is an another instruction that uses that as a source, no matter what that instruction will not execute until the add has completed. CMOV is implemented as an ALU instruction that always writes into it's output, and either writes the value that is already in there (which is why it depends on the value of it's output) or the value provided, depending on flags.
    - sitkack 3y ago
      I hope you work on compiler backends.
      - epcoa 3y ago
        With all due respect this is quite literally the level of stuff covered in an undergrad EE architecture course and is covered in an elementary text like Patterson and Hennessy.

EVa5I7bHFq9mnYK 3y ago

Is this the reason I dont usually see any speed up if I eliminate array boundary checking in C#? The jump condition is almost always false, is this what "predictable" means?

gpderetta 3y ago
Indeed. The cost of bound checking is second order effects like making vectorization harder, slightly higher instruction (and possibly data) cache pressure, or requiring higher decode bandwidth. For the vast majority of programs these bottlenecks do not really matter.
- EVa5I7bHFq9mnYK 3y ago
  I mean, if the innermost loop is something like 3 assembly instructions, two extra instructions cmp and jg do not make any difference, if jg never executes?
  - kaba0 3y ago
    I am by no means an expert, but I believe what you have in mind would likely fit in i-cache without a problem, so you wouldn’t see a significant difference. There is an interesting talk titled ‘the death of optimizing compilers’ that argues that for most code these optimizations are almost completely meaningless, and in the hot loops where it actually matters, they are not good compared to humans (and sometimes 100x or more improvements are possible and left on the table). While I don’t completely agree with its points, it is a good talk/slides to read through.
    - EVa5I7bHFq9mnYK 3y ago
      Its not that compilers are stupid, they just dont know what humans know about their data, it's ranges, invariants, symmetries etc. They work on most general case, which can be horribly inefficient.
  - gpderetta 3y ago