r/programming • • Jul 05 '15

Fast as C: How to write really terrible Java

https://vimeo.com/131394615
1.1k Upvotes

394 comments sorted by

View all comments

141

u/Chaoslab Jul 05 '15

Java certainly can be very fast but the code is not mainstream standard and be considered a horror show compared to normal development.

The experience I have with it is from writing ChaoslabVJ a real video mixing app that can push 100's of millions of pixels a second.

My favorite "bad coding practice for speed" is any loop over 300 (usually pixel processing). Don't even have a loop end condition in the for loop just catch the exception when the array out of index happens. Order of magnitude faster. (Awful idea and code but hey it works).

29

u/Omnicrola Jul 05 '15

Interesting. Do you know why the speed difference occurs? (at the bytecode level)

96

u/ElFeesho Jul 05 '15

You're eliminating a conditional check for every loop. The JVM has an implicit conditional check when indexing an array which provides a check to see if an index is out of bounds.

C will not stop you accessing an incorrect index in an array, but there is also no runtime accessible information stored for an array. When you allocate an array in Java, there is associated metadata which contains the length of the array.

5

u/IJzerbaard Jul 06 '15

Doesn't indexing an array inside a for-loop over its length normally trigger bounds check elimination anyway though?

→ More replies (11)
→ More replies (1)

20

u/minime12358 Jul 05 '15 edited Jul 05 '15

I could comment. For loops have an implicit if clause that are in the third second slot.

On most CPUs, ifs are very fast, because the computer will predict the outcome based on previous outcomes. In the case of a long for loop, it will guess that it will always be true. Once it realizes it is wrong, on the last one, it backtracks.

I'm not sure exactly, but this costs around 2-3 clock cycles per correct one and 15 or so for an incorrect one. These are if the computer does this optimization.

So, for over 300, we have 615-915 clock cycles that are wasted, compared to generation of a stack trace (which is actually a lot of work for the computer). They are probably not very big time wasters in the real world, except when you get very large arrays on this happens tens to hundreds of times a second (e.g. image rendering, as he said)

This also doesn't account for the lack of if predictions. On that hardware, there would be a much larger improvement in using try catch, because ifs are more costly.

This said, there are many things you could do inside the loop to make it faster as well. Only small manipulations are hard to optimize, really. Also, doing array[i] has an implicit if clause by itself, to add to a previous point.

6

u/estomagordo Jul 05 '15

For loops have an implicit if clause that are in the third slot.

Second slot.

3

u/minime12358 Jul 05 '15

Thanks, corrected. Not sure how I missed that

3

u/Shaper_pmp Jul 05 '15

FYI, double-tilde causes strikethroughs:

~~strikethrough~~ == strikethrough

→ More replies (1)

10

u/mrjigglytits Jul 06 '15

