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

Show parent comments

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?

1

u/kqr Jul 06 '15

...maybe. That's why it's useful to look at the generated assembly.

1

u/tias Jul 09 '15

The JIT-generated assembly you mean? Cause the bytecode compiler can't somehow elide the bounds check, that has to happen at the VM level.

1

u/kqr Jul 09 '15

Yes... I guess? I'm not enough of a Java wiz to answer that.

1

u/ghillisuit95 Jul 06 '15

yes, in java, hence why you can do the just catch the exception hack.

1

u/ElFeesho Jul 06 '15

So in Java you'd be checking whether a value is less than the length of an array, then when you index the array, the JVM will do the same.

1

u/IJzerbaard Jul 06 '15

Naively yes, but HotSpot does bounds-check elimination (sometimes) and I imagine other JVMs also make some effort in that direction

2

u/ElFeesho Jul 06 '15

I imagine a JIT compiler would be good at optimising that kind of thing, but on paper, without any optimism on implementation of a compiler, the only real way the JVM could report ArrayOutOfBoundsException is if it were to check every access of the array.

2

u/IJzerbaard Jul 06 '15

Well of course, but theoretical implementations don't have any performance to discuss, they don't even exist..

1

u/ElFeesho Jul 06 '15

I think it's plausible to suggest that conditional checks have an associated overhead... And that two conditional checks are likely to be twice as costly.

If you know of a JVM that had zero cost branching, hook me up!

2

u/IJzerbaard Jul 06 '15

No, the point is that it eliminates the branch when accessing the array, because it already knows the index is in range. That's literally the entire point of bounds-check elimination.

1

u/bliow Jul 12 '15

Given what you describe, I'd expect foreach loops to give you the same performance without exception-management hacks. Is that the case?

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

2

u/minime12358 Jul 05 '15

Thanks! I mixed up -- with ~~

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.

-11

u/ice109 Jul 05 '15

because the computer will predict the outcome based on previous outcomes.

you realize that branch prediction is basically at the assembly level right? who knows what in the world happens to a java loop when digested by the jvm. now maybe the jvm does branch prediction but i don't know that and depending on the processor pipeline to do it is silly.

→ More replies (15)

1

u/[deleted] Jul 05 '15

Probably because it wont evaluate the exit clause every single iteration, i think the proportional speedup is also very dependent on how much work both the exit clause and the loop-work are.