17 ms·
Why is 2 * (i * i) faster than 2 * i * i in Java?
- techopoly 8y agoThat just might be the most dedicated answer I've ever seen on Stack Overflow.
- azhenley 8y agoIt 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 https://stackoverflow.com/q/11227809/938695
- dopamean 8y agoWow that was a great read.
- fma 8y agoI find it interesting that there are developers out there that know to look at these nuances when respond to Stack Overflow questions. I'm been developing professionally for 10 years and probably went over branch prediction in my computer architecture class in college (I'm guessing I did, if I didn't then I never encountered it at all!). The person who answered the multiple question dove into byte code...but also answered questions on Angular. I am unworthy...and this is what impostor syndrome looks like.
- deleted 8y ago[deleted]
- Illniyar 8y agoThat person works in financial services, which I'm guessing is basically some form of automated trading. It is an industry where every cycle counts (so much so, that often times light speed latency between two edges is something you need to consider when placing servers). He probably has actual experience with branch prediction. He probably dabbled or had experience with angular in other jobs (he worked at google apparently, so maybe there). He'll most likely be stumped if you provide a graphic problem that a graphic designer with a few years of experience would solve in an instant, or an ML problem for a data scientist with similar experience. That doesn't mean he isn't extremely smart. He most likely is (it takes a lot of brain to do these things), but the fact that you can't tell branch prediction problems even though you had some computer architecture class in the past is irrelevant.
- saagarjha 8y agoThe author of that answer wrote y-cruncher, which has been used to set world records in the number of digits of pi calculated. So I'm not surprised at all to see that they how know branch prediction works.
- aristophenes 8y ago> they how know branch prediction works. Can’t tell if clever joke, or typo
- saagarjha 8y agoTypo, but I'll leave it up to brighten someone else's day.
- icebraining 8y agoI don't see anything regarding Angular, they're obviously very knowledgeable, but it's pretty much focused on low-level: https://stackoverflow.com/users/922184/mysticial?tab=tags&sort=votes https://stackoverflow.com/users/922184/mysticial?tab=tags&so...
- fma 8y agoI think these are his responses https://stackoverflow.com/users/485343/rustyx https://stackoverflow.com/users/485343/rustyx He answered a question on ticking clock in Angular.
- icebraining 8y agoOh, my mistake, I thought we were talking about the question linked by azhenley above.
- garmaine 8y agoWould be awesome if that answer was updated to explain Spectre (it’s 85% of the way there).
- foobaw 8y agotruly full-stack!
- Veedrac 8y agoThen you'll love https://stackoverflow.com/questions/37361145/deoptimizing-a-program-for-the-pipeline-in-intel-sandybridge-family-cpus/ https://stackoverflow.com/questions/37361145/deoptimizing-a-...
- pmarreck 8y agoTakeaway phrases from this I love: “Pessimization” “Diabolical incompetence”
- falcor84 8y agoIt 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-working-game-of-tetris-in-conways-game-of-life https://codegolf.stackexchange.com/questions/11880/build-a-w...
- pmarreck 8y agoOh my god. https://copy.sh/life/?pattern=TetrisOTCAMP.mc 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
- crb002 8y agoTIL about printing ASM from debug JVMs.
- pjmlp 8y agoIf you use Oracle Studio you can even see it on the IDE. https://www.youtube.com/watch?v=_cFwDnKvgfw https://www.youtube.com/watch?v=_cFwDnKvgfw There are also other tools like JITWatch. https://github.com/AdoptOpenJDK/jitwatch/wiki/Videos-and-Slideshows https://github.com/AdoptOpenJDK/jitwatch/wiki/Videos-and-Sli... https://vimeo.com/181925278 https://vimeo.com/181925278
- ww520 8y agoI'm surprised it's not doing a left shift for the x2.
- jcdavis 8y agoIt is in the first example (the sal instruction)
- DannyBee 8y agoHowever, if you look at the second, you won't see any left shifts, which is also interesting
- ascar 8y agoI find it weird that he doesn't mention this difference as part of the performance difference. A left shift should be considerably faster than a mul operation?
- foldr 8y agoI don't think this is generally true on modern processors.
- acdha 8y agoI believe this is far less true than it used to be, but it’s a good example of why these decisions really need to be data driven as compilers and processors change faster than most people can afford to optimize code. I don’t know that this would be the case for something that simple but I’ve seen a fair amount of heavily-tuned C/ASM code which was replaced with the now-faster “reference” code when someone noticed that the old assumptions weren’t true.
- deleted 8y ago[deleted]
- jepler 8y agoYou should translate your program to C++ and build with clang ; it turns the loop into a single constant load. https://godbolt.org/z/slznbU https://godbolt.org/z/slznbU
- ychen306 8y agoIt's usually a good idea to turn loop bound into a variable when benchmarking a compiler, lest it optimizes the whole thing away like in this case.
- archgoon 8y agoNope; doesn't work for clang. Clang actually detects and compiles the algebraic closed form sum(i^2, n) for a bound n.
- trogdc 8y agoYou'd have to use "volatile int n"
- Too 8y agoSo if the compiler is too good you want to trick it to produce less optimal code so you can benchmark it fairly? Isn't it part of the benchmark to allow the compiler reduce the whole expression to a compile time constant?
- TeMPOraL 8y agoYou want the loop to not be optimized away because the loop itself is not a part of benchmarked code, it's the benchmarking code. It executes the same thing million+ times so that the total execution time is much higher than timer measurement error, measurement overhead and random OS fluctuations, that would otherwise drown your result in noise.
- hyperpape 8y agoAside from what the sibling says about the difference between the test harness code and the code being benchmarked, there's a more abstract point: you want the compiler to reduce it to a compile time constant if and only if in the real world cases you're trying to model, it will be able to do so. That's pretty rare, since if that happens, you probably wouldn't have to do performance analysis on that code. These days I find myself telling people that benchmark numbers don’t matter on their own. It’s important what models you derive from those numbers. Refined performance models are by far the noblest and greatest achievement one could get with the benchmarking — it contributes to understanding how computers, runtimes, libraries, and user code work together. --Aleksey Shipilёv https://shipilev.net/blog/2014/nanotrusting-nanotime/ https://shipilev.net/blog/2014/nanotrusting-nanotime/ That's a bit of an obscure comment, but I keep coming back to it as I learn about performance work and benchmarking.
- microcolonel 8y agoI guess they do not use value numbering, which is typically how you get equivalent results for cases like this.
- userbinator 8y agoSo 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 reduce per-iteration overhead associated with checking for end-of-loop, but any superscalar/OoO/speculative processor can "execute past" those instructions anyway; all that unrolling will do is bloat the code and work against caching. Memory bandwidth is often the bottleneck, not the core.
- pcwalton 8y ago> 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 < 4; y++) for (unsigned x = 0; x < 4; x++) identity[y][x] = y == x ? 1 : 0; ... do some matrix math ... In this case, the compiler probably wants to unroll the loops so that it can straightforwardly forward the constant matrix entries directly to the matrix arithmetic. It'll likely be able to eliminate lots of operations that way. (You might ask "who would write this code?" As Schemers say: "macros do.") See LLVM's heuristics: http://llvm.org/doxygen/LoopUnrollPass_8cpp.html#ad7c38776d74075aa393534236d5a3d64 http://llvm.org/doxygen/LoopUnrollPass_8cpp.html#ad7c38776d7...
- bjoli 8y agoI 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.
- bjoli 8y agoAs 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.
- dreamcompiler 8y agoI 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.
- garmaine 8y agoThere isn’t an integer square opcode on any major processor architecture though, right?
- dreamcompiler 8y agoNot that I know of. It's not really worth it for short integers (64 bits or less). But it's helpful with bignums.
- qwerty456127 8y agoIMHO some kind of logic preprocesor should take care of this before the actual compilation.
- isbvhodnvemrwvn 8y agoHow? 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)
- pjmlp 8y agoCompiling 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.
- idiot2 8y agoIdiot. U had to post this crap three times to get noticed and make it a discussion
- networkimprov 8y agoHas anyone tried this with Go?
- saagarjha 8y agoTried what specifically? This particular example, or something similar where the compiler generates code with different speeds for seemingly equivalent code?
- pmarreck 8y agoNo, because come back when you’re a real language with a runtime error handler
- sabujp 8y agothank you for this!
- pmarreck 8y agoGo’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.
- networkimprov 8y agoWorking on it! Requirements to Consider for Go 2 Error Handling https://gist.github.com/networkimprov/961c9caa2631ad3b95413f7d44a2c98a https://gist.github.com/networkimprov/961c9caa2631ad3b95413f...
- bnegreve 8y agoI 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?
- amelius 8y agoBecause it's more work for the compiler to reduce the expression to something canonical (and it might even be impossible). Also what good will it bring? What if the canonical expression triggers the slow path? Now you have no means to change it into the fast version. Further, in the case of floating point operations, operation order matters for rounding. And with integer operations, the actual form used can be important for preventing overflow (of intermediate results).
- gnuvince 8y agoBecause 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 = 0.0; let mut total2: f32 = 0.0; let mut counter1: f32 = 0.0; let mut counter2: f32 = 100.0; for _ in 0 .. 10001 { total1 += counter1; total2 += counter2; counter1 += 0.01; counter2 -= 0.01; } println!("{} {}", total1, total2); } The output of this program is `500041.16 500012.16`, a difference of 25 for a program that computes the same result (unless I made a mistake).
- bnegreve 8y agoRight! thanks
- liftbigweights 8y agoThe 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.
- polskibus 8y agoI wonder if the same applies to .net (fx/core).
- pjmlp 8y agoDepends 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.
- beeforpork 8y agoWith 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).
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- yifanl 8y agoIt's possible that they're working in the frame of mind that there aren't any low-hanging fruit left after so many years of compiler optimizations and forget to even try.
- acdha 8y agoCompiler developers have tons of benchmarks which they run. I’d bet that this is as simple as not being significant in their test suite, with a good chance that it’s both not as simple as it might seem or that there are impacts on more complicated code which is in their benchmark suite or a big customer’s app.
- DannyBee 8y agoThe 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.
- alkonaut 8y agoIs 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?
- BeeOnRope 8y agoNothing you can do in pure Java code is UB in the C/C++ sense.
- alkonaut 8y agoWithout UB it must be very hard for the compiler to optimize arithmetic. Even obvious things like (2 x A) x B vs 2 x (A x B) are only equivalent without overflow. I guess it can be specified as being up to the jitter to decide - so not UB but not known from looking at the source either? Would be interesting to know what .NET and Java specifications say on it
- BeeOnRope 8y agoYou can usually optimize integer arithmetic just fine, including the example you gave (both forms are equivalent - try it!). Floating point arithmetic is different, but Java gives itself wiggle room by not exactly specifying many results unless you choose "strict math". That's not UB though: it's just a range of possible outcomes. Java can't have UB in the C/C++ sense, since it would break the security sandbox. It certainly has things without specifically defined values, such as hashCode() and what happens under data races isn't entirely deterministic, but it doesn't approach UB in the C/C++ sense.
- alkonaut 8y agoYeah I’m painfully aware of the FP gotchas. But are you saying there are usually never any issues with integer arithmetic and overflow vs. optimizations (reordering, common subexpressions etc)? A branch like “if a+1 < a” seems like it could under a clever compiler (allowed to do what it wants in unchecked overflow) optimize to a completely removed branch but with less optimization it will not, so the addition is carried out and the wraparound means the branch is entered? Seems that not checking for overflow and not being able to assume there is no overflow, would give the worst of both worlds (slower because of lack of some optimizations but still not safe against overflow like C#’s “checked”). I thought a deref of a possibly overflown value was what could risk security, ie so long as all array indices and similar are range checked then nothing bad can happen?
- openloop 8y agoBecause Java is shitty.
- JohnL4 8y agoThe database is fast enough for a few extra trips to it, so this is definitely what we should be focusing on. (My cup of bitterness doth overflow.)
- Koshkin 8y agoAt first, I thought it was because i * i == -1.
- podsnap 8y agoThe graal behavior is a lot more sane: graal: [info] SoFlow.square_i_two 10000 avgt 10 5338.492 ± 36.624 ns/op // 2 *\sum i * i [info] SoFlow.two_i_ 10000 avgt 10 6421.343 ± 34.836 ns/op // \sum 2 * i * i [info] SoFlow.two_square_i 10000 avgt 10 6367.139 ± 34.575 ns/op // \sum 2 * (i * i) regular 1.8: [info] SoFlow.square_i_two 10000 avgt 10 6393.422 ± 27.679 ns/op [info] SoFlow.two_i_ 10000 avgt 10 8870.908 ± 35.715 ns/op [info] SoFlow.two_square_i 10000 avgt 10 6221.205 ± 42.408 ns/op The graal-generated assembly for the first two cases is nearly identical, featuring unrolled repetitions of sequences like [info] 0x000000011433ec03: mov %r8d,%ecx [info] 0x000000011433ec06: shl %ecx ;*imul {reexecute=0 rethrow=0 return_oop=0} [info] ; - add.SoFlow::test_two_i_@15 (line 41) [info] 0x000000011433ec08: imul %r8d,%ecx ;*imul {reexecute=0 rethrow=0 return_oop=0} [info] ; - add.SoFlow::test_two_i_@17 (line 41) [info] 0x000000011433ec0c: add %ecx,%r9d ;*iadd {reexecute=0 rethrow=0 return_oop=0} [info] ; - add.SoFlow::test_two_i_@18 (line 41) [info] 0x000000011433ec0f: lea 0x5(%r11),%r8d ;*iinc {reexecute=0 rethrow=0 return_oop=0} [info] ; - add.SoFlow::test_two_i_@20 (line 40) while the third case does a single shl at the end. [info] 0x000000010e2918bb: imul %r8d,%r8d ;*imul {reexecute=0 rethrow=0 return_oop=0} [info] ; - add.SoFlow::test_square_i_two@15 (line 32) [info] 0x000000010e2918bf: add %r8d,%ecx ;*iadd {reexecute=0 rethrow=0 return_oop=0} [info] ; - add.SoFlow::test_square_i_two@16 (line 32) [info] 0x000000010e2918c2: lea 0x3(%r11),%r8d ;*iinc {reexecute=0 rethrow=0 return_oop=0} [info] ; - add.SoFlow::test_square_i_two@18 (line 31) Both graal and C2 inline, but as usual the graal output is a lot more comprehensible.