9 ms·
I'm not so sure that the right take-away is "hand-written assembler is 6x faster than C." It's more like "jumps are a lot slower than conditional arithmetic." A
by torstenvl 3y ago
I'm not so sure that the right take-away is "hand-written assembler is 6x faster than C." It's more like "jumps are a lot slower than conditional arithmetic." And that can [edit:often] be achieved easily in C by simply not using switch statements when an if statement or two will work fine.
Rewriting the C function as follows got a 5.5x speedup:
int run_switches(char *input) {
int r = 0;
char c;
while (1) {
c = *input++;
if (c == 's') r++;
if (c == 'p') r--;
if (c == '\0') break;
}
return r;
}
Results:
[16:50:14 user@boxer ~/looptest] $ gcc -O3 bench.c loop1.c -o lone
[16:50:37 user@boxer ~/looptest] $ gcc -O3 bench.c loop2.c -o ltwo
[16:50:47 user@boxer ~/looptest] $ time ./lone 1000 1
449000
./lone 1000 1 3.58s user 0.00s system 99% cpu 3.589 total
[16:50:57 user@boxer ~/looptest] $ time ./ltwo 1000 1
449000
./ltwo 1000 1 0.65s user 0.00s system 99% cpu 0.658 total
- BoppreH 3y agoWhat version of GCC are you using? For me both versions perform the same, both on Ubuntu and Windows: $ time ./lone 1000 1 851000 real 0m3.578s user 0m3.574s sys 0m0.004s $ time ./ltwo 1000 1 851000 real 0m3.583s user 0m3.583s sys 0m0.000s $ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 Copyright (C) 2019 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
- torstenvl 3y agoSorry, I write 'gcc' purely out of force of habit. I'm using Clang/LLVM. [17:23:00 user@boxer ~/looptest] $ uname -a Darwin boxer.local 21.6.0 Darwin Kernel Version 21.6.0: Thu Jun 8 23:57:12 PDT 2023; root:xnu-8020.240.18.701.6~1/RELEASE_X86_64 x86_64 [17:23:47 user@boxer ~/looptest] $ cc -v Apple clang version 14.0.0 (clang-1400.0.29.202) Target: x86_64-apple-darwin21.6.0 Thread model: posix InstalledDir: /Library/Developer/CommandLineTools/usr/bin Clang generates the sete instruction for me with the above code: [17:23:49 user@boxer ~/looptest] $ gcc -c -O3 loop2.c [17:25:00 user@boxer ~/looptest] $ objdump -d --symbolize-operands --x86-asm-syntax=intel --no-show-raw-insn loop2.o loop2.o: file format mach-o 64-bit x86-64 Disassembly of section __TEXT,__text: 0000000000000000 <_run_switches>: 0: push rbp 1: mov rbp, rsp 4: xor eax, eax 6: nop word ptr cs:[rax + rax] <L0>: 10: movzx ecx, byte ptr [rdi] 13: add rdi, 1 17: xor edx, edx 19: cmp cl, 115 1c: sete dl 1f: add eax, edx 21: xor edx, edx 23: cmp cl, 112 26: sete dl 29: sub eax, edx 2b: test cl, cl 2d: jne <L0> 2f: pop rbp 30: ret
- DeathArrow 3y agoShouldn't the compiler be able to do that, too?
- ModernMech 3y agoYes, there’s always the “sufficiently smart compiler” that can generate this code. Question is, does that compiler exist?
- Groxx 3y agoI sure hope so. The semantics are trivially identical, the optimizations should be as well, by default - they should depend on semantics, not syntax. And GCC in another comment under this thread seems to be doing similar or identical optimizations in both cases. I wholly admit that this implies nothing about all optimizers. But it's a pretty reasonable one to expect.
- charcircuit 3y ago>does that compiler exist? and if so are the compile times worth it
- icsa 3y agoThese days, I's put my money on zig cc. I.E. zig cc -Os or zig cc -O3
- eyegor 3y agoDoes the zig compiler have many fancy bits? I was under the impression the c support was a "nothing special" compiler that punted to llvm for optimizations.
- plorkyeran 3y agoCorrect, zig currently does not do any of its own optimizations. It won't necessarily have identical results to clang because it'll generate equivalent but not identical IR and the optimizer passes may happen to do something different as a result, but it's not going to be consistently different.
- haberman 3y ago> 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 agoI 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.
- 414owen 3y agoNice! There's a part two in which I rewrote the C. I got a 12x speedup :) https://owen.cafe/posts/the-same-speed-as-c/ https://owen.cafe/posts/the-same-speed-as-c/ And as others have pointed out, you can tweak the input, then vectorize the algo, if you want to go that route. I considered this a pedagogical exercise and I sincerely hope nobody will start dropping down to assembly without a very good reason to.
- rajnathani 3y agoGreat post! One thought: If the code is rewritten using bit arithmetic, then potentially the result could be even faster as there need not be a pointer look-up. A bit arithmetic solution would have a mask created for the characters ‘p’ and ‘s’, and then the result could be AND-ed, and then with more bit arithmetic this all 1s value can be translated to a 1 if and only if all the bits are 1. Following which, there would be a no conditional check and simply be both an add and a subtract operation but where the value to be added will only be 1 if the mask for ‘p’ matches and 1 to be subtracted if the mask for ‘s’ matches respectively. I’m not fully sure if this would necessarily be faster than the pointer look-up solution, but it would be interested to try this version of the code and see how fast it performs. Update: The bit arithmetic could also be done with an XOR on the mask, and following which the ‘popcnt’ x86 instruction could be used to figure out if all are 0 bits.
- JohnMakin 3y agoThank you for your post and reply but I fear with a post + title like this you may just be chumming the waters.
- p1necone 3y agoIs rewriting switch statements to a bunch of ifs always faster? Or is there some number of cases where the switch is faster? Seems like it should be added as a compiler optimization if it's consistent.
- Karellen 3y agoIt shouldn't be. If the fastest way to implement a particular `switch` in assembly is with the equivalent of a set of `if`s, a reasonably smart compiler "should" be able to output the assembly to do that. And I thought that gcc and clang at least have actually been smart enough to do that for a while now. But if the number of `if`s is high and the distribution sufficiently dense, where a jump table is better than a bunch of `if`s, then a `switch` should output that. OTOH, a sufficiently smart compiler could theoretically turn a bunch of `if`s into a `switch`-like jump table - but it's much harder to reason that case through correctly than it is the other way, so I'm not sure any current compilers are sufficiently smart to do that.
- kevin_thibedeau 3y agoOn x64, GCC is supposed to use a a jump table with more than 4 cases when the cases are dense enough (gaps of 9 or less) to minimize wasted memory, otherwise it generates sequential comparisons. Testing on Godbolt, it looks like GCC 13.1 uses 10 cases as the jump table threshold for ARM64.
- flohofwoe 3y agoIt shouldn't if the control flow is actually identical. E.g. note how both the switch- and if-based functions generate the same code using a lookup table here: https://godbolt.org/z/qoT3M7r5G https://godbolt.org/z/qoT3M7r5G
- BbzzbB 3y agoIs there any good article comparing performance across programming languages? Seems like everytime I see one they're broken because the tested logic is poorly implemented in language(s) XYZ.
- deleted 3y ago[deleted]
- okaleniuk 3y agoYes, but this will backfire on ARM, where jumps are as roughly fast as conditional arithmetic. The whole point of using C is not to think about the underlying architecture. As soon as you start taking "jumps are a lot slower than conditional arithmetic on x86" into account, you're not writing in C, you're writing in assembly with extra steps :-)
- bruce343434 3y agoIs that because cjumps on ARM are faster, or cmovs on ARM are slower?
- dzaima 3y agoNote, that's only ARMv7; ARMv8 dropped most of the conditionally executed instruction stuff. And so it isn't even jumps that's fast on ARMv7, it's specifically cases that can be (and are) converted to predicated instrs; jumps are still gonna be slow in general on anything high-perf enough that it needs speculation, which can include the actual jumps of ARMv7. If a compiler can convert jumpy code to the predicated instrs, it should be able to trivially convert conditional arith to such too (even easier & more consistently than branches I'd say).
- MisterTea 3y agoYou can shorten the loop to just tree conditionals: while (c = *input++) { if (c == 's') r++; if (c == 'p') r--; }