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

Why is 2 * (i * i) faster than 2 * i * i in Java?

stackoverflow.com

Post reply on HN
Print view View original

61–70 of 109 posts

Re: Why is 2 * (i * i) faster than 2 * i * i in Java?

#61

Post by bnegreve »

fragmede wrote: post #53
bnegreve wrote: post #41

I don't see how generating different code for the same mathematical expression can be a good thing. The compiler should detect that the two expressions are strictly equivalent and generate whatever code it believes is the fastest. Any idea why it is this way?

Ideologically, yes, the compiler should generate the fastest code possible for the same math expression. However, the compiler ('s optimization step) is not magic and produces suboptimal code sometimes. Back when C was young, this was frequently the case (1970's and 1980's), so dropping into assembly to hand-code performance critical sections is just what people did, in order to get software to run smoothly. Thankful…

> However, the compiler ('s optimization step) is not magic and produces suboptimal code sometimes.

I agree that compilers are not always perfect, but in this particular case the two expressions are trivially equivalent from the associativity of the multiplication so the distinction had to be intentional.

But as gnuvince pointed out, the two expressions are not equivalent when you consider integer overflow.

Re: Why is 2 * (i * i) faster than 2 * i * i in Java?

#62

Post by bjoli »

bjoli wrote: post #33
pcwalton wrote: post #15

Earlier quoted context omitted.

> In my experience, loop unrolling should basically never be done except in extremely degenerate cases Not true. Like many such optimizations, loop unrolling can be useful because it makes downstream loads constant. For example: float identity[4][4]; for (unsigned y = 0; y In this case, the compiler probably wants to unroll the loops so that it can straightforwardly forward the constant matrix entries directly to the…

I didn't understand dead elimination until I wrote enough macros. It is a lot easier to generate code and have the optimizer fix it than to make sure to always generate efficient code. This is also how compilers do things, but it is only that we schemers can see the intermediate result much easier using simple source->source transformations.

As an example: I wrote a clone of racket's for loops. They use #:when and #:break clauses. Instead of generating them when they were present the break clauses just defaulted to #f and the when clauses to #t, meaning that the break clause of the generated code was just optimized away if the user didn't have any break clauses and the test for the when clauses was optimized to a regular (begin ...).

It simplified the code a lot and the optimizer was a lot faster than having to do it all myself at expansion time. I lazily just generate about 30 lines of code for a simple loop that in the end sometimes even is unrolled to the final reault due to guiles optimizer and partial evaluation.

Re: Why is 2 * (i * i) faster than 2 * i * i in Java?

#63

Post by beeforpork »

With all the optimisations being implemented in compilers today, it is impressive to see how this opportunity to optimise is missed. Put differently, compiler writers bother about optimisations that gain 0.1% performance in some special cases, but others that could gain 20% performance are not implemented.

Why? Is this optimisation particularly difficult to implement? Or is it just missed low-hanging fruit? It sure looks easy (like: rearrange expressions to keep the expression tree shallow and left-branching to avoid stack operations).

Re: Why is 2 * (i * i) faster than 2 * i * i in Java?

#64

Post by astn »

userbinator wrote: post #11

So it's an issue of the optimizer; as is often the case, it unrolls too aggressively and shoots itself in the foot, all the while missing out on various other opportunities. In my experience, loop unrolling should basically never be done except in extremely degenerate cases; I remember not long ago someone I know who also optimises Asm remarking "it should've died along with the RISC fad". The original goal was to re…

Yeah, sometimes the compiler unrolls too much and innocent looking one-liner can be compiled into a monstrosity like this:

https://godbolt.org/z/aKtko5

Re: Why is 2 * (i * i) faster than 2 * i * i in Java?

#65

Post by [deleted] »

beeforpork wrote: post #63

With all the optimisations being implemented in compilers today, it is impressive to see how this opportunity to optimise is missed. Put differently, compiler writers bother about optimisations that gain 0.1% performance in some special cases, but others that could gain 20% performance are not implemented. Why? Is this optimisation particularly difficult to implement? Or is it just missed low-hanging fruit? It sure l…

[deleted]

Re: Why is 2 * (i * i) faster than 2 * i * i in Java?

#66

Post by nothrabannosir »

geezerjay wrote: post #23
cryptonector wrote: post #17

Earlier quoted context omitted.

Did you read TFA? The author did that (though using GCC), and the reason the optimizer does what you see is undefined behavior due to signed integer overflow.

> does what you see is undefined behavior Just to be clear, undefined behavior means the standard allows implementations to do what they they feel is the right thing to do under that scenario, and the outcome will still comply with the standard.

Undefined behaviour, in reality, means: the compiler will assume that it doesn’t happen, so whatever code path leading up to it can also (by definition) not happen and be eliminated. E.g. signed integer overflow “cannot happen” so you never need to emit code checking for it or dealing with it.

That’s the real world implication of undefined behaviour.

Re: Why is 2 * (i * i) faster than 2 * i * i in Java?

#67

Post by alkonaut »

Is Overflow UB so the compiler can choose to ignore the fact that 2x(i x i) could overflow differently from 2 x i x i?

I’m not sure it does overflow differently but I would expect overflow to behave consistently as written, and not be dependent on optimization, is that not the case?

Re: Why is 2 * (i * i) faster than 2 * i * i in Java?

#68

Post by [deleted] »

[deleted] wrote: post #65
beeforpork wrote: post #63

With all the optimisations being implemented in compilers today, it is impressive to see how this opportunity to optimise is missed. Put differently, compiler writers bother about optimisations that gain 0.1% performance in some special cases, but others that could gain 20% performance are not implemented. Why? Is this optimisation particularly difficult to implement? Or is it just missed low-hanging fruit? It sure l…

[deleted]

[deleted]

Re: Why is 2 * (i * i) faster than 2 * i * i in Java?

#70

Post by utopcell »

jepler wrote: post #5

You should translate your program to C++ and build with clang ; it turns the loop into a single constant load. https://godbolt.org/z/slznbU

GCC applies the same optimization and compiles to a single constant if overflow does not occur. To see this, you can change '1000000000' to '1000'.
Post reply on HN