How much overhead do realloc calls introduce?

Question

I am using realloc in every iteration of a for loop that iterates more that 10000 times.

Is this a good practice? Will realloc cause an error if it was called a lot of times?

Answer 1

It won't fail unless you've run out of memory (which would happen with any other allocator as well) - but your code will usually run much quicker if you manage to estimate the required storage upfront.

Often it's better to do an extra loop run solely to determine the storage requirements.

I wouldn't say that realloc is a no-go, but it's not good practice either.

Answer 2

I stumbled upon this question recently, and while it is quite old, I feel the information is not entirely accurate.

Regarding an extra loop to predetermine how many bytes of memory are needed,

Using an extra loop is not always or even often better. What is involved in predetermining how much memory is needed? This might incur additional I/O that is expensive and unwanted.

Regarding using realloc in general,

The alloc family of functions (malloc, calloc, realloc, and free) are very efficient. The underlying alloc system allocates a big chunk from the OS and then passes parts out to the user as requested. Consecutive calls to realloc will almost certainly just tack on additional space to the current memory location.

You do not want to maintain a Heap Pool yourself if the system does it for you more efficiently and correctly from the start.

Answer 3

I thought I would add some empirical data to this discussion.

A simple test program:

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

int main(void)
{
    void *buf = NULL, *new;
    size_t len;
    int n = 0, cpy = 0;

    for (len = 64; len < 0x100000; len += 64, n++) {
        new = realloc(buf, len);
        if (!new) {
            fprintf(stderr, "out of memory\n");
            return 1;
        }

        if (new != buf) {
            cpy++;
            printf("new buffer at %#zx\n", len);
        }

        buf = new;
    }

    free(buf);
    printf("%d memcpys in %d iterations\n", cpy, n);
    return 0;
}

GLIBC on x86_64 yields this output:

new buffer at 0x40
new buffer at 0x80
new buffer at 0x20940
new buffer at 0x21000
new buffer at 0x22000
new buffer at 0x23000
new buffer at 0x24000
new buffer at 0x25000
new buffer at 0x26000
new buffer at 0x4d000
new buffer at 0x9b000
11 memcpys in 16383 iterations

musl on x86_64:

new buffer at 0x40
new buffer at 0xfc0
new buffer at 0x1000
new buffer at 0x2000
new buffer at 0x3000
new buffer at 0x4000
new buffer at 0xa000
new buffer at 0xb000
new buffer at 0xc000
new buffer at 0x21000
new buffer at 0x22000
new buffer at 0x23000
new buffer at 0x66000
new buffer at 0x67000
new buffer at 0xcf000
15 memcpys in 16383 iterations

So it looks like you can usually rely on libc to handle resizes that do not cross page boundaries without having to copy the buffer.

The way I see it, unless you can find a way to use a data structure that avoids the copies altogether, skip the track-capacity-and-do-power-of-2-resizes approach in your application and let your libc do the heavy-lifting for you.

Answer 4

you should realloc to sizes that are power of 2. This is the policy used by stl and is good because of the way memory is managed. realloc donesn't fail except when you run out of memory (and will return NULL) but will copy your existing (old) data in the new location and that can be a performance issue.