Why are for loops in IDL so slow?
Anonym
Once upon a time, I worked as an undergraduate programmer, where I wrote code that calculated atmospheric radiation algorithms. Before I knew much about IDL, I wrote some code that performed the desired calculations and placed it inside a giant for loop. To say the least, this code was slow and painful to run. In fact, it was so bad that a guy from IT came into my office to tell me I had to stop using so much of their processors. Not only that, but it took over a day to run code that calculated a day's worth of atmospheric radiation, and the algorithms don't do much good if data comes in faster than it can be processed.
That was when I decided to pick up some IDL books and learn more on how to write better code. As it turns out, there are quite a few ways to move calculations outside of a loop and reduce how much work is done inside the loop.
Why do loops in IDL seem slow?
First of all, this is not unique to IDL. If you don't believe me, look at what people commonly ask Google:
IDL is an interpreted language, which is defined by Wikipedia as
This means that when IDL executes a for loop, each statement inside the loop is interpreted at the IDL level and then sent down to the machine to process, and this is done every time the loop iterates. In loops with many, many iterations or when there are several statements inside the loop, the loop will be very slow to complete.
That said, what is the best way to avoid this problem?
Vectorize
Vectorizing, or operating on an entire array at once, is probably the first piece of advice found from the Google search above. Nearly all of IDL's mathematical functions can accept arrays and not just single values, and the result will be a corresponding array. Consider this statement
array = Dindgen(100000, INCREMENT=.001)
arcsines = DblArr(100000, /NOZERO)
for i=0,99999 do arcsines[i] = asin([i])
This loop took 0.047 seconds to run on my computer. However by performing the arcsine operation outside of the loop results in a significant gain.
arcsines = asin(array)
In fact, for me, the time to execute this statement was so small that IDL's tic/toc calls around it reported zero seconds.
The reason for this is that instead of passing each arcsine call to the machine to execute individually, the whole array is passed at once, and the machine handles the array. In other words, there is only one time IDL and the machine communicate back-and-forth instead of 100000 times.
Additionally, WHERE is (in my mind) one of the most convenient vectorized operations in IDL. Using it can often avoid the need for a loop altogether. The conditional value inside the Where statement can be an array of any dimensions.
result = Where(condition, count)
Keep in mind, also, that if all you care about is the count in the Where call and you don't need the result, you can avoid creating a new variable by using TOTAL on the condition, where the items in the conditional value can also be an array of any dimensions:
count = Total(condition)
Move conditionals and calculations outside of loops
Conditional statements always come with a performance expense. Again, consider vectorization if it is possible to do so, but if not, try keeping conditional statements as simple as possible.
One possibility is if you know you will only work with a subset of data, use a WHERE statement and only iterate through the subset. For example, instead of this:
for i=0,N_Elements(array) do begin
if (array[i] mod 3 eq 0) then begin
...
endif
endfor
try this:
result = Where(array mod 3 eq 0, count)
for ii=0, count-1 do begin
i = result[ii]
...
endfor
Now you are only doing 1/3 as many iterations of the loop, and the conditional has been moved outside of the loop
Also consider moving mathematical calculations on constants outside of the loop so that minimal operations are performed in the loop. For example, instead of this:
for i=0,N_Elements(array) do begin
value = array[i] * !pi/2
endfor
try this:
piOverTwo = !pi/2
for i=0,N_Elements(array) do begin
value = array[i] * piOverTwo
endfor
The loop completed in half of the time when the constants were computed and set to a single variable. Again, try to keep the content of the loop as simple as possible.
Use in-place operations
It is more efficient if you can operate on a variable in-place rather than redefine the variable. In this statement:
var = var + 1
IDL creates a new item in memory, performs the operation, and then forgets about the old item. Inside a large loop, this can be expensive.
IDL contains the following in-place operators:
| Operator |
Definition |
Example |
Non in-place Equivalent |
| ++ |
Increment variable by one |
a++ |
a = a + 1 |
| -- |
Decrement variable by one |
a-- |
a = a - 1 |
| += |
Add a specified value to a variable (value specified after operator) |
a += 2 |
a = a + 2 |
| -= |
Subtract a specified value from the variable |
a -= 2 |
a = a -2 |
| *= |
Multiply the variable by a specified value |
a *= 2 |
a = a * 2 |
| /= |
Divide the variable by a specified value |
a /= 2 |
a = a /2 |
This can be done to elements of an array in addition to a single variable:
array[i]++
array[i] /= 2
and it can even be done to a whole array (vectorized operation):
array--
array *= 3
Use early breaks if possible
As described in an IDL Data Point post about a year and a half ago, it is convenient to move on to the next iteration of the loop using CONTINUE in cases where it is not necessary to continue with the current iteration of the loop. Also, if there is no more work to do in the loop altogether, then it saves time to exit from a loop early using BREAK. This can be useful if, for instance, you have a way to determine that the rest of the data in your array is missing or unimportant data.
Note that order matters
Lastly, note that IDL is Column-major rather than row-major (just like Fortran, rather than C). Although this code is more intuitive and is what you would write in C:
array = Lindgen(10000,100000)
for i=0,9999 do begin
for j=0,9999 do begin
value = array[i,j]/2
endfor
endfor
This loop took 9.96 seconds to run on my computer. However, by switching i and j:
for j=0,9999 do begin
for i=0,9999 do begin
value = array[i,j]/2
endfor
endfor
it took only 8 seconds to run. This is because when IDL iterates through the columns before iterating through the rows, it is accessing the data in the order in which it is stored in memory.
In conclusion
For loops in IDL can sometimes seem like bad thing, but they aren't really that bad and are sometimes unavoidable. There are quite a few techniques to use that make loops as efficient and fast as possible, and this article outlines only a handful of them. To summarize these:
- First try vectorization. Move a whole line or even getting rid of the loop altogether if IDL has a way to perform your desired calculation using a single call on the array.
- Move everything possible out of the loop, such as setting variables, calculating using constants, and performing conditional statements. Consider using the WHERE statement when checking conditionals or looking for a certain item in the array.
- Use in-place operators for simple arithmetic to avoid making copies of variables or arrays.
- Leave the loop early if you are done with it.
- Finally, access data in the order in which it is stored.
The idea, in conclusion, is to keep the loops as simple and minimalistic as possible.
By the way, I only mention for loops in this article. However, these exact same techniques apply to any kind of loop in IDL, including While, Repeat, and Foreach.