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

51–60 of 109 posts

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

#51

Post by bnegreve »

gnuvince wrote: post #48
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?

Because of integer overflows and floating-point operations, the notion of equivalent mathematical expressions is tricky. fn main() { let a: i8 = 125; let b: i8 = 3; let c: i8 = (a + b) / 2; let d: i8 = b + ((a - b) / 2); println!("{} {}", c, d); } This program outputs `-64 64` although the computations of `c` and `d` are equivalent. Here's another example using floating point numbers: fn main() { let mut total1: f32…

Right! thanks

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

#53

Post by fragmede »

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.

Thankfully this is largely no longer the case, however it does still happen.

In Java's case, the JVM runs on top of multiple different architectures which makes optimization even more complicated.

Low-level instruction generation and optimization is just one topic under the umbrella of compiler design, which is a huge (and fascinating!) discipline to get into.

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

#54

Post by kannanvijayan »

pcwalton wrote: post #15
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…

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

> (You might ask "who would write this code?" As Schemers say: "macros do.")

To expand on this point - in the more prosaic world of C++ - this sort of code comes about all the time in templated code. For example, the above loop you posted might have been found in something like:

``` template class Matrix { static Matrix Identity() { ... } }

    auto m = Matrix::Identity();
```

The other major source of these sorts of constants leading to DCE oppportunities is inlining. Consider a more classical, matrix implementation that is not templated and doesn't lift its dimensions into the type:

``` class Matrix { unsigned n; unsigned m; static Matrix Identity(unsigned n, unsigned m) { ... } }

    // Somewhere else
    Matrix m = Matrix::Identity(4, 4);
```

Here, the inlining of the call to `Identity` at the call-site will turn the `n` and `m` in the body of `Identity` into the constant 4.

If I had to make an educated guess - inlining typically generates these (i.e. partial evaluation, constant folding, an DCE) situations most often in compilers. An incredible amount of information can flow from caller to callee when you specialize the callee for that call-site.

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

#55

Post by dreamcompiler »

garmaine wrote: post #21
dreamcompiler wrote: post #16

I thought at first this was because integer squaring is potentially faster than general integer multiplication and the compiler wasn't seeing the square operation in the second case, but that's not the explanation here.

There isn’t an integer square opcode on any major processor architecture though, right?

Not that I know of. It's not really worth it for short integers (64 bits or less). But it's helpful with bignums.

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

#56

Post by pmarreck »

falcor84 wrote: post #40
techopoly wrote: post #2

That just might be the most dedicated answer I've ever seen on Stack Overflow.

It really was, but as others mentioned, there's a lot of really good stuff on Stack Overflow and Stack Exchange in general. This is my favorite: https://codegolf.stackexchange.com/questions/11880/build-a-w...

Oh my god.

https://copy.sh/life/?pattern=TetrisOTCAMP.mc

OH MY GOD!

My eyes are watering and I can’t stop deeply chuckling at the sheer collaborative esoteric audacity

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

#57

Post by Sharlin »

tomsmeding wrote: post #30
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…

In addition to the optimisations already mentioned, loop unrolling also typically enables vectorisation in compilers. You might argue that for vectorisation it is not exactly necessary to have the relevant oerations next to each other in a continuous instruction stream, but it makes the vectorisation pass a lot nicer and simpler (if it can be called that to begin with).

Assuming you unroll just enough to fill a SIMD lane. As mentioned, in this case aggressive (16-fold) unfolding actually appears to have prevented vectorization. (A smart enough vectorizer could of course handle this but unrolling just to ”re-roll” in a later pass doesn’t sound very smart.)

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

#58

Post by pmarreck »

Veedrac wrote: post #39
techopoly wrote: post #2

That just might be the most dedicated answer I've ever seen on Stack Overflow.

Then you'll love https://stackoverflow.com/questions/37361145/deoptimizing-a-...

Takeaway phrases from this I love:

“Pessimization”

“Diabolical incompetence”

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

#60

Post by stochastic_monk »

pcwalton wrote: post #15
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…

> 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 had a case where I was counting occurrences of 8-bit integer values. Manual loop unrolling provided a 33% speed up.
Post reply on HN