12 ms·
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 ther
by 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 agoI'd be curious to learn why CPUs don't have conditional move speculation.
- Tuna-Fish 3y agoBecause 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 agoI hope you work on compiler backends.
- epcoa 3y agoWith 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.
- sitkack 3y ago> With all due respect > quite literally You could have conveyed the close to the same thing by saying, "things like this are covered in Patterson and Hennessy" > elementary text Jesus, do you even lift? The rest of the discussion is amazing.
- epcoa 3y agoFor those not aware Patterson and Hennessy is elementary (“relating to the basic elements of a subject.”) because it is often used in an introductory course of computer architecture. This isn’t a slight.
- AnotherGoodName 3y agoThe inputs here are random which is the problem and why this isn't demonstrating that. Create an input of all 's' and compare it.
- torstenvl 3y agoBetter than random input, but still only ~half as fast as using sete [19:13:34 user@boxer ~/src/looptest] $ diff -u bench.c bench-alls.c --- bench.c 2023-07-06 16:04:16.000000000 -0400 +++ bench-alls.c 2023-07-06 19:13:34.000000000 -0400 @@ -17,7 +17,7 @@ int num_rand_calls = number / CHAR_BIT + 1; unsigned char *buffer = malloc(num_rand_calls * CHAR_BIT); for (int i = 0; i < num_rand_calls; i++) { - buffer[i] = rand(); + buffer[i] = 's'; //rand(); } return buffer; } [19:13:37 user@boxer ~/src/looptest] $ gcc -O3 bench-alls.c loop2.s -o l2 [19:13:42 user@boxer ~/src/looptest] $ gcc -O3 bench-alls.c loop4.s -o l4 [19:13:47 user@boxer ~/src/looptest] $ time ./l2 1000 1 250001000 ./l2 1000 1 0.69s user 0.00s system 99% cpu 0.699 total [19:13:55 user@boxer ~/src/looptest] $ time ./l4 1000 1 250001000 ./l4 1000 1 1.28s user 0.00s system 99% cpu 1.290 total Jumps are slower.
- deleted 3y ago[deleted]
- Guvante 3y agoMicrobenchmarks are hard. You aren't doing any meaningful work that could benefit from speculatively executing instead of stalling for the conditional value. Similarly you might be busting the pipeline by chaining together the jumps so close together. Not saying your point is wrong, just saying your proof isn't super solid.
- deleted 3y ago[deleted]
- gpderetta 3y agoIn this benchmark the only loop carried dependency is over the res variable (edit: and of course the index). The jump doesn't break these dependencies, so for this specific problem, the additional latency of the cmov doesn't matter as it is always perfectly pipelined and cmov will always come up on top. But if the input of cmov depended on a previous value, then potentially a branch could be better given an high enough prediciton rate.
- seventhson 3y agoLinus' post is 15+ years old. Much has changed in Intel hardware since then. He was probably right on the money re the hardware available at the time.
- torstenvl 3y ago> I don't know when the change was made, but conditional moves are fast and efficient on the last several generations of AMD and Intel processors. Usually, you are trading 1 or 2 extra cycles of latency against the chance of a ~15 cycle mispredicted branch penalty. If your branch cannot be predicted correctly ~85% of the time, this can be a significant win. https://news.ycombinator.com/item?id=10749195 https://news.ycombinator.com/item?id=10749195
- zaxomi 3y agoI read the rant. He is talking about Pentium 4.
- MobiusHorizons 3y agoJumps are slower on completely random input. If I understand Linus’s point correctly, he is suggesting that random inputs like this are unusual (although a good way to measure worst case performance)
- zaxomi 3y agoDid you test this on a Pentium 4, the processor that Linus is talking about?
- deleted 3y ago[deleted]