Is indexing vectors in MATLAB inefficient?
Solution 1:
I can, of course, only speculate. However when I run your test with the JIT compiler enabled vs disabled, I get the following results:
% with JIT no JIT
0.1677 0.0011 %# init
0.0974 0.0936 %# #1 I added an assigment before this line to avoid issues with deferring
0.4005 0.4028 %# #2
0.4047 0.4005 %# #3
1.1160 1.1180 %# #4
0.8221 48.3239 %# #5 This is where "don't use loops in Matlab" comes from
0.3232 48.2197 %# #6
0.5464 %# logical indexing
Dividing shows us where there is any speed increase:
% withoutJit./withJit
0.0067 %# w/o JIT, the memory allocation is deferred
0.9614 %# no JIT
1.0057 %# no JIT
0.9897 %# no JIT
1.0018 %# no JIT
58.7792 %# numel
149.2010 %# no numel
The apparent speed-up on initialization happens, because with JIT turned off it appears that MATLAB delays the memory allocation until it is used, so x=zeros(...) does not do anything really. (thanks, @angainor).
Methods 1 through 4 don't seem to benefit from the JIT. I guess that #4 could be slow due to additional input testing in subsref to make sure that the input is of the proper form.
The numel result could have something to do with it being harder for the compiler to deal with uncertain number of iterations, or with some overhead due to checking whether the bound of the loop is ok (thought no-JIT tests suggest only ~0.1s for that)
Surprisingly, on R2012b on my machine, logical indexing seems to be slower than #4.
I think that this goes to show, once again, that MathWorks have done great work in speeding up code, and that "don't use loops" isn't always best if you're trying to get the fastest execution time (at least at the moment). Nevertheless, I find that vectorizing is in general a good approach, since (a) the JIT fails on more complex loops, and (b) learning to vectorize makes you understand Matlab a lot better.
Conclusion: If you want speed, use the profiler, and re-profile if you switch Matlab versions. As pointed out by @Adriaan in the comments, nowadays it may be better to use timeit() to measure execution speed.
For reference, I used the following slightly modified test function
function tt = speedTest
tt = zeros(8,1);
tic; x = zeros(1,1e8); tt(1)=toc;
x(:) = 2;
tic; x(:) = 1; tt(2)=toc;
tic; x(1:end) = 2; tt(3)=toc;
tic; x(1:1e8) = 3; tt(4)=toc;
tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
tt(5)=toc;
tic;
for i=1:numel(x)
x(i) = 5;
end
tt(6)=toc;
tic;
for i=1:1e8
x(i) = 6;
end
tt(7)=toc;
%# logical indexing
tic;
id = true(1e8,1));
x(id)=7;
tt(8)=toc;
Solution 2:
I do not have an answer to all the problems, but I do have some refined speculations on methods 2, 3 and 4.
Regarding methods 2 and 3. It does indeed seem that MATLAB allocates memory for the vector indices and fills it with values from 1 to 1e8. To understand it, lets see what is going on. By default, MATLAB uses double as its data type. Allocating the index array takes the same time as allocating x
tic; x = zeros(1e8,1); toc
Elapsed time is 0.260525 seconds.
For now, the index array contains only zeros. Assigning values to the x vector in an optimal way, as in method 1, takes 0.094316 seconds. Now, the index vector has to be read from the memory so that it can be used in indexing. That is additional 0.094316/2 seconds. Recall that in x(:)=1 vector x has to be both read from and written to the memory. So only reading it takes half the time. Assuming this is all that is done in x(1:end)=value, the total time of methods 2 and 3 should be
t = 0.260525+0.094316+0.094316/2 = 0.402
It is almost correct, but not quite. I can only speculate, but filling the index vector with values is probably done as an additional step and takes additional 0.094316 seconds. Hence, t=0.4963, which more or less fits with the time of methods 2 and 3.
These are only speculations, but they do seem to confirm that MATLAB explicitly creates index vectors when doing native vector indexing. Personally, I consider this to be a performance bug. MATLABs JIT compiler should be smart enough to understand this trivial construct and convert it to a call to a correct internal function. As it is now, on the todays memory bandwidth bounded architectures indexing performs at around 20% theoretical peak.
So if you do care about performance, you will have to implement x(1:step:end) as a MEX function, something like
set_value(x, 1, step, 1e8, value);
Now this is clearly illegal in MATLAB, since you are NOT ALLOWED to modify arrays in the MEX files inplace.
Edit Regarding method 4, one can try to analyze the performance of the individual steps as follows:
tic;
id = 1:1e8; % colon(1,1e8);
toc
tic
x(id) = 4;
toc
Elapsed time is 0.475243 seconds.
Elapsed time is 0.763450 seconds.
The first step, allocation and filling the values of the index vector takes the same time as methods 2 and 3 alone. It seems that it is way too much - it should take at most the time needed to allocate the memory and to set the values (0.260525s+0.094316s = 0.3548s), so there is an additional overhead of 0.12 seconds somewhere, which I can not understand. The second part (x(id) = 4) looks also very inefficient: it should take the time needed to set the values of x, and to read the id vector (0.094316s+0.094316/2s = 0.1415s) plus some error checks on the id values. Programed in C, the two steps take:
create id 0.214259
x(id) = 4 0.219768
The code used checks that a double index in fact represents an integer, and that it fits the size of x:
tic();
id = malloc(sizeof(double)*n);
for(i=0; i<n; i++) id[i] = i;
toc("create id");
tic();
for(i=0; i<n; i++) {
long iid = (long)id[i];
if(iid>=0 && iid<n && (double)iid==id[i]){
x[iid] = 4;
} else break;
}
toc("x(id) = 4");
The second step takes longer than the expected 0.1415s - that is due to the necessity of error checks on id values. The overhead seems too large to me - maybe it could be written better. Still, the time required is 0.4340s , not 1.208419s. What MATLAB does under the hood - I have no idea. Maybe it is necessary to do it, I just don't see it.
Of course, using doubles as indices introduces two additional levels of overhead:
- size of
doubletwice the size ofuint32. Recall that memory bandwidth is the limiting factor here. - doubles need to be cast to integers for indexing
Method 4 can be written in MATLAB using integer indices:
tic;
id = uint32(1):1e8;
toc
tic
x(id) = 8;
toc
Elapsed time is 0.327704 seconds.
Elapsed time is 0.561121 seconds.
Which clearly improved the performance by 30% and proves that one should use integers as vector indices. However, the overhead is still there.
As I see it now, we can not do anything to improve the situation working within the MATLAB framework, and we have to wait till Mathworks fixes these issues.
Solution 3:
Just a quick note to show how in 8 years of development, the performance characteristics of MATLAB have changed a lot.
This is on R2017a (5 years after OP's post):
Elapsed time is 0.000079 seconds. % x = zeros(1,1e8);
Elapsed time is 0.101134 seconds. % x(:) = 1;
Elapsed time is 0.578200 seconds. % x(1:end) = 2;
Elapsed time is 0.569791 seconds. % x(1:1e8) = 3;
Elapsed time is 1.602526 seconds. % id = 1:1e8; x(id) = 4;
Elapsed time is 0.373966 seconds. % for i=1:numel(x), x(i) = 5; end
Elapsed time is 0.374775 seconds. % for i=1:1e8, x(i) = 6; end
Note how the loop for 1:numel(x) is faster than indexing x(1:end), it seems that the array 1:end is still being created, whereas for the loop it is not. It is now better in MATLAB to not vectorize!
(I did add an assignment x(:)=0 after allocating the matrix, outside of any timed regions, to actually have the memory allocated, since zeros only reserves the memory.)
On MATLAB R2020b (online) (3 years later) I see these times:
Elapsed time is 0.000073 seconds. % x = zeros(1,1e8);
Elapsed time is 0.084847 seconds. % x(:) = 1;
Elapsed time is 0.084643 seconds. % x(1:end) = 2;
Elapsed time is 0.085319 seconds. % x(1:1e8) = 3;
Elapsed time is 1.393964 seconds. % id = 1:1e8; x(id) = 4;
Elapsed time is 0.168394 seconds. % for i=1:numel(x), x(i) = 5; end
Elapsed time is 0.169830 seconds. % for i=1:1e8, x(i) = 6; end
x(1:end) is now optimized in the same as x(:), the vector 1:end is no longer being explicitly created.