How much overhead does realloc calls?

Question

I use realloc in every iteration of the for loop, which repeats more than 10,000 times.

Is this a good practice? Will realloc cause an error if it has been called many times?

Answer 1

This will not work if you do not run out of memory (which will happen with any other allocator), but your code will work much faster if you manage to evaluate the preliminary reserve.

It is often best to run an extra loop just to determine storage requirements.

I would not say that realloc is not-go, but it is not a good practice.

Answer 2

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

As for the extra loop, to determine how many bytes of memory are needed,

Using an extra loop is not always or even often better. What is involved in deciding how much memory is required? This can lead to additional I / O, which are costly and undesirable.

Regarding the use of realloc in general,

The family of alloc functions (malloc, calloc, realloc and free) is very efficient. The basic distribution system extracts a large block from the OS and then transfers the details to the user upon request. Successive calls to realloc will almost certainly just touch extra space in the current memory location.

You do not want to independently maintain a bunch of pools if the system does this for you more efficiently and correctly from the very beginning.

Answer 3

You risk fragmenting your memory if you do. This leads to poor performance, and for 32-bit systems it can lead to a lack of memory due to the lack of availability of large contiguous memory blocks.

I assume that you increase the length of the array by 1 each time. If so, you track capacity and length much better and only increase capacity when you need a length that exceeds the current capacity. When you increase capacity, do it more than just 1.

Of course, standard containers will do such things for you, so if you can use them, it’s best to do this.

Answer 4

In addition to what was said earlier, a few more things are needed:

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

• malloc(N + inc) speed malloc(N + inc) , which usually worsens in the O(N) direction with the size of the allocated block
• memcpy(newbuf, oldbuf, N) speed memcpy(newbuf, oldbuf, N) , which is also O(N) with block size

This means that for small increments but large existing blocks, realloc() performance is O(N^2) relative to the size of the existing data block. Think of bubbles versus quicksort ...

It is relatively cheap if you start with a small block, but will significantly punish you if the redistributed block is large. To reduce, you must make sure that inc not small relative to the existing size; realloc'ing a constant value is a recipe for performance problems.

In addition, even if you grow in large increments (say, scale the new size to 150% of the old), it uses a burst of memory usage from reallocating a large buffer; When copying existing content, you use the amount of memory twice. Sequence:

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

therefore fails (a lot) earlier than:

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

There are data structures that do not require realloc() growth; linked lists, skip lists, spanning trees can add data without having to copy existing data. C ++ vector<> grows this way, it starts with an array for the initial size and continues to be added if you grow it above this, but it will not be realloc() (i.e.Copy). Consider implementing (or using a pre-existing implementation) something like this.

Answer 5

In C:

Used correctly, there is nothing wrong with realloc. However, it is easy to use it incorrectly. See Writing Solid Code for an in-depth discussion of all methods of intercepting a realloc call and additional complications that may arise during debugging.

If you redistribute the same buffer over and over again with a small increase in incremental size, keep in mind that it is usually much more efficient to allocate more space than you need and then keep track of the actual space. If you exceed the allocated space, select a new larger buffer, copy the contents, and empty the old buffer.

In C ++:

You should probably avoid realloc (as well as malloc and free). If possible, use the container class from the standard library (for example, std :: vector). They are well tested and well optimized and relieve you of the burden of many homework on managing memory correctly (for example, with eliminating exceptions).

C ++ has no concept of redistributing an existing buffer. Instead, the new buffer is allocated at a new size, the contents are copied, and the old buffer is deleted. This is what realloc does when it cannot satisfy the new size in the existing location, which makes it look like a C ++ approach less efficient. But it rarely happens that realloc can actually use redistribution in place. C ++ standard containers are pretty smart about distribution in such a way as to minimize fragmentation and amortize the cost of many updates, so you should usually not try to chase realloc if you want to improve performance.

Answer 6

you have to redistribute sizes that have a force of 2. This is the policy used by stl, and the good thing is that it is memory driven. realloc donesn't fail, unless you run out of memory (and it returns NULL) but copies the existing (old) data to a new location and may be a performance issue.

Answer 7

If you realloc () is the same buffer in the loop, I don't see a problem if you have enough memory for the horror of additional memory requests :)

usually realloc () will expand / contract the existing allocated space that you are working against and will return the same pointer to you; if he cannot do it locally, then copy and freedom are involved, so in this case realloc () becomes expensive; and you will also get a new pointer :)