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?

Trinee

What exception? Do you mean C++? Use C++ things. Do you mean C? There are no exceptions in C. – Lundy

Please do not tag questions C and C++. The answer usually differ depending on the language you are actually using. In C++, I would ask why you are manually managing memory at all? – Reverent

There are no exceptions in C functions, but you risk a null pointer return if the realloc fails. Why not allocate a reasonable size buffer and keep that until you need something bigger? Or use a standard container that manages the memory for you? – Renie

use a container instead? – Secret

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.

Dickdicken

If you can run an extra loop to determine storage then it's good to do so. But in many situations it's not really possible since you need to deal with each item once and for all as it arrives. – Strainer

Even without an extra loop you can reduce the number of reallocs by rule-of-thumb heuristics like increasing the amount of memory allocated as a factor of the total size, rather than just one object at a time (e.g. you might start with room for 100 objects and when that is full add another 50% (bring the total to 150), then another 50% (to 225), and another (to 338) and so on... – Longwinded

Yes, if you need to use realloc (i.e. in the case described by David, leaving out obvious C++ alternatives), make sure you use it with care. Re-allocating for every single loop iteration is a bad idea. But I think the search for the best growth factor for arrays is a different topic that has already been debated a lot on SO. – Dickdicken

"[R]un out of memory" might be too much of a simplification. When memory is fragmented, an allocation can fail even when there's enough space but it's simply not contiguous. Since the question hints strongly at many incremental reallocations, fragmentation seems like a real concern. – Abscission

An extra loop will most certainly introduce overhead that is more expensive than calling realloc multiple times. The alloc family of functions are very efficient and will do a better and more efficient job than the user maintaining their own heap pool. – Magnetochemistry

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.

Magnetochemistry

Answer 3

You run the risk of fragmenting your memory if you do this. This causes performance degredation and for 32 bit systems can lead to memory shortages due to lack of availability of large contiguous blocks of memory.

I'm guessing you are increasing the length of an array by 1 each time round. If so then you are far better keeping track of a capacity and length and only increasing the capacity when you need a length that exceeds the current capacity. When you increase the capacity do so by a larger amount than just 1.

Of course, the standard containers will do this sort of thing for you so if you can use them, it's best to do so.

Strainer

Answer 4

In addition to what's being said before, there's a few more things to consider:

Performance of realloc(<X-sized-buf>, X + inc) depends on two things:

1. the speed of malloc(N + inc) which usually degrades towards O(N) with the size of the allocated block
2. the speed of memcpy(newbuf, oldbuf, N) which is also O(N) with the size of the block

That means for small increments but large existing blocks, realloc() performance is O(N^2) with respect to the size of the existing data block. Think bubblesort vs. quicksort ...

It's comparatively cheap if you start with a small block but will significantly punish you if the to-be-reallocated block is large. To mitigate, you should make sure that inc is not small relative to the existing size; realloc'ing by a constant amount is a recipe for performance problems.

Additionally, even if you grow in large increments (say, scale the new size to be 150% of the old), there's the memory usage spike from realloc'ing a large buffer; during the copy of the existing contents you use twice the amount of memory. A sequence of:

addr = malloc(N);
addr = realloc(addr, N + inc);

therefore fails (much) sooner than:

addr[0] = malloc(N);
addr[1] = malloc(inc);

There are data structures out there which do not require realloc() to grow; linked lists, skip lists, interval trees all can append data without having to copy existing data. C++ vector<> grows in this fashion, it starts with an array for the initial size, and keeps on appending if you grow it beyond that, but it won't realloc() (i.e. copy). Consider implementing (or using a preexisting implementation of) something like that.

Mcentire

Speaking of memory spikes, one of the stupidest uses of realloc I've seen is resizing a buffer whose contents you don't intend to use, rather than just freeing it and allocating a new one... – Gloucestershire

Ack, right after the realloc(buf, size++) magic ... there's an endless supply of bad ideas. – Mcentire

How do you come up with O(N^2) for realloc? Two separate operations that are each O(N) is still considered just O(N). In order to get O(N^2), you would have to have for each item n in N another O(N) complexity operation performed on the item. – Juvenile

@Jason: you're correct on that, me bad. That said ... if you say it's (i + k)*O(N) with i the share of malloc() and k that of memcpy(), you still end up with k >> i for large memory blocks - a cost you may not want to bear. My statement re C++ vector<> is also no longer correct; the behaviour was allowed pre-C++11, but C++11 requires contiguous mem for the vector contents, and therefore cannot avoid the copy on resize anymore. – Mcentire

Answer 5

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.

Nelle

STL implementations may have an advantage there, of knowing what the default memory allocator is on the implementation. I've worked on systems where powers of 2 are the worst possible sizes in terms of efficiently using memory, because the allocator has to add a small header and then rounds the required size to an even block. In that case, powers of two pretty much maximise unused space. – Constrictor

There is nothing magic about powers of two. You should just realloc with exponentially-increasing sizes to avoid O(n^2) loop performance, but the base can be any value greater than 1, not necessarily 2. Lots of people like 1.5 (growing the buffer 50% each time you run out of space). – Gloucestershire

@Steve: true, but that's a particular case that can be handled if it is the case. @R. it's not magic but it's optimal to alloc sizes that are power of 2:), the reason is the page size that can be 4k or 2Mb. – Nelle

@Nelle you might match the page size for the block that you allocate, but there's the overhead too. Factor in sub-allocation too, the fact that your memory request is dealt with my a sub-allocator rather than the main system allocator. So, that argument certainly does not show optimality of powers of 2. – Strainer

@David: how can I set an allocator under malloc ? It's just a wrapper over HeapAlloc. New operator however can be overwritten, but as I have said: it;s a particular case of which you must be aware and handle. – Nelle

@Nelle You don't set an allocator. Your C or C++ libraries come with one. It will get memory from the system but then sub-allocate from that. So whilst you may think it's clever to call malloc (or any allocation function) with powers of 2 and values equal to multiples of the page size, but that's all gobbled up by the library which allocates larger blocks and sub-allocates from within. Far and away the best strategy is to use the standard containers. – Strainer

according to c:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\crt\src\malloc.c, malloc calls (indirectly) HeapAlloc with the same size(more exactly "size ? size : 1") . in some particular cases what you are saying it's true, but as i have write above this is not the general case... – Nelle

Answer 6

In C:

Used properly, there's nothing wrong with realloc. That said, it's easy to use it incorrectly. See Writing Solid Code for an in-depth discussion of all the ways to mess up calling realloc and for the additional complications it can cause while debugging.

If you find yourself reallocating the same buffer again and again with only a small incremental size bump, be aware that it's usually much more efficient to allocate more space than you need, and then keep track of the actual space used. If you exceed the allocated space, allocate a new buffer at a larger size, copy the contents, and free the old buffer.

In C++:

You probably should avoid realloc (as well as malloc and free). Whenever possible, use a container class from the standard library (e.g., std::vector). They are well-tested and well-optimized and relieve you of the burden of a lot of the housekeeping details of managing the memory correctly (like dealing with exceptions).

C++ doesn't have the concept of reallocating an existing buffer. Instead, a new buffer is allocated at the new size, contents are copied, and the old buffer is deleted. This is what realloc does when it cannot satisfy the new size at the existing location, which makes it seem like C++'s approach is less efficient. But it's rare that realloc can actually take advantage of an in-place reallocation. And the standard C++ containers are quite smart about allocating in a way that minimizes fragmentation and about amortizing the cost across many updates, so it's generally not worth the effort to pursue realloc if you're goal is to increase performance.

Abscission

Answer 7

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.

Alysonalysoun

Answer 8

if you're realloc()-ing the same buffer in the loop I see no problems as long as you have enough memory to horror the additional memory requests :)

usually realloc() will extend/shrink the existent allocated space you're working against and will give you back same pointer; if it fails to do so inplace then a copy and free are involved so in this case the realloc() gets to be costly; and you also get a new pointer :)

Technique

I see the "horror" instead of "honor" as a kind of a freudian slip. :-) Surely calling realloc() 10000 times looks like an extreme case of indecision. Why not settle on a resonable size, and keep that? – Renie

that's a slip alright cuz i consider meself a junger :) extreme is a tough word, what about poor man's quicktool against a smart but complicated algorithm? re, "setting on a reasonable size", thats what realloc is exactly for, when one can't properly figure the number. i'm thinking getline(3)'s impl for example; also the software tester must feed his family, right? where will he be without these indecisions? realloc may feed the hungry if not properly used; on the other hand, each unfreed pointer kills a kitten! save the kittens! – Technique