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

161–170 of 193 posts

Re: You can't fool the optimizer

#161

Post by abainbridge »

SkiFire13 wrote: post #118
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…

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

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

Re: You can't fool the optimizer

#162

Post by inkyoto »

senfiaj wrote: post #62

I wonder if compilers do multiple passes on the intermediate code in order to optimize / simplify it. For example, during each pass the optimizer searches some known harcoded patterns and replaces them with something else and repeats until no possible improvement is found. Also optimizers have a limit, they can't reason as abstractly as humans, for example: bool is_divisible_by_6(int x) { return x % 2 == 0 && x % 3 =…

> So no, there are plenty of easy ways to fool the optimizer by obfuscation.

If you mean fooling the compiler by the source code obfuscation, it won't – by the time the first optimisation pass arrives, the source had already been transformed into an abstract syntax tree and the source code obfuscation becomes irrelevant.

Multiple optimiser passes do take place, but they are bounded in time – it is not an accepted expectation that the optimiser will spend a – theoretically – indefinite amount of time trying to arrive at the most perfect instruction sequence.

There was a GNU project a long time ago, «superoptimiser», which, given a sequence of instructions, would spend a very long time trying to optimise it into oblivion. The project was more of an academic exercise, and it has been long abandoned since.

Re: You can't fool the optimizer

#163

Post by delta_p_delta_x »

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…

> but some compilers don't: 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

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.

Re: You can't fool the optimizer

#165

Post by mattnewport »

anonymousiam wrote: post #149

Sometimes you can fool the (C) optimizer by using the 'volatile' keyword in front of a variable in code that would otherwise be optimized out. https://www.embeddedrelated.com/thread/4749/when-and-how-to-...

That's not really "fooling" the optimizer, that's kind of the point of volatile. The optimizer not making optimizations is the intended behaviour.

Re: You can't fool the optimizer

#166

Post by raluk »

Years ago I wrote c++ library for stream compostion. Something like C++20 ranges. It turns out that as long as you compose everything with lambdas, compiled code is same as it would be with naive loops. Everything gets optimised.

For example, you can write sum of numbers less than n as:

  count(uint64_t(0)) 
   | take(n) 
   | sum();
Clang converted this into n*(n-1)/2.

Re: You can't fool the optimizer

#167

Post by eigenspace »

stabbles wrote: post #23

For people who enjoy these blogs, you would definitely like the Julia REPL as well. I used to play with this a lot to discover compiler things. For example: $ julia julia> function f(n) total = 0 for x in 1:n total += x end return total end julia> @code_native f(10) ... sub x9, x0, #2 mul x10, x8, x9 umulh x8, x8, x9 extr x8, x8, x10, #1 add x8, x8, x0, lsl #1 sub x0, x8, #1 ret ... it shows this with nice colors rig…

Another nice thing in julia is that if you dont want the optimizer to delete something, you can just ask it nicely :)

    julia> function f(n)
             total = 0
             for x in 1:n
               total += Base.donotdelete(x)
             end
             return total
           end
will keep the loop

Re: You can't fool the optimizer

#168

Post by astrange »

adrianN wrote: post #106
astrange wrote: post #104

Earlier quoted context omitted.

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.

I don't think anyone actually bothers to do that tbh.

Re: You can't fool the optimizer

#169

Post by 1718627440 »

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.

It does. The meaning of certain functions are prescribed by the C standard and the compiler is allowed to expect them to have certain implementations. It can replace them with intrinsics or even remove them entirely. It is of course different for a freestanding implementation.

Re: You can't fool the optimizer

#170

Post by 1718627440 »

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?

What happens when you change random functions in your C compiler? The C standard library and compiler are not independent, both make up a C implementation, which behaviour is described by the C standard.
Post reply on HN