Tips & Tricks
Follow


goc3

+1 for Backwards Loops!

goc3 on 13 Jun 2024 (Edited on 13 Jun 2024)
Latest activity Reply by goc3 on 19 Jul 2024 at 15:22

Base case:
Suppose you need to do a computation many times. We are going to assume that this computation cannot be vectorized. The simplest case is to use a for loop:
number_of_elements = 1e6;
test_fcn = @(x) sqrt(x) / x;
tic
for i = 1:number_of_elements
x(i) = test_fcn(i);
end
t_forward = toc;
disp(t_forward + " seconds")
0.10925 seconds
Preallocation:
This can easily be sped up by preallocating the variable that houses results:
tic
x = zeros(number_of_elements, 1);
for i = 1:number_of_elements
x(i) = test_fcn(i);
end
t_forward_prealloc = toc;
disp(t_forward_prealloc + " seconds")
0.035106 seconds
In this example, preallocation speeds up the loop by a factor of about three to four (running in R2024a). Comment below if you get dramatically different results.
disp(sprintf("%.1f", t_forward / t_forward_prealloc))
3.1
Run it in reverse:
Is there a way to skip the explicit preallocation and still be fast? Indeed, there is.
clear x
tic
for i = number_of_elements:-1:1
x(i) = test_fcn(i);
end
t_backward = toc;
disp(t_backward + " seconds")
0.032392 seconds
By running the loop backwards, the preallocation is implicitly performed during the first iteration and the loop runs in about the same time (within statistical noise):
disp(sprintf("%.2f", t_forward_prealloc / t_backward))
1.08
Do you get similar results when running this code? Let us know your thoughts in the comments below.
Beneficial side effect:
Have you ever had to use a for loop to delete elements from a vector? If so, keeping track of index offsets can be tricky, as deleting any element shifts all those that come after. By running the for loop in reverse, you don't need to worry about index offsets while deleting elements.

4 Comments

VBBV
VBBV on 19 Jul 2024 at 13:22
@goc3 you're a genius !. Interesting computing concept learnt from you today. One thing that intrigues me is how the index offsets can be beneficial while deleting elements when the loop is run backwards. Is this true only for for loops or also true for while loops ?
goc3
goc3 on 19 Jul 2024 at 15:22
@VBBV: Thanks. Regarding while loops, some other mechanism necessarily controls the indexing variable (other than the loop itself, as in the case of for loops). If that mechanism decrements the index (instead of incrementing the index), then the benefit of deleting elements without having to adjust the index after each deletion is still present.
Angelo Yeo
Angelo Yeo on 13 Jun 2024

Wow, such a clever tip! Thanks for sharing.

goc3
goc3 on 13 Jun 2024
After I originally posted this topic, someone pointed out that certain speedup claims (backwards vs. forwards) were unlikely, given statistical noise. Accordingly, I updated the end of the post to more accurately describe the situation.

See Also

Tags