Why is Preallocating arrays important in MATLAB, and how does it improve performance compared to dynamically growing arrays?

I am trying to understand the performance difference between preallocating arrays and dynamically growing them in MATLAB.

For example, I have seen that using loops like this:

• Dynamically growing:

for i = 1:10000
    A(i) = i^2;
end

is slower than preallocating memory first:

• Preallocated:

A = zeros(1,10000);
for i = 1:10000
    A(i) = i^2;
end

I would like to know:

• Why MATLAB performs worse when arrays grow inside a loop
• What happens in memory when MATLAB resizes arrays repeatedly
• When it is acceptable to avoid preallocation
• Whether modern MATLAB versions still suffer from this performance issue

[Stephen23]

"Whether modern MATLAB versions still suffer from this performance issue"

Your critique of MATLAB’s emphasis on preallocation seems to misunderstand a fundamental aspect of all programming languages: resizing arrays in memory is expensive, regardless of the language. MATLAB’s focus on homogenous numeric arrays and preallocation is not a flaw, it’s a strength in numerical computing, where large, contiguous memory blocks are essential for numeric computation performance.

Languages like Java and C++ also face this issue with homogenous arrays, employing strategies like amortized doubling to reduce but not eliminate resizing overhead (and have other disadvantages, such as blocking significant areas of memory not actually used for storing data). Dynamic containers (e.g., Python lists) avoid manual preallocation, but sacrifice numeric efficiency for flexibility, as they store data non-contiguously. Every approach is a compromise.

Rather than “sweeping this under the rug,” MATLAB’s documentation highlights a key optimization technique upfront, empowering users to write fast, scalable numerical code. The criticism here is misplaced: these trade-offs exist universally, any time an array must be resized, regardless of the programming language. Do you consider that "modern C++ versions still suffer from the malloc() performance issue"?

[Walter Roberson]

@Stephen23

most approaches to memory allocation require periodically copying old content to new memory from time to time as arrays grow. There are techniques such as the "doubling" that you mention that reduce the number of times that copying is needed, but do not eliminate it.

There is, however, one no-copy approach that can work with sufficient operating system cooperation.

Internally, non-privileged memory is allocated to virtual addresses, collections of physical blocks given virtual addresses. The program accesses using the virtual addresses, and the Memory Management Unit uses lookup tables to translate the memory block portion of the address into physical block locations. Usually memory is managed in either 512 byte or 1 kilobyte or 4 kilobyte chunks, so the prefix of the virtual address is mapped to physical addresses and then the bottom bits of the virtual address are used as the offset into the physical address. There is specialized hardware known as Translation Lookaside Buffer (TLB) that cache the address translation, and typically achieve cache hit rates of better than 99%, so internally the operation is quite fast.

The lookup tables in turn often have either starting address and ending address, or else starting address and size. It is uncommon to track single blocks at a time (but can happen): much of the time several contiguous physical blocks at a time are mapped into a single entry. In turn memory management for a process involves putting together a number of these descriptors.

For larger objects, MATLAB uses memory allocation calls that allocate new virtual regions, letting the hardware find appropriate backing physical memory. When the object is released by MATLAB, it uses the operating system call to return the entire virtual region, which in turn takes care of deallocating the physical regions.

When large objects are expanded, MATLAB creates a larger region, copies the old and new data into it, and frees the original region.

In theory, MATLAB could allocate memory chunks instead of asking for just enough to satisfy the current request. In the special case of unshared memory, much of the time expanding the array would involve incrementing the internal tracking of how much of the chunk is used, with the reallocation strategy used when the chunk runs out.

Now... in theory if MATLAB were to work in chunks that were the operating system physical page size, then potentially expanding the memory for a region could involve asking the operating system to allocate additional physical blocks to the virtual region, without deallocating the existing memory. In theory the operating system could satisfy the request by adding a new memory translation entry to the process translation tables, without needing to move any existing memory around.

This requires that the operating system provides calls that can handle this kind of memory management. I lack the knowledge to say whether Windows or Linux provide such operating system calls. It is, for example, not the documented behaviour of C++ realloc(), which is defined as using allocation and copying the existing content, if memory in the current chunk is exhausted.

Answer 1

[Torsten]

That's what AI answers:

Preallocation in MATLAB—creating an array to its full size before filling it within a loop—is significantly faster than dynamic growth, which expands the array one element at a time. When arrays grow dynamically, MATLAB must find new, larger contiguous blocks of memory in each iteration and copy all previous data to the new location, leading to quadratic performance degradation (time spent grows quadratically with size).

Performance Comparison: Preallocation vs. Dynamical Growth

• Preallocation: Initializing with zeros(N,1) or NaN(N,1) allows MATLAB to allocate memory once. The loop merely fills the existing slots.
• Dynamic Growth: Adding elements like x(i) = new_val without prior allocation forces repeated reallocation, requiring O(N^2)time.
• Result: Preallocation is typically 5 to over 35 times faster than dynamic resizing, with the advantage becoming more pronounced as the data size increases.

Why Dynamic Growth is Slow

MATLAB stores numeric arrays in contiguous memory (unbroken memory blocks).

1. Memory Search: In every iteration, if the array needs to grow, MATLAB searches for a new, larger space.
2. Data Copying: It copies the entire contents of the old array to the new, larger block.
3. Quadratic Growth: The time spent increases quadratically because each copy operation takes longer as the array grows.

