Questions regarding preallocation and much more
1 view (last 30 days)
Show older comments
Consider the following function:
function A = plodding(N,d)
for ii = 1:N
jj = 1;
A(ii,jj) = randn;
while abs(A(ii,jj)) < d
jj = jj + 1;
A(ii,jj) = randn;
end
end
Rewrite this function to eliminate the allocation problem that is slowing it down. Call the new function, cruising. On a Dell Latitude E6410, with 7.8 gigabytes of usable memory, eliminating the allocation problem produces a speed-up factor of 7.”
Here's my work:
The original version with rng(0)
function A = plodding(N,d)
rng(0); % To compare between the original and the modified version
for ii = 1:N
jj = 1;
A(ii,jj) = randn;
while abs(A(ii,jj)) < d
jj = jj + 1;
A(ii,jj) = randn;
end
end
end
The modified version
function A = cruising(N,d)
rng(0);
for jj = 1:N % Reorganize, so elems are added column-wise
ii = 1;
A(ii,jj) = randn;
while abs(A(ii,jj)) < d
ii = ii + 1;
A(ii,jj) = randn;
end
end
A = A'; % To get the matrix desired
end
But when I test:
tic;A = plodding(5,4.5);toc
Elapsed time is 0.176091 seconds.
>> tic;A1 = cruising(5,4.5);toc;
Elapsed time is 39.285447 seconds.
>>>B = A - A1; sum(B(:))
ans =
0
So certainly A = A1.
Based on what I learned from the lesson, my logic should be right, because MATLAB stores elements column-wise. Could someone please help me????
5 Comments
Adam
on 31 Jul 2015
Well, you didn't give the arguments with which the function is to be called to produce a factor of 7 speedup. With a function like that the speedup will certainly not be linear in the inputs.
When I run your code with 10000, 2 as the two input arguments I get 7.36s for plodding and ~0.114s for cruising which is a speedup of the order of 60 times. That is certainly surprising to me since I wasn't aware just allocating in columns vs rows could make such a difference, but then I rarely use arrays that are resizing dynamically in that manner.
Answers (1)
Philip Borghesani
on 31 Jul 2015
Edited: Philip Borghesani
on 31 Jul 2015
The problem here is that the shape of the output and the algorithm determine the number of times the array needs to be reallocated. Plodding is faster when N is small and d is large, cruiseing is faster when N is large and d is small. Take a look at this code (which I do not claim is optimal but runs ok in both cases)
function A = warping(N,d)
rng(0);
A=zeros(1,N);
for jj = 1:N % Reorganize, so elems are added column-wise
ii = 1;
%A(ii,jj) = randn;
t(ii) = randn;
while abs(t(ii)) < d
ii = ii + 1;
t(ii) = randn;
end
A(1:ii,jj)=t(1:ii);
end
A = A'; % To get the matrix desired
end
Try all three with the inputs of (1000,3.5) (both values fairly large) your two do poorly and warping does much better.
I think the fastest solution would be to collect the rows of the final output into different cell arrays and then build the final matrix by concatenation or indexing after all the data has been calculated.
2 Comments
Philip Borghesani
on 10 Aug 2015
The number of reallocations of A determines how long the function will take. This overwhelms any advantage cruising has due to access order. Given a return value of A(m,n) plodding will reallocate A a minimum of m times and cruising will reallocate A a minimum of n times.
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!