5

When making automatically expanding arrays (like C++'s std::vector) in C, it is often common (or at least common advice) to double the size of the array each time it is filled to limit the amount of calls to realloc in order to avoid copying the entire array as much as possible.

Eg. we start by allocating room for 8 elements, 8 elements are inserted, we then allocate room for 16 elements, 8 more elements are inserted, we allocate for 32.., etc.

But realloc does not have to actually copy the data if it can expand the existing memory allocation. For example, the following code only does 1 copy (the initial NULL allocation, so it is not really a copy) on my system, even though it calls realloc 10000 times:

#include <stdlib.h>
#include <stdio.h>

int main()
{
    int i;
    int copies = 0;
    void *data = NULL;
    void *ndata;

    for (i = 0; i < 10000; i++)
    {
        ndata = realloc(data, i * sizeof(int));
        if (data != ndata)
            copies++;
        data = ndata;
    }
    printf("%d\n", copies); 
}

I realize that this example is very clinical - a real world application would probably have more memory fragmentation and would do more copies, but even if I make a bunch of random allocations before the realloc loop, it only does marginally worse with 2-4 copies instead.

So, is the "doubling method" really necessary? Would it not be better to just call realloc each time a element is added to the dynamic array?

Mike Pedersen
  • 1,056
  • 10
  • 18
  • 3
    Your O(N) algorithm is fundamentally worse than the O(logN) algorithm that doubling the allocation provides. – Hans Passant Dec 07 '13 at 23:37
  • 1
    Your algorithm is a steadily increasing memory demand with no intervening deallocations, so of course it never needs to copy. Try adding randomly sized and randomly interspersed `malloc` and `free` calls in your loop. – Carey Gregory Dec 07 '13 at 23:38
  • @Mike, you always have to do "worst-case" considerations here: Consider the case that a copying is necessary in every step. In this case, you live definitely better with that method. You don't have to double it every time, you can as well `* 1.5` it, that leads to a slower growth rate, but is still better than `+ 1` in every step. Even `+ 1000`ing it when needed would be better than `+ 1`, but doesn't scale so good. But if you have a certain maximum limit, that might be ok as well. – glglgl Dec 08 '13 at 00:21

3 Answers3

5

You have to step back from your code for a minute and thing abstractly. What is the cost of growing a dynamic container? Programmers and researchers don't think in terms of "this took 2ms", but rather in terms of asymptotic complexity: What is the cost of growing by one element given that I already have n elements; how does this change as n increases?

If you only ever grew by a constant (or bounded) amount, then you would periodically have to move all the data, and so the cost of growing would depend on, and grow with, the size of the container. By contrast, when you grow the container geometrically, i.e. multiply its size by a fixed factor, every time it is full, then the expected cost of inserting is actually independent of the number of elements, i.e. constant.

It is of course not always constant, but it's amortized constant, meaning that if you keep inserting elements, then the average cost per element is constant. Every now and then you have to grow and move, but those events get rarer and rarer as you insert more and more elements.

I once asked whether it makes sense for C++ allocators to be able to grow, in the way that realloc does. The answers I got indicated that the non-moving growing behaviour of realloc is actually a bit of a red herring when you think asymptotically. Eventually you won't be able to grow anymore, and you'll have to move, and so for the sake of studying the asymptotic cost, it's actually irrelevant whether realloc can sometimes be a no-op or not. (Moreover, non-moving growth seems to upset moder, arena-based allocators, which expect all their allocations to be of a similar size.)

Community
  • 1
  • 1
Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
3

Compared to almost every other type of operation, malloc, calloc, and especially realloc are very memory expensive. I've personally benchmarked 10,000,000 reallocs, and it takes a HUGE amount of time to do that.

Even though I had other operations going on at the same time (in both benchmark tests), I found that I could literally cut HOURS off of the run time by using max_size *= 2 instead of max_size += 1.

ciphermagi
  • 747
  • 3
  • 14
2

Q: 'doubling the capacity of a dynamic array necessary"
A: No. One could grow only to the extent needed. But then you may truly copy data many times. It is a classic trade off between memory and processor time. A good growth algorithm takes into account what is known about the program's data needs and also not to over-think those needs. An exponential growth of 2x is a happy compromise.

But now to your claim "following code only does 1 copy".

The amount of copying with advanced memory allocators may not be what OP thinks. Getting the same address does not mean that the underlying memory mapping did not perform significant work. All sorts of activity go on under-the-hood.

For memory allocations that grow & shrink a lot over the life of the code, I like grow and shrink thresholds geometrically placed apart from each other.

const size_t Grow[]   = {1, 4, 16, 64, 256, 1024, 4096, ... };
const size_t Shrink[] = {0, 2,  8, 32, 128,  512, 2048, ... };

By using the grow thresholds while getting larger and shrink one while contracting, one avoid thrashing near a boundary. Sometimes a factor of 1.5 is used instead.

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
  • 1
    You make a good point by saying that the allocator might do a lot of work even if it returns the same address. I did not consider that. – Mike Pedersen Dec 08 '13 at 11:13