When to Use Preallocation

• Large Data Arrays: Always preallocate when building vectors or matrices in loops.
• Cell Arrays & Structs: Repeatedly adding to cell arrays or structures without preallocation is slow because each element has its own memory overhead.
• If size is unknown: Preallocate the maximum possible size and trim it afterward, or preallocate in large chunks (e.g., 1000 elements at a time).

Best Practices for Preallocation

• Use zeros() or ones(): For numeric data.
• Use NaN(): For numerical data to debug unfilled slots.
• Use cell(): To preallocate cell arrays.
• Use cell(m, n): For sparse or non-numeric data structures.
• Avoid over-preallocation: While it is rarely a disadvantage, excessively large allocations that are not used can waste memory.

Answer 2

[Walter Roberson]

There are a few cases in which MATLAB semantics would potentially allow some variables to be grown in place, but much of the time, the semantics of MATLAB require that the output block for an assignment be seperate from the input block. For example,

A = [A, x];

requires that a temporary output the size of (A and x together) be allocated, then the contents of A and the contents of x be copied into the temporary output variable, and then make A point to the temporary location and decrement the usage counter on the memory that was occupied by A. After all, the code might potentially have been

A = [1 2 3 4 5];
B = A;
x = [11 12];
A = [A, x];

in which case the memory occupied by A could not be expanded in-place because the data block is shared with B. This behaviour of sharing data areas when appropriate and making new output areas as needed to break the sharing is important to MATLAB's performance.

When you have code such as

A(i) = i^2;

then in order for MATLAB to be able to expand A "in-place", MATLAB would first have to be able to prove that the memory for A was not shared with anything else. Then, it would have to check that there was space to expand into; if not then new space would need to be allocated, the current contents of A copied over, and the new element assigned.

Now, MATLAB has at least three memory allocation strategies:

• very very small arrays are allocated on fixed-sized blocks out of a cache. I do not recall the exact limit on the fixed size blocks; if I recall correctly it was either the size of one double, or else the size of three doubles. By the time that four doubles is reached, this memory strategy is no longer used
• modest small arrays are allocated out of fixed sized blocks that are partitioned out of a free list. I do not recall at the moment whether these blocks are 1Kb or 4Kb (and that detail might vary between 32 bit and 64 bit MATLAB.) Inactive blocks are marked as inactive rather than being deallocated
• all other arrays are allocated out of the heap, using standard memory allocators. In 64 bit versions of MATLAB, each variable is allocated as a seperate operating system memory region, and the entire region is returned to the operating system when the block is no longer in use. Although the operating system might possibly end up rounding up the requested memory size to the next 1Kb or 4Kb boundary, the model used is as-if the operating system might somehow be able to physically allocate the exact amount of requested memory. Virtual memory blocks are used, and in principle the operating system might potentially be able to allocate the virtual memory anywhere in physical memory (but in practice it probably aligns the request on physical blocks.)

So... MATLAB arrays could maybe get grown in-place provided they are not shared and provided that the result of growing did not exceed 4 Kb. And after that, for sure the allocate-copy-write-discard_original strategy needs to be used.

When the allocate-copy-write-discard_original strategy is being used, when you have a A(i) = i^2 loop:

• the first assignment creates a new area A of size 1. Memory writes this time: 1. Total memory writes so far: 1
• the second assignment creates a new temporary area of size 2, copies the A of size 1 into it, copies the i^2 into it, and releases the memory. Memory writes this time: 2. Total memory writes so far: 1+2 = 3
• the third assignment creates a new temporary area of size 3, copies the A of size 2 into it, copies the i^2 into it, and releases the memory. Memory writes this time: 3. Total memory writes so far: 3 + 3 = 6
• the fourth assignment creates a new temporary area of size 4, copies the A of size 3 into it, copies the i^2 into it, and releases the memory. Memory writes this time: 4. Total memory writes so far: 6+4 = 10

and so on. After N steps you have had 1+2+3...+N = N*(N+1)/2 total memory writes. Although the number of writes at any one iteration is linear, because you have the sum of increasing linear values, the overall result is quadratic performance.

In theory, MATLAB does not have to be quite this bad. If the heap allocates were multiples of a fixed size (such as multiples of 512 bytes), then in theory MATLAB could potentially grow some arrays in place. That would improve the quadratic performace by (block size divided by size of one scalar)... so for example by (512 bytes / 8 bytes per scalar) = 64 -- making the overall performance proportional to N*(N+1)/(2*64)

Answer 3

[Matt J]

When it is acceptable to avoid preallocation

Looping backwards is an alternative to pre-allocating. You're not really "avoiding" preallocation this way. You're just forcing Matlab to do the preallocation for you. Sometimes I do this just to simplify syntax.

N=3e6;

timeit(@()forward(N))

ans = 0.1433

timeit(@()back(N))

ans = 0.0048

timeit(@()prealloc(N))

ans = 0.0037

function forward(N)
 for i = 1:N
    A(i) = i^2;
 end
end
 

function back(N)
 clear A  %<------IMPORTANT!!
 for i = N:-1:1
    A(i) = i^2;
 end
end


function prealloc(N)
A = zeros(1,N);
 for i = 1:N
    A(i) = i^2;
 end
end