Disadvantages of calling realloc in a loop

Question

I'm trying to implement some math algorithms in C on Windows 7, and I need to repeatedly increase size of my array.

Sometimes it fails because realloc can't allocate memory. But if I allocate a lot of memory at once in the beginning it works fine.

Is it a problem with the memory manager? Can anyone explain me this please?

Answer 1

1. When you allocate/deallocate memory many times, it may create fragmentation in the memory and you may not get big contiguous chunk of the memory.
2. When you do a realloc, some extra memory may be needed for a short period of time to move the data.

If your algorithm does not need contiguous memory or can be changed to work on non-contiguous memory, consider using linked-lists of array (Something link std::dequeue of C++) that will avoid copying of data and your code may not suffer OOM. If you know the worst case memory requirement for the array, it is better to keep that memory allocated from the beginning itself, as it will avoid the cost of allocation and data moving when compared with realloc.

Answer 2

I you want your algorithms to work fast, try to do all the memory allocation up front. Memory allocation is an unbounded operation and will kill your performance. So speculate a reasonable worst case and allocate enough for that. If you do need to realloc later fine but don't do so continuously.