{n} times faster than C

Post by torstenvl » Fri, Jul 07, 2023, 4:38 AM UTC

celrod wrote: post #122

torstenvl wrote: post #112

Earlier quoted context omitted.

I'm not saying you're wrong — I'm completely ignorant at the microcode level — but it seems to me like between cmp x, y je z and cmp x, y sete z the actual speculative part is the same: speculating as to the result of cmp x, y If that's true, why would it not simply pipeline sete and the following instructions and simply execute (or not execute) sete according to its prediction, and then double check itself and rever…

Taking the example: cmpb $115, %cl sete %dl addl %edx, %eax vs cmpb $115, %cl jne _run_switches_jmptgt1 mov $1, %dl _run_switches_jmptgt1: addl %edx, %eax The argument about why `jne` might be faster is that that in the former case, the CPU always executes a dependency chain of length 3: `cmpb` -> `sete` -> `addl`. Each of these instructions have to be computed one after the other, as `sete` depends on the result of…

Post by skavi » Fri, Jul 07, 2023, 4:52 AM UTC

nwallin wrote: post #119

utopcell wrote: post #113

Earlier quoted context omitted.

Indeed. 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; }

Neat! Although you'll need to make a copy of `n`. The second loop will reduce the value of n to null. Edit: Also, there's an off by one error. should be: #include #include int run_switches(const char *s, const size_t n) { int res = 0; uint8_t tmp = 0; for (int i = n & 127; i--; ++s) tmp += *s == 's'; res += tmp; for (int size = n >> 7; size--;) { tmp = 0; for (int i = 128; i--; ++s) tmp += *s == 's'; res += tmp; } re…

Post by romnon » Fri, Jul 07, 2023, 5:08 AM UTC

sriku wrote: post #95

414owen wrote: post #51

Earlier quoted context omitted.

Nice! 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/ 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.

Wondering how res += (c=='s')-(c=='p') might do. I sure there is some C undefined behaviour relevant there. Curious but too lazy to check it myself!

Post by [deleted] » Fri, Jul 07, 2023, 5:39 AM UTC

torstenvl wrote: post #11

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…

Post by teo_zero » Fri, Jul 07, 2023, 5:45 AM UTC

utopcell wrote: post #113

nwallin wrote: post #87

Earlier quoted context omitted.

So 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 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 an…

Indeed. 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; }