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

I am new to C language (coming from java) and wondering what is a better approach in my situation. I am programming a game and in the function where i generate the moves, i want to return some pointer to an array of structs (a Move is represented by a struct).

Because i don't know in advance what will be the array size, i thought about starting with an empty array an than resize it every time i want to add a move (by realloc(size+1)). but i wonder if it is more optimal to just set an initial size and if i need to,just double the size. what is the better approach performance wize?

Thank you!

Answers


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.


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?


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.


Need Your Help

initWithNibName use partial nib name rather than full nib name

string nsstring xib nib

So i want to initialise my view controller with a nib however i don't want to use the full name of the nib just the first four characters as the remaining characters vary.

Can auto transfer data from memcached to mysql DB?

python mysql django memcached

I'm building a real-time service so my real-time database need to storage in memcached before fetch to DB (Avoid to read/write mysql db too much). I want to fetch data to mysql DB when some events ...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.