Fastest way to fill in an array

Hi,

I have written the following program, 3 ways to create the same array:

number = 1e5;
tic
A = [];
for i = 1 : number
  A = [A i];
end
toc

tic
for i = 1 : number
  B(i) = i;
end
toc

tic
C = [];
for i = 1 : number
  C(i) = i;
end
toc

Here are the results:

Elapsed time is 11.126158 seconds.

Elapsed time is 0.003447 seconds.

Elapsed time is 0.020941 seconds.

- Why is the first method (A = [A i];) so slow compared to B(i) = i; ??

Why does writing C = []; slow down the computation? (compared to B)

Thanks!

Answer 1

[David Sanchez]

The first method is the slowest because even when the matrix is preallocated, its size changes within the loop, what renders the first preallocation useless. The system has to look for increasing room for a growing matrix. The third method is slower than the second because it preallocates the matrix but with no specific size, the problem is similar to the first method but faster because the matrix is not overwritten. The second method gives more freedom to the system to locate the matrix.

[David Sanchez]

Try this out, it is the fastest way to do it:

D=zeros(number,1);
for i = 1 : number
  D(i) = i;
end

[Martin]

Thanks for your answer. Ok for the first comparison.

But for the second one I still have trouble understanding. After the first step, the two loops should be the same as the previous initialization C = []; does not have any impact anymore.

But I tried with bigger numbers and the solving times ratio remains the same, e.g. with number = 1e8:

Elapsed time is 0.353962 seconds.

Elapsed time is 2.141597 seconds.

It is as if Matlab drew the conclusion, after reading "C = [];", that C will always be small and that Matlab should rather allocate only a small space, even if C is growing.

I'm intrigued. :)

[James Tursa]

@Martin: Please read my Answer. You can't take your code literally as written because the MATLAB JIT will change it to something else depending on what patterns it recognized. I strongly suspect that the 2nd example has been rewritten by the JIT as simply

B = 1:number;

Compare the timing of that statement with the timing of your 2nd example to see how similar they are.

I suspect that the 3rd example is the result of the JIT doing the pre-allocation for you, but still doing the loop.

Answer 2

[James Tursa]

The results will be highly dependent on MATLAB version used. Since none of the examples explicitly pre-allocate the result, you are at the mercy of the JIT as to what MATLAB will do with the three methods. On paper, all three methods are pretty much equivalent ... they have to reallocate the memory on each iteration to make room for the next entry. The only difference is a slight syntax difference that either the JIT recognizes or it doesn't. If it recognizes the pattern of what you are doing in the loop, it can pre-allocate the result for you and greatly increase performance time. If it can't recognize the pattern, then you are stuck with the very inefficient as-written reallocation at each iteration. The JIT might even be smart enough to simply calculate the result directly and avoid the loop entirely (which might be the difference between method 2 and 3 in your example). E.g., here are the timings from an older version of MATLAB that does not have the JIT smarts that later versions have:

Elapsed time is 11.726275 seconds.
Elapsed time is 12.153010 seconds.
Elapsed time is 12.048716 seconds.

Basically no difference in the timings because none of the methods is recognized by the JIT as something it can pre-allocate or pre-calculate for you.

Bottom line: Best to explicitly pre-allocate like David has shown you rather than rely on the JIT to recognize the pattern in your loop to do the pre-allocation for you. Even if you know a certain pattern is recognized by the JIT of your version, what will happen to the performance if it ever gets ported to another machine with an earlier version of MATLAB? Well, what I have shown above will happen ... lousy performance. So always explicitly pre-allocate.

[Martin]

Ok James, thank you for this great answer. I hadn't seen it when I answered. I didn't know JIT before. From what I understood, it translates the byte code in machine code. Is it hard for Matlab to do it always and for the whole program, as it seems to increase the speed so much?

2 remarks: - MY MISTAKE: When I didn't initialize, I didn't clear either. That's the reason why it was faster than initializing with C = [];. Now that I clear all; at the beginning of my program, the processing times are almost exactly the same (even slightly faster when initialized). Sorry for this.

- As expected, initializing with zeros is faster than not initializing (1st time below), and simply writing B = 1 : number is faster (3rd). But surprisingly, I tried initializing with ones and it is constantly faster than zeros (2nd):

Elapsed time is 0.055619 seconds.

Elapsed time is 0.045064 seconds.

Elapsed time is 0.024084 seconds.

Apparently, this difference between the first two (initializing with zeros or ones) is entirely contained in the initialization itself and not when filling the array (I tested it), which thus seems to be faster for ones than for zeros. That's pretty interesting.

[Cedric]

As you are in these memory management experiments, note that there can be a significant difference of execution time between initializing with e.g. 0's, and simply (pre-)allocating memory (careful with 2e4x2e4, this could freeze your system if it starts swapping, but I wanted to use large enough arrays [3.2GB] for the difference to be significant):

 >> clear all

 >> tic ;  a1 = zeros(2e4) ;  toc            % Init.
 Elapsed time is 1.383591 seconds.

 >> tic ;  a2(2e4,2e4) = 0 ;  toc            % (Pre-)alloc.
 Elapsed time is 0.021422 seconds.

[James Tursa]

Another alternative, if you know you will be filling in the data downstream, is this UNINIT function from the FEX:

http://www.mathworks.com/matlabcentral/fileexchange/31362-uninit-create-an-uninitialized-variable-like-zeros-but-faster

It allocates a variable without initializing the data and is very fast.

[Martin]

Thank you!

Answer 3

[dan]

Can someone please explain this one then?

tic
Test = zeros(20000);
for i = 1:20000
    for j=1:20000
        Test(i,j) = i+j;
    end
end
toc
tic
Test = zeros(20000);
for i = 1:20000
    for j=1:20000
        Test(j,i) = i+j;
    end
end
toc

Elapsed time is 5.271389 seconds.

Elapsed time is 0.938210 seconds.

[Stephen23]

"Can someone please explain this one then?"

This topic has been discussed fairly regularly:

https://www.mathworks.com/matlabcentral/answers/410794-for-loop-order

https://www.mathworks.com/matlabcentral/answers/440506-optimize-the-ordering-of-nested-loop-for-speed#answer_357120

https://www.mathworks.com/matlabcentral/answers/119717-more-efficient-way-for-doing-for-and-while-loops#answer_126698

https://www.mathworks.com/matlabcentral/answers/434746-which-for-loop-will-completed-first#answer_351319

https://www.mathworks.com/matlabcentral/answers/160161-why-vectorized-calculations-are-faster-than-for-loops#comment_245775

https://www.mathworks.com/matlabcentral/answers/528938-comparing-the-performance-of-colon-loop-and-cell-indexing

As far as I understand, the cause is due to the processor reading a whole block of data into its memory cache, which is then very fast to access (faster even than the main memory).

[James Tursa]

@Stephen23 +1