Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

You can't fool the optimizer

xania.org

Post reply on HN
Print view View original

131–140 of 193 posts

Re: You can't fool the optimizer

#131

Post by titzer »

tialaramex wrote: post #59
sureglymop wrote: post #8

With this one I instead wondered: If there are 4 functions doing exactly the same thing, couldn't the compiler also only generate the code for one of them? E.g. if in `main` you called two different add functions, couldn't it optimize one of them away completely? It probably shouldn't do that if you create a dynamic library that needs a symbol table but for an ELF binary it could, no? Why doesn't it do that?

If your language has monomorphization† (as C++ and Rust do) then it's really common to have this commonality in the emitted code and I believe it is common for compilers to detect and condense the resulting identical machine code. If the foo function for an integer checks if it's equal to four, it well be that on your target hardware that's the same exact machine code whether the integer types T are 1 byte, 2 bytes o…

The linker de-duping identical machine code is common, but most frontends that do monomorphization aren't that smart about identical copies, because monomorphization is usually done with source-level types, and there are lots of typeful operations that need to get resolved and lowered before it's known that the machine code will be identical.

Re: You can't fool the optimizer

#132

Post by titzer »

amelius wrote: post #6

One undesirable property of optimizers is that in theory one day they produce good code and the next day they don't.

These situations are known as "performance cliffs" and they are particularly pernicious in optimizing dynamic languages like JavaScript, where runtime optimization happens that depends not just on the program's shape, but its past behavior.

Re: You can't fool the optimizer

#133

Post by SpaceManNabs »

valleyer wrote: post #103
stabbles wrote: post #85

Earlier quoted context omitted.

The 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.

No, the compiler may assume that the behavior of standard library functions is standards-conformant.

> No, the compiler may assume that the behavior of standard library functions is standards-conformant.

Why?

What happens if it isn't?

Re: You can't fool the optimizer

#134

Post by DannyBee »

SpaceManNabs wrote: post #133
valleyer wrote: post #103

Earlier quoted context omitted.

No, the compiler may assume that the behavior of standard library functions is standards-conformant.

> No, the compiler may assume that the behavior of standard library functions is standards-conformant. Why? What happens if it isn't?

Because 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

Re: You can't fool the optimizer

#135

Post by [deleted] »

WalterBright wrote: post #110
abainbridge wrote: post #80

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 n…

`s` may be null, and so the strlen may seg fault.

[deleted]

Re: You can't fool the optimizer

#136

Post by cibyr »

commandlinefan wrote: post #81
abainbridge wrote: post #80

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 n…

> 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.

The 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/Refe...

Andy Wingo (of course!) has a good explanation of this: https://wingolog.org/archives/2012/01/12/javascript-eval-con...

Re: You can't fool the optimizer

#137

Post by DannyBee »

WalterBright wrote: post #115

There are general optimizations, based on DFA (Data Flow Analysis). These recognize things like loops, loop invariants, dead code, copy propagation, constant propagation, common subexpressions, etc. Then, there are is a (very long) list of checks for specific patterns and replacing them with shorter sequences of code, things like recognizing the pattern of bswap and replacing it with a bswap instruction. There's no e…

This is true but there is actually an end ;)

There are limits on provable equivalence in the first place. things like equality saturation also try and do a better job of formalizing equivalence based rewrites.

Re: You can't fool the optimizer

#138

Post by DannyBee »

adwn wrote: post #70
DullPointer wrote: post #56

Earlier quoted context omitted.

I’m not a compiler expert, an assembly expert or an ARM expert, so this may be wildly wrong, but this looks optimized to me. The trick is that it’s doing both the add and the left shift in parallel then selecting which to use based on a compare of the two values with csel. (To see this, rather than reading the code sequentially, think of every instruction as being issued at the same time until you hit an instruction…

> this looks optimized to me. It's not. Why would lsl+csel or add+csel or cmp+csel ever be faster than a simple add? Or have higher throughput? Or require less energy? An integer addition is just about the lowest-latency operation you can do on mainstream CPUs, apart from register-renaming operations that never leave the front-end.

In the end, the simple answer is that scalar code is just not worth optimizing harder these days. It's rarer and rarer for compilers to be compiling code where spending more time optimizing purely scalar arithmetic/etc is worth the payback.

This is even true for mid to high end embedded.

Re: You can't fool the optimizer

#139

Post by DannyBee »

jcranmer wrote: post #69
jmcomets wrote: post #47

Obvious caveat: pushing this a bit further it can quickly fallback to the default case. The optimizer is a superpower but you still need to try to write efficient code. unsigned add_v5(unsigned x, unsigned y) { if (x == y) return 2 * x; return x + y; } Results in: add_v5(unsigned int, unsigned int): lsl w8, w0, #1 add w9, w1, w0 cmp w0, w1 csel w0, w8, w9, eq ret (armv8-a clang 21.1.0 with O3) If compiler folks can c…

> If compiler folks can chime in, I'm curious why incrementing in a loop can be unrolled and inspected to optimize to an addition, but doubling the number when both operands are equal can't? Compilers are essentially massive towers of heuristics for which patterns to apply for optimization. We don't throw a general SMT solver at your code because that takes way too long to compile; instead, we look at examples of act…

This is all true. Additionally, the payback from optimizing purely scalar arithmetic harder has gone down more and more over time compared to almost anything else.

For example, eliminating an extra load or store is often worth more than eliminating 100 extra arithmetic operations these days.

Re: You can't fool the optimizer

#140

Post by MindSpunk »

SpaceManNabs wrote: post #133
valleyer wrote: post #103

Earlier quoted context omitted.

No, the compiler may assume that the behavior of standard library functions is standards-conformant.

> No, the compiler may assume that the behavior of standard library functions is standards-conformant. Why? What happens if it isn't?

Sadness. 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.

Post reply on HN