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.
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.
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!
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.
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.
As a computer architecture guy, a couple things to clarify slights, but mostly right:
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.
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.
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.
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.
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.
29
u/Omnicrola Jul 05 '15
Interesting. Do you know why the speed difference occurs? (at the bytecode level)