Using realloc for dynamic array size vs. initial size in C

Calling realloc many times would be inefficient. So adding one memory size is a bad idea. Double the size and when you are done and get the exact size you wanted for storing the data you can realloc down to that size. That should take care of wasted memory. But realloc down only at the end when you think you don't need to to increase anymore.

Depending on the particular situation and your implementation if you think doubling is bit too much when the total memory allocated becomes big you can add checks to incrementally add memory. Something like

if (memory_allocated < 100)
   //realloc to double size
else
  //realloc 10 more

The numbers above are arbitrary and you can choose better ones. But use this if doubling the memory is a huge concern. Otherwise doubling and reallocing down to exact is a good enough solution.

Apart from doubling the array size using realloc to improve the allocation performance, I'd ask if you really need O(1) access time to each of the Move items. If not you could also use a list instead, like:

typedef struct Move Move;
struct Move {
    /* your stuff here */
    Move *next;
};

With this in mind, you could add a new Move item to the lists head or tail each time you create a new one. But here you'd end up with O(n) access time for random access to the Move items.

You could double. But if you are concerned about the time and wasted space, you need to know the distribution of the number of moves. That is, what percent of the time are there 1 moves, 2 moves, etc. Then a method might be clearer. Such as double when number of moves is <= 100, but add 20 for greater than 100.

Initially, write code into your game that tracks these stats and adjust your method accordingly.

suppose you have an array of n elements,and now it is full. everytime you call realloc(), every elements will be moved to a new space.

realloc(size+1):

the sum of moves is 1+2+...+n = O(n^2)

(even if it begins as k+k+1...+n, it turns out to be O(n^2), where k is the original space you malloc)

realloc(size*2) even if the original space is just one:

the sum of moves is n*(1/2+1/4+...+1/(2^logn)),(2^logn = n) and the sum's upper bound is 2n, that's to say, O(n).

it's clear that, when the number of total element is quite few, they are almost same.But if the n is large, the double one is more efficient.

by the way, the one which double the size when array is full,is a popular implement of many dynamic array.

Increasing by constant amount will lead to each insertion to cost O(n), therefore inserting n elements will have time complexity of O(n²).

The amortized cost of inserting a single element when you increase the allocation by a constant factor is O(1), which means O(n) for insertion of n elements. You don't need to double every time, allocating just 25 % or 20 % or just 15 percent more at most will overallocate that 15 %, and you will still get the O(1) amortized cost per insertion. With 15 % say, the O(1) will have a higher constant factor, but on average will now overallocate much less than with 100 % increment every time the buffer is full.

No contest. Choose an arbitrary size and double it each time you need to allocate more memory. The function calls to realloc() for every single struct you need to add would cause your program to be slow.

realloc() is also expensive. Every time you call it, you're going to use a new block of memory on the heap. realloc() does free the originally allocated block when the new memory is successfully allocated; however, this leads to heap fragmentation and you run the risk of running out of contiguous memory to allocate even though there's plenty of free memory.

Finally, every time you call realloc(), you run the risk of the memory allocation failing. Why not minimize the risk by calling it as few times as possible?