Why does PETSc matrix memory allocation improve performance so much?

Question

Context

In the Portable, Extensible Toolkit for Scientific Computing (PETSc), the user often creates matrices and vectors. These objects are then used as input for other routines like iterative solvers.

PETSc offers a routine for preallocating matrix memory by providing the number of nonzero entries in the diagonal submatrix and the off diagonal submatrices.

MATLAB has some useful articles about why preallocation helps -- for example, it eliminates the need to reallocate memory every time an element is added to a vector.

Question

Why does memory preallocation in PETSc help so much? What exactly is happening when I tell PETSc the number of nonzeros in my matrix, and how does it compare to when I do not preallocate?

Edit

I found a partial answer in this powerpoint about how the preallocation is related to the AIJ format. It says that PETSc sparse matrices are dynamic objects and can have nonzeros added to them on the fly. But this "on the fly" approach can lead to extra copying and reallocating, etc. I suppose this is the answer I wanted, but more details would be great.

Answer 1

Warning: this answer is only going to give a brief overview, for the real details, the one source that won't be wrong is the source code.

The core matrix AIJ format is basically the same as the one known as compressed sparse row (CSR) or Yale format. This stores a sparse matrix as a list (normally concretely implemented as an array), $A$, of the nonzero entries, ordered by a key like (row index)$\times$(number of columns)+(column index), along with a list, $I$, of the index in $A$ at which which each row starts, and another list, $J$, containing the column indices of each of the entries in $J$. This format makes it quick to pull out the individual rows of $A$, and is good for right multiplication by column vectors. On the other hand, this makes adding a random new entry potentially expensive, since it means inserting an entry into the middle of a list, which potentially means reallocating a new block of memory and copying the existing values on either side of the one you're inserting.

Based on the code, it looks like when used without preallocation PETSc inserts some padding space into its guesses for the size of $A$ and $J$, and stores an additional list, $Ilen$, containing the number of genuine entries in each row. However, if a number of nonzero entries in a row exceeds the guess, you still need to reallocate and copy.