C - Is realloc'ing arrays to arrays twice the size efficient in dynamic data structures?

Question

Lately I've been writing a lot of code in C and I've noticed, that the thing that takes most time in my programs is resizing dynamic data structures. Let's say we have an array with characters and I want to append some characters to the end of this array. I do this that way:

1. Check if there is enough memory allocated.
2. If not, realloc array to array having twice the size (using realloc)
3. If there is enough memory now, append the characters, else go to point 2.

I'm just wondering if this is efficient enough. For example I could think of something like a tree structure where I would hold the arrays in nodes of the tree, and that way instead of copying old elements to new array before appending something, I would just add newly malloc'ed elements to the next node of the tree and append the characters there. That way I would avoid unnecessary copying...

So that's just one way of doing that resizing differently. Should I look for something else or is my solution of just copying old elements to new array twice the size efficient enough?

Answer 1

As with all "most efficient" questions, the only way to know is to measure the actual performance in real-life conditions.

Generally speaking, there can be big performance gains from having items in consecutive memory locations, as that's almost always the most cache-friendly layout for any algorithm that's processing the items one after the other. Overall, a consecutive array uses less space, as well, simply because you don't need extra space to store additional data (like tree nodes).

While doubling the size when you need to grow is a common approach, it can tend to eat up address space. Some STL implementations grow structures like vectors by 1.5x instead of 2x to avoid certain pathological cases. In the short term, this leads to more allocations but can lead to less memory fragmentation. That may or may not apply if you're using realloc. It depends how often realloc succeeds in doing it in place.

Answer 2

Usually anything that has logarithmic time complexity (like your reallocation algorithm) is considered "good enough". In general you would only save the copy operation with a list of chunks, but you would still have to access the free store for the new chunks which is always comparatively costly.

Your best bet is probably to perform reasonable heuristics for pre-allocation so that you avoid re-allocs altogether in most cases. Today memory is plentiful, at least if the others show some disciplin ;-).

Answer 3

After accept answer

Efficiency depends on many issue including and profiling will provide an idea for a given siltation.

Certainly growing by a scale factor like 2.0, 1.5, or something in the neighbor provides a nice logarithmic growth.

2 issue not cover elsewhere: shrink and optimistic allocation.

Shrink: Not only do structures grow, they may shrink. Like growth, the reduction should be logarithmic. Yet with reduction can occur thrashing if the threshold of grow/reduction are similar. Recommend that the growth and shrink thresholds are logarithmically evenly spaced. Example: 4x steps,

Grow on size 1, 4, 16, 64, 256 ...
Shrink on 2, 8, 32, 128 ...

Optimistic allocation: Processors with large memory capacity use virtual address spaces often far larger than the physical address space. When allocating memory, say of 1,000,000, no true physical memory is allocated until it is used - (e.g. set to non-zero). Even then, it is only used in chunks of some page size like 4k or 64k bytes. See Why is malloc not "using up" the memory on my computer?

Answer 4

The basic idea of growing allocations by a factor of two is solid, because it makes average reallocation work linear to the maximum array size (every object is moved once on average due to the fact that half the objects are never moved).

The only optimizable point I see in your implementation is that you reallocate several times when the size of the array has to jump: If you have an array of 64 bytes and need 4096 bytes, your realloc() calls first copy 64 bytes, then 128 bytes (64 of which are uninitialized), then 256 bytes, and so on, copying 4032 bytes in total, doing six allocations on the way. Yet all that's needed is to grab memory for 4096 bytes and copy over the 64 bytes. Write your code in a way that you maximally call realloc() once when you grow your allocation.

Another point that can kill performance is a too small starting size. A malloc() call takes more than 250 CPU cycles, and an allocation has an overhead of at least two pointer sized values. You want to make sure that these costs are small relative to your use of the memory. As such, there is usually no point in using an initial allocation for only one element. You want to make sure that the initial allocation is at least in the range of 64 bytes (twenty-five percent space overhead).

Answer 5

Reallocing the array is definitely not most efficient. Realloc ensures contiguous block of memory. Since that may not be possible, realloc may end up allocating new block of memory, copy all of your data to it, and releasing an original block of memory. This can be very expensive, as it is a liner operation in terms of size of your data, with a pretty large constant overhead.

You should really evaluate if you need contiguous block of memory (a tree structure you are describing is an example of non contiguous data structure). If you do, you should try to come up with a technique to estimate how much memory you will need, and minimize reallocing.

It seems to me that you can store your data in an array of pointers to other character arrays. Since top level array stores only pointers, you can pre-allocate it large enough for all practical uses. I don't know enough about your problem to recommend a proper solution, though.