6 ms·
The examples are fun, but rather than yet another article saying how amazing optimizing compilers are (they are, I already know), I'd probably benefit more from
by abainbridge 10mo ago
The examples are fun, but rather than yet another article saying how amazing optimizing compilers are (they are, I already know), I'd probably benefit more from an article explaining when obvious optimizations are missed and what to do about it.
Some boring examples I've just thought of...
eg 1:
int bar(int num) { return num / 2; }
Doesn't get optimized to a single shift right, because the that won't work if num is negative. In this case we can change the ints to unsigneds to tell the compiler we know the number isn't negative. But it isn't always easy to express to the compiler everything you know about your data and use case. There is an art in knowing what kinds of things you need to tell the compiler in order to unlock optimizations.
eg 2:
int foo(void) { return strlen("hello"); }
We all know that strlen will return 5, but some compilers don't: https://godbolt.org/z/M7x5qraE6 https://godbolt.org/z/M7x5qraE6
eg 3:
int foo(char const *s) {
if (strlen(s) < 3) return 0;
if (strcmp(s, "hello") == 0)
return 1;
return 0;
}
This function returns 1 if s is "hello". 0 otherwise. I've added a pointless strlen(). It seems like no compiler is clever enough to remove it. https://godbolt.org/z/Koj65eo5K https://godbolt.org/z/Koj65eo5K. I can think of many reasons the compiler isn't able to spot this.
- commandlinefan 10mo ago> won't work if num is negative I remember reading (although I can't find it now) a great analysis of all the optimizations that Javascript compilers _can't_ do because of the existence of the "eval" instruction.
- astrange 10mo agoA JIT can do any optimization it wants, as long as it can deoptimize if it turns out it was wrong.
- LoganDark 10mo agoCould this perhaps be it? https://janvitek.org/pubs/ecoop11.pdf https://janvitek.org/pubs/ecoop11.pdf
- cibyr 10mo agoThe extra fun thing about this is that eval has different semantics if it's assigned to a different name, in order to allow JavaScript implementations to apply extra optimizations to code that doesn't call a function literally named "eval": https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/eval#direct_and_indirect_eval https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... Andy Wingo (of course!) has a good explanation of this: https://wingolog.org/archives/2012/01/12/javascript-eval-considered-crazy https://wingolog.org/archives/2012/01/12/javascript-eval-con...
- dzaima 10mo ago> I've added a pointless strlen(). It seems like no compiler is clever enough to remove it. For that you could at least argue that if the libc's strlen is faster than strcmp, that improves performance if the programmer expects the function to be usually called with a short input. That said, changing it to `if (strlen(s) == 5) return 0;` it still doesn't get optimized (https://godbolt.org/z/7feWWjhfo https://godbolt.org/z/7feWWjhfo), even though the entire function is completely equivalent to just `return 0;`.
- senfiaj 10mo agoYeah, this one as well: bool is_divisible_by_6(int x) { return x % 2 == 0 && x % 3 == 0; } bool is_divisible_by_6_optimal(int x) { return x % 6 == 0; } Mathematically x % 2 == 0 && x % 3 == 0 is exactly the same as x % 6 == 0 for all C/C++ int values but the compiler doesn't see them as identical, and produces less optimal code for is_divisible_by_6 than for is_divisible_by_6_optimal.
- abainbridge 10mo agoNice. Is the best way to think of optimizing compilers, "I wonder if someone hand wrote a rule for the optimizer that fits this case"?
- stouset 10mo agoProbably not, because a lot of the power of optimizing compilers comes from composing optimizations. Also a lot comes from being able to rule out undefined behavior.
- Koffiepoeder 10mo agoMhm, this is one of these cases I'd prefer a benchmark to be sure. Checking %2 is very performant and actually just a single bit check. I can also imagine some cpu's having a special code path for %3. In practice I would not be surprised that the double operand is actually faster than the %6. I am mobile at this moment, so not able to verify.
- Bratmon 10mo agoBut if % 2 && % 3 is better, then isn't there still a missed optimization in this example?
- NobodyNada 10mo agoLet's throw this into godbolt: https://clang.godbolt.org/z/qW3qx13qT https://clang.godbolt.org/z/qW3qx13qT is_divisible_by_6(int): test dil, 1 jne .LBB0_1 imul eax, edi, -1431655765 add eax, 715827882 cmp eax, 1431655765 setb al ret .LBB0_1: xor eax, eax ret is_divisible_by_6_optimal(int): imul eax, edi, -1431655765 add eax, 715827882 ror eax cmp eax, 715827883 setb al ret By themselves, the mod 6 and mod 3 operations are almost identical -- in both cases the compiler used the reciprocal trick to transform the modulo into an imul+add+cmp, the only practical difference being that the %6 has one extra bit shift. But note the branch in the first function! The original code uses the && operator, which is short-circuiting -- so from the compiler's perspective, perhaps the programmer expects that x % 2 will usually be false, and so we can skip the expensive 3 most of the time. The "suboptimal" version is potentially quite a bit faster in the best case, but also potentially quite a bit slower in the worst case (since that branch could be mispredicted). There's not really a way for the compiler to know which version is "better" without more context, so deferring to "what the programmer wrote" makes sense. That being said, I don't know that this is really a case of "the compiler knows best" rather than just not having that kind of optimization implemented. If we write 'x % 6 && x % 3', the compiler pointlessly generates both operations. And GCC generates branchless code for 'is_divisible_by_6', which is just worse than 'is_divisible_by_6_optimal' in all cases.
- stabbles 10mo agoThe compiler doesn't know the implementation of strlen, it only has its header. At runtime it might be different than at compile time (e.g. LD_PRELOAD=...). For this to be optimized you need link time optimization.
- dzaima 10mo agoBoth clang and gcc do optimize it though - https://godbolt.org/z/cGG9dq756 https://godbolt.org/z/cGG9dq756. You need -fno-builtin or similar to get them to not.
- abainbridge 10mo agoHmmm, really? Switching compiler seems sufficient: https://godbolt.org/z/xnevov5d7 https://godbolt.org/z/xnevov5d7 BTW, the case of it not optimizing was MSVC targetting Windows (which doesn't support LD_PRELOAD, but maybe has something similar?).
- valleyer 10mo agoNo, the compiler may assume that the behavior of standard library functions is standards-conformant.
- SpaceManNabs 10mo ago> No, the compiler may assume that the behavior of standard library functions is standards-conformant. Why? What happens if it isn't?
- DannyBee 10mo agoBecause that's what it means to compile a specific dialect of a specific programming language? If you want a dialect where they aren't allowed to assume that you would have to make your own
- MindSpunk 10mo agoSadness. Tons of functions from the standard library are special cases by the compiler. The compiler can elide malloc calls if it can prove it doesn't need them, even though strictly speaking malloc has side effects by changing the heap state. Just not useful side effects. memcpy will get transformed and inlined for small copies all the time.
- abainbridge 10mo agoeg 4: int foo(char const *s) { if (s[0] == 'h' && s[1] == 'e' && s[2] == 'l' && s[3] == 'l') return 1; return 0; } The outputs 4 cmp instructions here, even though I'd have thought 1 was sufficient. https://godbolt.org/z/hqMnbrnKe https://godbolt.org/z/hqMnbrnKe
- raphlinus 10mo agoThat's because the 1 instruction variant may read past the end of an array. Let's say s is a single null byte at 0x2000fff, for example (and that memory is only mapped through 0x2001000); the function as written is fine, but the optimized version may page fault.
- abainbridge 10mo agoAh, yes, good point. I think this is a nice example of "I didn't notice I needed to tell the compiler a thing I know so it can optimize".
- ynik 10mo ago`s[0] == 'h'` isn't sufficient to guarantee that `s[3]` can be access without a segfault, so the compiler is not allowed to perform this optimization. If you use `&` instead of `&&` (so that all array elements are accessed unconditionally), the optimization will happen: https://godbolt.org/z/KjdT16Kfb https://godbolt.org/z/KjdT16Kfb (also note you got the endianness wrong in your hand-optimized version)
- abainbridge 10mo agoOoo, I'd never thought of using & like that. Interesting. > (also note you got the endianness wrong in your hand-optimized version) Doh :-)
- rdc12 10mo agoMatt Godbolt's talk on ray tracers, shows how effective that change can be. Think it was that talk anyway. https://www.youtube.com/watch?v=HG6c4Kwbv4I https://www.youtube.com/watch?v=HG6c4Kwbv4I
- abbeyj 10mo ago> We all know that strlen will return 5, but some compilers don't: https://godbolt.org/z/M7x5qraE6 https://godbolt.org/z/M7x5qraE6 I feel like it is unfair to blame the compiler when you've explicitly asked for `/O1`. If you change this to `/O2` or `/Ox` then MSVC will optimize this into a constant 5, proving that it does "know" that strlen will return 5 in this case.
- abainbridge 10mo agoFair point. It doesn't do the optimization if you ask to optimize for size '/Os' either.
- WalterBright 10mo ago`s` may be null, and so the strlen may seg fault.
- pianom4n 10mo agoBut that's undefined behavior, so the compiler is free to ignore that possibility.
- WalterBright 10mo ago> so the compiler is free to ignore that possibility And that's what is wrong. This is the most unfriendly behavior towards the programmer.
- flqn 10mo agoSince the optimiser is allowed to assume you're not invoking UB, and strlen of null is UB, I don't believe that it would consider that case when optimising this function.
- WalterBright 10mo agoI understand that, but I don't agree that such optimizer behavior is worth it and I won't put it in my compilers.
- kragen 10mo agoI appreciate that greatly.
- WalterBright 10mo agoThe notion that because it is undefined behavior means that the compiler is free to replace it with anything up to and including "launch nuclear missiles". This is just nuts. If I program it to cause a null pointer seg fault, I expect a null pointer seg fault. If I program it to cause a twos complement overflow, I want a twos complement overflow.
- SkiFire13 10mo ago> int bar(int num) { return num / 2; } > > Doesn't get optimized to a single shift right, because the that won't work if num is negative. Nit: some might think the reason this doesn't work is because the shift would "move" the sign bit, but actually arithmetic shifting instructions exist for this exact purpose. The reason they are not enough is because shifting provides the wrong kind of division rounding for negative numbers. This can however be fixed up by adding 1 if the number is negative (this can be done with an additional logical shift for moving the sign bit to the rightmost position and an addition).
- kragen 10mo agoWill shift, shift, and add be slower or faster than a divide instruction on machines with a divide instruction?
- SkiFire13 10mo agoMost likely no, division instructins generally take as much as 10-20 other arithmetic/logic instruction.
- abainbridge 10mo agoGood point. I guess there are more cases than just this one where I'd like to be able to tell the compiler I don't care about rounding behaviour and would prefer the fastest code. Like -ffast-math but for integer operations. I don't think that exists. I wonder why.
- delta_p_delta_x 10mo ago> but some compilers don't: https://godbolt.org/z/M7x5qraE6 https://godbolt.org/z/M7x5qraE6 You've misrepresented the situation. Turn up the optimiser to `/O2` and MSVC returns 5 directly, too. > This function returns 1 if s is "hello". 0 otherwise. I've added a pointless strlen(). It seems like no compiler is clever enough to remove it. It's funny how sometimes operating at a higher level of abstraction allows the compiler to optimise the code better: https://godbolt.org/z/EYP5764Mv https://godbolt.org/z/EYP5764Mv In this, the string literal "hello" is lowered not merely into a static string, but a handful of integral immediates that are directly inline in the assembly, no label-dereferencing required, and the 'is equal to "hello"' test is cast as the result of some sign extends and a bitwise-xor. Of course, one could argue that std::string_view::size() is statically available, but then my counter-argument is that C's zero-terminated strings are a massive pessimisation (which is why the compiler couldn't 'see' what we humans can), and should always be avoided.