Last night as I wandered around some sites on Java optimization, I came across an example of loop optimization that felt so wrong, yet unfortunately does work!
The reasoning goes as follows: both C# and Java perform array bounds checking, whether you like it or not. Therefore, if you’re looping over all the items in the array, don’t bother testing for the termination condition – just keep going until you get an index out of bounds exception.
So, rather than your traditional code along the lines of this:
|
1 |
int[] arr = new int[size];for (int i = 0; i < arr.Length; i++){ arr[i] = i;} |
You instead end up with:
|
1 |
int[] arr = new int[size];start = DateTime.Now;try{ for (int i = 0; ; i++) { arr[i] = i; }}catch (IndexOutOfRangeException){ } |
To my mind, this goes well and truly against two often-quoted design patterns: 1) code for readability, and 2) exceptions are expensive.
Leaving aside point 1) for a moment, 2) is an interesting one. Yes, exceptions are (relatively) expensive, but if your array is, say, ten million elements, the cost of throwing one exception can be outweighed by the gain of not performing ten million comparisons. If your array is only five items, chances are the exception will be more expensive.
Some results: to run the code as above on an array of size 100,000,000, the “conventional” method took 625ms, and the “exception”method 609ms. Another interesting point was that looping backwards over the array (i.e. comparing against zero rather than the array’s length) was actually slower, at 656ms.
When I originally tried this at home under Java, I got significantly more different results – with the “exception” method being three times quicker at times. However, I’ve been unable to reproduce this on my work machine, so it could be something slightly weird going on.
I hope no-one reading this post is now running for their code to go and replace all their loops with try..catch…IOOBE’s now – I wouldn’t recommend it. Sure, it might be a little faster, but I’d go for the more obviously correct code any time.
And you should always remember the 80:20 rule: chances are, 80% of your program’s execution time is in 20% of the code. Chances are, “i < arr.Length” isn’t part of that 20%.
(Lastly, a caveat: this post uses “micro-benchmarks”; tiny snippets of code that probably don’t bear any resemblance to real life in almost all cases. I don’t promise that these results hold in different situations!)
Load comments