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

101–110 of 193 posts

Re: You can't fool the optimizer

#101

Post by abbeyj »

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…

> We all know that strlen will return 5, but some compilers don't: 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.

Re: You can't fool the optimizer

#102

Post by gfaster »

thaumasiotes wrote: post #52
matja wrote: post #29

You can fool the optimizer, but you have to work harder to do so: unsigned add(unsigned x, unsigned y) { unsigned a, b; do { a = x & y; b = x ^ y; x = a becomes (with armv8-a clang 21.1.0 -O3) : add(unsigned int, unsigned int): .LBB0_1: ands w8, w0, w1 eor w1, w0, w1 lsl w0, w8, #1 b.ne .LBB0_1 mov w0, w1 ret

Since I had to think about it: unsigned add(unsigned x, unsigned y) { unsigned a, b; do { a = x & y; /* every position where addition will generate a carry */ b = x ^ y; /* the addition, with no carries */ x = a It's easy to show that this algorithm is correct in the sense that, when b is returned, it must be equal to x + y . x + y summing to a constant is a loop invariant, and at termination x is 0 and y is b . It's…

In C, I'm pretty confident the loop is defined by the standard to terminate.

Also I did take the excuse to plug it (the optimized llvm ir) into Alive:

https://alive2.llvm.org/ce/#g:!((g:!((g:!((h:codeEditor,i:(f...

Re: You can't fool the optimizer

#103

Post by valleyer »

stabbles wrote: post #85
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…

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.

Re: You can't fool the optimizer

#104

Post by astrange »

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.

A JIT can do any optimization it wants, as long as it can deoptimize if it turns out it was wrong.

Re: You can't fool the optimizer

#105

Post by adwn »

DullPointer wrote: post #75
adwn wrote: post #70

Earlier quoted context omitted.

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

ARM is a big target, there could be cpus where lsl is 1 cycle and add is 2+. Without knowing about specific compiler targets/settings this looks reasonable. Dumb in the majority case? Absolutely, but smart on the lowest common denominator.

> Without knowing about specific compiler targets/settings this looks reasonable.

But we do, armv8-a clang 21.1.0 with O3, and it doesn't.

> […] but smart on the lowest common denominator.

No, that would be the single add instruction.

Re: You can't fool the optimizer

#106

Post by adrianN »

astrange wrote: post #104
commandlinefan wrote: post #81

Earlier quoted context omitted.

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

A JIT can do any optimization it wants, as long as it can deoptimize if it turns out it was wrong.

You also want to prove that the „optimization“ doesn’t make things slower.

Re: You can't fool the optimizer

#107

Post by j2kun »

Findecanor wrote: post #71

I'm wondering how the compiler optimised add_v3() and add_v4() though. Was it through "idiom detection", i.e. by recognising those specific patterns, or did the compiler deduce the answers them through some more involved analysis?

Scalar Evolution is one way loops can be simplified

Re: You can't fool the optimizer

#108

Post by moregrist »

jagged-chisel wrote: post #2

I always code with the mindset “the compiler is smarter than me.” No need to twist my logic around attempting to squeeze performance out of the processor - write something understandable to humans, let the computer do what computers do.

There are optimizations that a compiler can perform; usually these are code transformations. Modern optimizing compilers usually get these right.

The optimizations that tend to have the most impact involve changes to the algorithm or data layout. Most compilers won’t do things like add a hash table to make a lookup O(1) or rearrange an array of structures to be a structure of arrays for better data locality. Coding with an eye for these optimizations is still a very good use of your time.

Re: You can't fool the optimizer

#109

Post by abainbridge »

abbeyj wrote: post #101
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…

> We all know that strlen will return 5, but some compilers don't: 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.

Fair point. It doesn't do the optimization if you ask to optimize for size '/Os' either.

Re: You can't fool the optimizer

#110

Post by WalterBright »

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.
Post reply on HN