C: Allocate memory ahead or on every demand?

Question

I've got a simple (propably) question for you. When creating own dynamic array implementation in C, is it better to allocate memory ahead(let's presume, for 10 elements) when an array is close to reach its current maximum capability, or to realloc memory every time when element count changes?

I mean: for performance, elegance or whatever comes to your mind.

Answer 1

The usual choice is to multiple the current size by a fixed number greater than one (1.5ish is common, as is 2) which gets you amortized O(n) total allocation and copying costs.

Note that there is no guarantee that you can increase the size of the array in place, so you may have to copy all the existing elements to the new location (realloc() does this automatically for you, but you still have to pay the cost).

Answer 2

It's much better for performance to realloc as few times as possible. So you can do something like:

array = realloc(array, old_size * 2);