I use an example from finite element theory, but anybody who maintains a large datastructure and successively extends it will find something similar.
Suppose I have an unstructured mesh of points and triangles, where the points are given by coordinates (say $x$ and $y$) and the triangles each consist of three point indices (say $i$,$j$ and $k$).
As common in FEM, the mesh will be successively refined. If we resort to global regular refinement, the number of triangles will grow by factor $4$ with each iteration of the refinement. Depending on how this is done, the memory layout will develop differently.
Say the mesh occopies memory cells 1 to 300, anything beyond there being free.
Example 1:
We allocate the space for the new mesh, cells 301 to 1501, fill it up with the data of the refined mesh, and forget the old one. The next refined mesh will be placed in cells 1501 to 6300, the next one in 6301 to 21500, and so on. The location of the current mesh will move in memory "to the right", while a huge patch will not be used. We may run out of memory prematurely.
One might observe in the above example, that this will only hinder us for one refinestep, because even without that fragmentation we would run out of total memory one refinement later. As the vertex array is taken into account, too, the problem can become more severe.
How can this be circumvented?
Example 2:
Realloc the triangle array to cells 1..1200. Create the new mesh in cells 1201 to 2400. Copy the content of that working copy to cells 1..1200, and forget the working copy. Repeat similarly.
Ok, still we run out of memory prematurely, because we need a working copy. How about this:
Example 3:
Realloc the triangle array to cells 1..1500. Copy old mesh to 1201 .. 1500. Create new mesh in cells 1..1200. Then forget the copy of the old mesh.
The case here is artificial, because one would not use global mesh refinement on these scales. If the growth is much smaller, memory realignment is possible to avoid fragmentation. However,
Questions:
Does memory fragmentation ever become critical in practical scientific computing/high-performance computing?
If at all, how do you avoid it? Maybe my machine model is even wrong, and the OS by some heavy magic does realign the memory tacitly, or manages fragmented blocks on the heap.
More specific, how does it impact grid management?