Why is subscripted assignment so inefficient?

2 views (last 30 days)
Why is MATLAB's subscripted assignment so abysmally inefficient with more than 2 subscripts? e.g.,
>> clear, a = []; tic, for j = 1e3:-1:1, for k = 1e3:-1:1, a(j,k,1) = 1; end, end, toc
Elapsed time is 0.193743 seconds.
>> clear, a = []; tic, for j = 1e3:-1:1, for k = 1e3:-1:1, a(j,k) = 1; end, end, toc
Elapsed time is 0.004241 seconds.
  1 Comment
Walter Roberson
Walter Roberson on 5 Feb 2022
Interesting. I thought for a moment that it might be due to the extra multiplication and addition needed each time, but when I rewrite the code in terms of linear indexing as-if a 3D array, then I do not see nearly that much performance drop.

Sign in to comment.

Accepted Answer

Matt J
Matt J on 5 Feb 2022
Edited: Matt J on 5 Feb 2022
I would guess it's only because you are using 3 subscripts on an array that only has 2 dimensions. This forces Matlab to to do extra work, namely running a check to make sure that in a(j,k,m) the 3rd subscript is m=1 and simplifying the subscripts from (j,k,1) to (j,k). When a actualy does have 3 dimensions, the times are much more comparable:
a=zeros(1e3,1e3,2);
tic,
for j = 1e3:-1:1
for k = 1e3:-1:1
a(j,k,1) = 1;
end
end
toc
Elapsed time is 0.019444 seconds.
a=zeros(1e3,1e3);
tic,
for j = 1e3:-1:1
for k = 1e3:-1:1
a(j,k) = 1;
end
end
toc
Elapsed time is 0.016890 seconds.
  7 Comments
Walter Roberson
Walter Roberson on 6 Feb 2022
There is a lot of noise in these measurements, and it is difficult to tell what is meaningful or not.
I skip the first few runs in the plot because in nearly all runs there is a bad peak early on.
The second plot here is the more interesting one, showing the log of how the time to allocate increases with amount requested. Noise affects it a lot, so I can only describe trends that I encountered a fair bit:
  • time to allocate 1 byte starts off a bit higher
  • time to allocate a quite small number of bytes but more than 1, falls a bit, then rises a bit.
  • there does seem to be a peak at 256 bytes
  • and then it does seem to fall a bit
  • until at 2^14 there seems to be a distinct rise. This would correspond to 16384 bytes. I suspect that either 4096 or 16384 bytes is the size of an entry in the "small block pool"
  • in some of the plots, there was a leveling from 2^14 to 2^16; the more fine-grained I draw the less I see this, so it might have been a statistical artificat
  • from 2^16 onward, the log grows pretty much linearly as log2() of number of bytes increases. To phrase that a different way: from 2^16 onward, the allocation time grows linearly with number of bytes allocated. The actual boundary might possibly be 2^14
  • so, below 2^14, there appear to be at least two different allocation strategies, but the boundaries between them are a bit difficult to find. If there were only one allocation strategy for that range, using a free block pool with entries of size 2^14, then you would expect the time to be constant up to that point, but there do seem to be peaks.
  • I seem to recall that 256 bytes is the limit below which for some constant allocations and some colon expressions, that MATLAB keeps a copy around as an optimization, to be handed out when encountering another request with the same spelling (spacing even being important!). Perhaps that is why we see a blip at 256??
If someone cares to do a study of how small block allocation is done in MATLAB, I suggest 2^14 as the upper limit to study (and remember to take into account those new hidden copies that MATLAB recently starting taking for small constants.)
N = 50;
G = 2^24;
start = datetime('now');
%timing pushed into a function to allow for potential JIT
[t, gvals] = run_timing(N, G);
stop = datetime('now');
elapsed = seconds(stop - start);
display(elapsed)
elapsed = 0.5941
figure(1)
%tfilt = filloutliers(t, 'center','movmedian', 3, 1);
startat = 6;
semilogy(startat:N, t(startat:end,:));
xlabel('try #'); ylabel('seconds')
title('absolute time')
%legend("2^{"+string(gvals)+"}", 'NumColumns',4);
figure(2)
tmean = mean(t(startat:end,:),1);
semilogy(gvals, tmean)
xt = 1:ceil(max(gvals));
xticks(xt)
xticklabels("2^{"+string(xt)+"}");
xtickangle(45)
xlabel('bytes')
ylabel('mean seconds')
plin = polyfit(2.^gvals, tmean, 1);
%plog = polyfit(log2(gvals), log2(tmean),1);
fprintf('linear: roughly %g seconds + %g seconds per gigabyte\n', plin(2), plin(1)*2^30);
linear: roughly -4.90643e-08 seconds + 0.0490081 seconds per gigabyte
%fprintf('log: roughly %g seconds + %g seconds per gigabyte\n', 2.^plog(2), plog(1));
function [t,gvals] = run_timing(N,G)
%wb = waitbar(0, '0G');
%cleanMe = onCleanup(@()delete(wb));
gvals = 0:.1:ceil(log2(G));
ng = length(gvals);
t = zeros(N,ng);
for g = 1 : ng
gp = gvals(g);
gv = round(2.^gp);
%waitbar(0, wb, "2^{"+string(gp)+"}");
for n = 1 : N
tic();
initmem(gv);
t(n,g) = toc;
%waitbar(n/N, wb);
end
end
end
%gigabyte 1073741824
%megabyte 1048576
function initmem(M)
ma = ones(1,M,'uint8');
end

Sign in to comment.

More Answers (0)

Categories

Find more on Startup and Shutdown in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by