As a computer architecture guy, a couple things to clarify slights, but mostly right:

  1. branch prediction (the term for guessing which way an if is going to go and keeping the processor running before backing up if it turns out you're wrong) exists on almost all modern processors. It's been in intel chips since the mid 80s and now is pretty much ubiquitous on any normal set of hardware your code will be running on. I'd venture to say that if you're writing for hardware specialized enough that it doesn't have branch prediction, you already know more than you'll get from a reddit post about it. Always assume it's there.

  2. Branch prediction, when it guesses right, doesn't cost any cycles, except for the 1 of the branch instruction itself. That's the whole point of branch instruction, the computer guesses on way and continues executing like nothing happened. Then, if it turns out it was wrong, it has to back up and restart at the other branch, which costs somewhere in the ballpark of 12-15 cycles.

  3. Most of the time, branch prediction is remarkably good (obviously it will depend on the code, and you can do benchmarking stuff like I'm sure OP did to decide try/catch was better), but studies show most modern ones in x86 or other widely used environments get 90+% hit rates. You can do things like lining up the data so you go one direction all the times you need to before flipping to the other (i.e. sorting a list so the internal ifs will go all one direction then all the other). In the given case though, the nature of it being a for loop will do that anyways. After the first 2-3 loops (probably before in modern stuff), it will guess that it goes into the loop every time, so it only costs you one cycle per loop, which unless you're writing super crazy optimized stuff you won't even notice. Any internal ifs, breaks, and continues will be the same whether you're using for or try/catch in terms of branch prediction, so they won't really change either way. In general, branch prediction is absolutely good enough (and is perfectly optimized for loops) to where it'll work better/well enough for whatever you're doing. It'll cost n+15 cycles, which in the whole scope of things is not a big deal in the overwhelming majority of cases. I'm not sure how expensive creating an exception is, or the cycle/memory overhead of a try/catch block, but except for very specific circumstances, I have a hard time believing it's much faster. The times where that level of code optimization is worth the readability tradeoffs are verrrrry rare.

tl;dr: Use loops, they're easier to read, they're either faster or cost so little that you shouldn't worry about it in 99.999% of cases.

7

u/Chaoslab Jul 05 '15

Optimal for a loop over 300 so when processing an HD frame 1920x1080=2073600, that is a significant performance increase.

→ More replies (16)
→ More replies (1)

38

u/Richard_Fey Jul 05 '15 edited Jul 05 '15

Do you have any evidence your favorite "bad coding practice for speed" is actually faster? I have been reading Effective Java by Joshua Bloch and he uses this as an example of one of the worst pieces of code hes ever seen (Page 241 2nd Edition). He also says "In fact, the exception-based idiom is far slower than the standard one on modern JVM implementations. On my machine, the exception-based idiom is more than twice as slow as the standard one for arrays of one hundred elements. "" The reasoning he gives is as follows:

  1. Because exceptions are designed for exceptional circumstances, there is little incentive for JVM implementors to make them as fast as explicit tests.

  2. Placing Code inside a try-catch block inhibits certain optimizations that modern JVM implementations might otherwise perform.

  3. The standard idiom for looping through an array doesn't necessarily result in redundant checks. Modern JVM implementations optimize them away.

13

u/mike_hearn Jul 05 '15

Exceptions can, in optimal scenarios, compile down to a direct jump with modern compilers I believe. So it's not infeasible that it really was faster.

2

u/UMadBreaux Jul 06 '15

Isn't generating the stack trace expensive? I know in the .net CLR it is expensive

5

u/zenflux Jul 06 '15

It is, however if the exception is ignored it is theoretically possible for compilers to see that the stacktrace generation is dead code and elide it.

→ More replies (1)
→ More replies (13)

8

u/Chaoslab Jul 05 '15

It all depends on the loop size & jvm. Once over the 10's of thousands (millions as well) what ever extra cost will be dwarfed by the execution of the loop check.

5

u/uxcn Jul 06 '15

I'm skeptical as well. Loop unrolling and vectorization generally depends on the loop condition, which relying strictly on exceptions precludes.

Also, it's smaller loops that generally have the higher relative cost for condition checks.

2

u/captainAwesomePants Jul 06 '15

That's all absolutely correct, but I could imagine some exceptions might show up for situations that involve many millions of iterations and for some reason can't be automatically optimized into iterating over an array. A sufficiently good optimization being defeated by a check that can't be optimized away for a big enough loop could be a better savings than the cost of creating and throwing an exception. Maybe. Never optimize without measuring and all that. But the resulting code would still look terrible and be confusing to read, which is ALSO a tradeoff, and a bad one in most cases.

9

u/__Cyber_Dildonics__ Jul 05 '15

Do you realize that using something like C++ and ISPC you can literally do dozens of operations on multiple billions of floating point pixels per second on a single sandy bridge core?

6

u/headius Jul 05 '15

There's work happening on OpenJDK to do the same thing without requiring a lot of gymnastics from users. They've managed to do GPU and SIMD-based processing of plain Java arrays/matrices without users having to write specialized code. Unreleased, but exciting.

33

u/__Cyber_Dildonics__ Jul 05 '15

I've been hearing promises like this from Java for literally two decades, so I'll believe it when I see it.

I wonder how they will get around the array bounds checking if it is going to work the same?

9

u/mike_hearn Jul 05 '15

Intel has been directly implementing the support in recent times, e.g.

http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/2015-April/017631.html

I think people always overestimate how quickly compilers can get better though. It does seem to take forever.

One interesting project in the JVM world right now is Graal. It rewrites the HotSpot compilers, in Java (boggle). The app starts with the compiler compiling itself. They plan to have AOT compilation as part of it to avoid this overhead at some point. But the idea is that it becomes a lot easier to implement new fancy compiler technologies and refactorings when you aren't writing it in C++.

6

u/[deleted] Jul 06 '15

It rewrites the HotSpot compilers, in Java (boggle).

What is with the boggle? Most things are written in themselves. C is written in C. Java is written in Java. Scala is written in Scala.

→ More replies (3)
→ More replies (1)

2

u/_zenith Jul 06 '15

.NET does this now :-)

→ More replies (13)

4

u/shipmyweiners Jul 06 '15 edited Jul 06 '15

Don't even have a loop end condition in the for loop just catch the exception when the array out of index happens. Order of magnitude faster.

Super False.

How do you think a computer knows when to throw the exception? Bounds-checking is the only way - there isn't some magic flag on every memory address telling you which data structure it belongs to. It doesn't matter whether you're relying on an OS-level interrupt like a segfault, or runtime interrupt like an IndexOutOfBoundsException, or any other your-array-isn't-here-anymore-moron notification. Boundary comparisons are the way memory access is managed.

If you decide not to check bounds at the application level, deferring to a runtime like the JVM, you're removing a single comparison operation from every iteration. The runtime's comparison is still happening, and so is your OS's virtual memory implementation. I can absolutely guarantee you that any performance gain, if anything, is negligible with respect to a loop body that compiles to more than a few machine instructions.

EDIT: Grammar.

→ More replies (23)