Tips & Tricks
Follow


goc3

+1 for Backwards Loops!

goc3 on 13 Jun 2024 (Edited on 13 Jun 2024)
Latest activity Edit by John D'Errico on 8 Sep 2024 at 14:47

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.

5 Comments

John D'Errico
John D'Errico on 6 Sep 2024 at 13:26 (Edited on 8 Sep 2024 at 14:47)
Cute. A sneaky preallocation that uses prestadigitation. It works of course because a statement like
x(10) = 1
x = 1x10
0 0 0 0 0 0 0 0 0 1
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
creates a new vector of length 10, where only the last element has been assigned, and the very first iteration of the loop implicitly does exactly that. And at no point did my fingers leave my hand!
Using a reverse loop to delete however, is still not efficient, because that loop still performs dynamic reallocation of memory at each step. The code is nice and clean, and easy to read, so that is a good thing.
n = 1e5;
tic
y = 1:n;
for ind = n:-1:1
if mod(ind,2) == 0
y(ind) = [];
end
end
toc
Elapsed time is 4.899416 seconds.
tic
y2 = 1:n;
y2(mod(1:n,2) == 0) = [];
toc
Elapsed time is 0.004071 seconds.
So the loop is MUCH less efficient, because at each step MATLAB reallocates memory. And the longer the loop, the worse it gets. A forwards loop might look like this:
tic
y3 = 1:n;
deleteflag = false(1,n);
for ind = 1:n
if mod(ind,2) == 0
deleteflag(ind) = true;
end
end
y3(deleteflag) = [];
toc
Elapsed time is 0.009604 seconds.
So fairly efficient, but extra code, and I had to create a secondary logical vector on the side to flag elements for deletion. Note this last loop could have been written to run in either direction, because no deletion was done until the end.
For shorter loops where the time is not a factor, the backwards deletion loop is a beautiful thing, since the code is nice and clean (and it works!) when a sloppily written forwards deletion loop completely fails.
Overall, a nice idea, well worth keeping in your bag of tricks.
VBBV
VBBV on 19 Jul 2024
@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
@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