I see other people have done minor rewrites, but the post does mention reordering branches, so the obvious question is whether there was any attempt to use PGO, which is an obvious first step in optimization.
{n} times faster than C
141–150 of 249 posts
Re: {n} times faster than C
#142It's a cardinal rule that any time someone utters "XYZ is n faster than C" someone comes along and shows C is actually 2x faster than XYZ.
I had an old compilers professor say something like this once. “If you think you can do something better than the C compiler, I promise you you can’t.”
That is just dumb and overly reductive. There is just lot of properties about programs that can not be expressed to compiler with portable ISO C but could be exploited for optimization. Of course reducing portability progressively improves situation, like using GCC extensions or machine-specific intrinsics. But even then its ridiculous to claim that C compilers could in general case generate true optimal code.
Re: {n} times faster than C
#143Earlier quoted context omitted.
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…
This is a wonderful thread. Which tricks in there are worth playing around with more widely? Is the uint8_t just "no point in using something bigger" or does it likely help the compiler? Does/can the signedness matter as well as the size? Ditto looping downwards -- is it often likely to improve things? Can it generalize to pointer/iterator ranges, or is it often worth trying to phrase them in terms of array/index acc…
> Is the uint8_t just "no point in using something bigger" or does it likely help the compiler? Does/can the signedness matter as well as the size?
In a good world you could use just uint_fast8_t and compiler would optimize this question for you. In real world I don't think compilers are smart enough, or there are too many other constraints limiting them :(
Re: {n} times faster than C
#144Earlier quoted context omitted.
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…
Yeah, or at least I don't understand why that wouldn't be possible. Microcode can set the EIP register based on its prediction of what the result of cmpb $115, %cl will be. Why can't it set the EDX register based on its prediction of what the result of cmpb $115, %cl will be?
In principle is perfectly possible to speculatively execute cmov (and viceversa to change jump-over-one-instruction into conditional execution).
But Intel historically didn't do it as programs tend to use cmov when the condition is unpredictable , so there was little reason to optimize it.
After Spectre, I believe intel has given an architectural guarantee that cmov is never speculated so it can be used as part of speculation attack prevention.
Re: {n} times faster than C
#145naive q: could one just count one of the letters and subtract it from the total number of letters?
You’d need to count both as other characters are ignored.
naïve q2: does that mean most comparisons are no match 3 times? could one do a bitwise operation and fuzzy test for all 3 in one go?
Re: {n} times faster than C
#146Earlier quoted context omitted.
> 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
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?
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.
Re: {n} times faster than C
#147Earlier 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; }
This makes the assumption that the only characters in the string are "s" and "p". There is no basis for this assumption. I think this code solves a different problem rather than being an optimisation of the original code.
Re: {n} times faster than C
#148I'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…
Is 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.
It 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:
Re: {n} times faster than C
#149Earlier quoted context omitted.
> 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
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 clai…
Did you test this on a Pentium 4, the processor that Linus is talking about?
Re: {n} times faster than C
#150Earlier quoted context omitted.
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 clai…
Linus' 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.
I read the rant. He is talking about Pentium 4.