Why is 2 * (i * i) faster than 2 * i * i in Java? • Hacker News Board

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

#81

Post by liftbigweights » Sat, Dec 01, 2018, 5:51 PM UTC

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…

The difference is that with fp ops, it's part of the design and understood that you should never directly compare the equality of fp numbers since they are estimates. You should check for equality of fp numbers by checking their difference according to your needs.

Whereas for int ops, equality works within the limits of the design.

In short equality means something different in fp by design. For int, it means what we think it means within its limits. When we overflow, then things get screwy.

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

#82

Post by networkimprov » Sat, Dec 01, 2018, 5:54 PM UTC

pmarreck wrote: post #59

networkimprov wrote: post #38

Has anyone tried this with Go?

No, because come back when you’re a real language with a runtime error handler

Working on it!

Requirements to Consider for Go 2 Error Handling

https://gist.github.com/networkimprov/961c9caa2631ad3b95413f...

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

#83

Post by [deleted] » Sat, Dec 01, 2018, 6:22 PM UTC

berti wrote: post #45

geezerjay wrote: post #23

Earlier quoted context omitted.

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

No, that's implementation defined behaviour.

[deleted]

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

#84

Post by isbvhodnvemrwvn » Sat, Dec 01, 2018, 6:24 PM UTC

qwerty456127 wrote: post #28

IMHO some kind of logic preprocesor should take care of this before the actual compilation.

How? Java is compiled to bytecode, you don't know the architecture of the system the code is going to run on. It's one of the reasons javac only implements the simplest optimizations possible (constants folding and the like)

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

#85

Post by pjmlp » Sat, Dec 01, 2018, 6:24 PM UTC

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…

While true, and I still remember those days, when many C code bases were full functions whose body was a big asm { ... } block, there were also compilers which were much better dealing with optimizations than those C compilers were capable of.

"An overview of the PL.8 compiler"

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.453...

Notice the architecture, quite similar to the layers and compiler phases used in modern compiler toolchains like LLVM.

The secret sauce, if one can call it as such, was that PL.8 had a richer type system, and the System/370 was a bit beefier than most platforms adopting C compilers.

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

#86

Post by BeeOnRope » Sat, Dec 01, 2018, 6:27 PM UTC

dragontamer wrote: post #24

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…

Fully agree. In most cases on modern systems, small loops should remain compact as possible, to stay in the uop cache. The "for" loop overhead (the inc, cmp, and jmp instructions) effectively execute in parallel. Modern systems are highly out-of-order and the for-loop overhead is virtually nil.

Actually unrolling is often very important. In some cases it is even more important with modern high speed out-of-order cores. For example, you might need several accumulators to handle instruction or memory latency.

For small loops, unrolling is the most important of all, since loop carried dependency chains are dense, and the loop overhead is a high fraction of the overall work.

It is easy to get a 2x speedup by unrolling a small loop, and even larger speedups are not uncommon.

So this "unrolling rarely helps" idea is just as much of a myth as "unrolling never helps". The main problem with unrolling is that the compilers usually don't do it intelligently - usually loops are unrolling if some kind of threshold is met, depending on compiler options - but this always happens in kind of a feed-forward way, rather thank a feed-back way, which would involve unrolling the loop and analyzing the benefit and costs after further optimization passes.

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

#87

Post by pjmlp » Sat, Dec 01, 2018, 6:29 PM UTC

polskibus wrote: post #52

I wonder if the same applies to .net (fx/core).

Depends on the runtime.

You have the old JIT, replaced by RyuJIT on .NET 4.6 and .NET Core.

Then .NET Native, which does AOT compilation via the same backend as Visual C++.

Followed by Mono's JIT/AOT implementation.

Windows/Windows Phone 8.x used a Bartok derived compiler for the MDIL format.

Same applies to Java though, as the answer only goes through what Hotspot does, but there are many other JIT/AOT compilers for Java as well.

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

#88

Post by isbvhodnvemrwvn » Sat, Dec 01, 2018, 6:33 PM UTC

bnegreve wrote: post #61

fragmede wrote: post #53

Earlier quoted context omitted.

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.

Multiplication of floating-point numbers is not associative. Take for instance:

* 0.5 * 2

When evaluated like that:

( * 0.5) * 2

the result is 0 * 2 = 0

And when evaluated the other way around:

* (0.5 * 2)

the result is * 1 =

    double sppn = Double.MIN_VALUE;

    double first = sppn * (0.5 * 2);
    double second = (sppn * 0.5) * 2;

    System.out.println(sppn);
    System.out.println(first);
    System.out.println(second);

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

#89

Post by MauranKilom » Sat, Dec 01, 2018, 6:34 PM UTC

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 behavior is "literally anything can happen". So yes, implementations doing "what they feel is the right thing to do" is one possible result of UB (as in this case). It could also emit an rm -rf / call and it would still comply with the standard...

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

#90

Post by dragontamer » Sat, Dec 01, 2018, 6:34 PM UTC

BeeOnRope wrote: post #86

dragontamer wrote: post #24

Earlier quoted context omitted.

Fully agree. In most cases on modern systems, small loops should remain compact as possible, to stay in the uop cache. The "for" loop overhead (the inc, cmp, and jmp instructions) effectively execute in parallel. Modern systems are highly out-of-order and the for-loop overhead is virtually nil.

Actually unrolling is often very important. In some cases it is even more important with modern high speed out-of-order cores. For example, you might need several accumulators to handle instruction or memory latency. For small loops, unrolling is the most important of all, since loop carried dependency chains are dense, and the loop overhead is a high fraction of the overall work. It is easy to get a 2x speedup by un…

Okay, manual loop unrolling definitely helps, but the programmer MUST be aware of dependency chains and ILP. The compiler cannot make the decision, at least not without a pragma or maybe an autovectorization engine.

At least, I haven't seen todays (2018) compilers cut dependency chains on without a #pragma omp reduce, or other assistance from the programmer.

I've unrolled loops myself to good sucess. But it isn't as easy as some people think it is.

Without knowing about dependency chains or ILP, small loops are often best left in smaller compact form. You leverage the branch predictor and minimize uop cache usage. I'd argue the typical program benefits from compact loops more.