5 ms·
IMHO the original code wasn't written in a way that's particularly friendly to compilers. If you write it like this: int run_switches_branchless(const char
by nwallin 3y ago
IMHO the original code wasn't written in a way that's particularly friendly to compilers. If you write it like this:
int run_switches_branchless(const char* s) {
int result = 0;
for (; *s; ++s) {
result += *s == 's';
result -= *s == 'p';
}
return result;
}
...the compiler will do all the branchless sete/cmov stuff as it sees fit. It will be the same speed as the optimized assembly in the post, +/- something insignificant. However it won't unroll and vectorize the loop. If you write it like this:
int run_switches_vectorized(const char* s, size_t size) {
int result = 0;
for (; size--; ++s) {
result += *s == 's';
result -= *s == 'p';
}
return result;
}
It will know the size of the loop, and will unroll it and use AVX-512 instructions if they're available. This will be substantially faster than the first loop for large inputs, although I'm too lazy to benchmark just how much faster it is.
Now, this requires knowing the size of your string in advance, and maybe you're the sort of C programmer who doesn't keep track of how big your strings are. I'm not your coworker, I don't review your code. Do what you want. But you really really probably shouldn't.
https://godbolt.org/z/rde51zMd8 https://godbolt.org/z/rde51zMd8
- jonny_eh 3y ago> But you really really probably shouldn't. Shouldn't "not" keep track of string length?
- 414owen 3y agoThe version that's friendly to the compiler is described in part two: https://owen.cafe/posts/the-same-speed-as-c/ https://owen.cafe/posts/the-same-speed-as-c/ It achieves 3.88GiB/s I intentionally didn't go down the route of vectorizing. I wanted to keep the scope of the problem small, and show off the assembly tips and tricks in the post, but maybe there's potential for a future post, where I pad the input string and vectorize the algorithm :)
- nwallin 3y agoSo I downloaded your code. On my desktop, with loop-9 gcc I got ~4.5GB/s, and with loop-7 I got ~4.4GB/s. With the following code: #include <stddef.h> int run_switches(const char *s, size_t n) { int res = 0; for (; n--; ++s) res += (*s == 's') - (*s == 'p'); return res; } I got ~31GB/s in GCC and ~33GB/s in Clang. This is without any padding, or SIMD intrinsics, or any such nonsense. This is just untying the compiler's hands and giving it permission to do its job properly. Don't want to pass the string length? That's fine, we can figure that out for ourselves. This code: #include <stddef.h> #include <string.h> int run_switches(const char *s) { int res = 0; for (size_t n = strlen(s); n--; ++s) res += (*s == 's') - (*s == 'p'); return res; } Is 27GB/s. With a little bit of blocking: #include <stddef.h> int run_switches(const char *s, size_t n) { int res = 0; char tmp = 0; for (size_t i = n & 63; i--; ++s) tmp += (*s == 's') - (*s == 'p'); res += tmp; for (n >>= 6; n--;) { tmp = 0; for (size_t i = 64; i--; ++s) tmp += (*s == 's') - (*s == 'p'); res += tmp; } return res; } That's ~55GB/s. Anyway, the point is, you're pretty far from the point where you ought to give up on C and dive into assembly.
- rajnathani 3y agoThis seems like the most efficient solution. I have a neighboring comment on this post which suggests using bit arithmetic, but the above solution is more efficient than that. Here’s what the assembly code for the body of the first loop compiles down to (I had to use ChatGPT-4 as godbolt unfortunately doesn’t work on mobile): cmp dl, 's' ; Compare the character with 's' sete dl ; If the character is 's', set dl to 1. Otherwise, set dl to 0. sub al, dl ; Subtract the result from res cmp dl, 'p' ; Compare the character with 'p' sete dl ; If the character is 'p', set dl to 1. Otherwise, set dl to 0. add al, dl ; Add the result to res
- utopcell 3y agoIndeed. I suppose the two lessons are, stick with C, and don't forget the semantics of your original problem when optimizing. int run_switches(const char *s) { int res = 0; uint8_t tmp = 0; size_t n = strlen(s); for (size_t i = n & 127; i--; ++s) tmp += (*s == 's'); res += tmp; for (size_t j = n >> 7; j--;) { tmp = 0; for (size_t i = 128; i--; ++s) tmp += (*s == 's'); res += tmp; } return 2 * res - n; }
- elcritch 3y agoNice! I tried it in Nim and it appears to trigger it with: {.overflowChecks:off.} proc run_switches*(input: cstring): int {.exportc.} = result = 0 for c in input: result.inc int('s' == c) result.dec int('p' == c) That gives a ~5x speedup on an Apple M1. Keeping overflow checks on only gets it up to ~2x the default C version. Always nice to know good ways to trigger SIMD opts.
- shusaku 3y agoYou forgot an important line of the code: /* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */