Live data from Hacker News

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

stackoverflow.com

91–100 of 109 posts

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

#91

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)

Compiling to bytecode is just one of the possibilities.

Since the early days of Java, OEM vendors targeting embedded targets do support AOT compilation, with possible PGO feedback.

Some vendors like IBM, also provide similar capabilities on their regular Java toolchains.

And Maxime finally graduated as Graal/Substrate, which is also another way of compiling Java.

But all in all, everyone is transitioning to the benefits of bytecode as intermediate executable format.

Even some cool LLVM optimizations, like ThinLTO, are only possible thanks to using bytecode.

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

#92

Earlier quoted context omitted.

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…

Just run benchmarks with -fno-unroll-loops and see what damage it does to performance.

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

#93
post #64

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

Is that more performant?

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

#94

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…

The truth is that the hotspot computer is pretty old at this point and never really implemented a lot of good, robust, and thorough optimizations (I've read the source every year or two). It does some stuff and hopes for the best.

This is why there is a real commercial jvm market with azul.

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

#95

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?

Nothing you can do in pure Java code is UB in the C/C++ sense.

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

#96

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.

The two expressions are equivalent, even under overflow. With a few exceptions (eg division, right shift) fixed size integer math follows the same associative rules as "standard math".

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

#97
post #78

Earlier quoted context omitted.

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

thank you for this!

Go’s an OK language but

1) This is not the forum to bring it up

2) Given its warts it gets FAAAARRRRR too much attention IMHO

Sorry for snark.

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

#98
post #9

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

It is a good answer, but my favorite by far is an answer about branch prediction to explain why processing a sorted array is faster than unsorted: https://stackoverflow.com/q/11227809/938695

truly full-stack!

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

#100

Earlier quoted context omitted.

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…

You are right, the vast majority of loops should be left without unrolling. In fact, the majority of code should be compiled for size, not for speed. For a typical application you probably have 99% of the code not being very performance sensitive, and the remaining 1% is where the time is spent. Still, people regularly compile for speed to good effect, because it's so important to compile that 1% for speed that you are better off just compiling everything that way if you aren't able/willing to profile and figure what code falls in the 1%.

That's nothing specific to unrolling though: it applies to all optimizations which trade off size and speed.

About dependency chains and ILP: of course the compiler is in the perfect places to be aware of all of this. They have detailed machine models updated carefully as new CPUs come out (in fact, some of the earliest details about new CPU models often comes from compiler commits from insiders where hardware details are necessarily leaked).

A compiler could certainly statically analyze a loop using an approach similar to Intel IACA or OASCA [1], and then unroll the loop a few times and run the analysis again and see if it improves. So it doesn't need any kind of sophisticated analysis, just try-and-measure. Of course, compilers don't actually work like this. One of reasons it is not so easy is that optimizations is done in layers, against a machine independent IR, and you might not be able to carefully evaluate the impact of unrolling until some later time, possibly as late the machine-dependent instruction emission. This issue is pervasive across many compiler optimizations, and leads to many cases where a compiler generates bad code where a human wouldn't.

---

[1] https://github.com/RRZE-HPC/OSACA

Post reply on HN