Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Differences between using realloc vs. free -> malloc functions

Why would one use realloc() function to resize an dynamically allocated array rather than using free() function before calling the malloc() function again (i.e. pros and cons, advantages vs. disadvantages, etc.)? It's for C programming, but I can't find the proper tag for it. Thanks in advance.

like image 971
stanigator Avatar asked Sep 09 '09 18:09

stanigator


People also ask

What is the difference between malloc and realloc?

The malloc() and realloc() functions are part of dynamic memory; malloc() is used for the memory allocation and realloc() is used for the reallocation of the memory.

What is the difference between realloc () and free ()?

To avoid waste of memory or the memory leak (memory leaks), then we should do the reallocation of the spaces memory previously allocated by function malloc (), calloc () or realloc (). In the C language, this process will be carried out by using function free () which has the form of a pointer parameter.

What is difference between calloc () malloc () and free () functions?

malloc() function creates a single block of memory of a specific size. calloc() function assigns multiple blocks of memory to a single variable.


1 Answers

While this benchmark is not definitive since memory management varies across different systems, nowadays things tend to be pretty standarized, so these results should be safe to use as a reference point (If you know of a real life case it isn't, please tell me). I'm using Windows 7 on an 2.10GHz QuadCore Intel Core i3 2310M with 4GB RAM. Not the best hardware ever, but the best I have around now.

What this benchmark does is it starts with a certain amount of memory (INITIAL_MEMORY) and repeatedly reallocates by small amounts (BYTE_STEP) until it fully allocates/deallocates ALLOCATE_MEMORY. For this, it tries 6 approaches:

  1. Increasing Lossful Malloc: free() and malloc() more memory.
  2. Decreasing Lossful Malloc: free() and malloc() less memory.
  3. Increasing Malloc: malloc() more memory, copy data and free() previous memory.
  4. Decreasing Malloc: malloc() less memory, copy data and free() previous memory.
  5. Increasing Realloc: realloc() more memory.
  6. Decreasing Realloc: realloc() less memory.

So, first test: Start with 2MB and allocate ±1MB in 1KB steps:

Increasing Lossful Malloc took 3 ms Decreasing Lossful Malloc took 5 ms Increasing Malloc took 1 265 ms Decreasing Malloc took 744 ms Increasing Realloc took 316 ms Decreasing Realloc took 0 ms 

As we can see, copying manually with memcpy is always slower than realloc, because in this scenario malloc is guaranteed to allocate new memory and you're forced to copy the data in every allocation, which shows us that realloc is indeed reusing the same address and enlarging the block size in some cases. So if you want to keep your data, realloc is probably what you want to use. In order to simplify things, I won't keep testing this lossless malloc approach.

Let's proceed to the next test: 32MB initial memory, 16MB allocation in 16KB steps:

Increasing Lossful Malloc took 4 ms Decreasing Lossful Malloc took 4 ms Increasing Realloc took 21 453 ms Decreasing Realloc took 0 ms 

Now, we can see that increasing realloc takes a lot of time compared to the other tests. Decreasing realloc hasn't even reached 1 ms. This shows that if you don't want to keep your memory you should use a free->malloc approach, or does it? Look at these results:

Increasing Lossful Malloc took 777 ms Decreasing Lossful Malloc took 729 ms Decreasing Realloc took 19 ms 

(These results were too close, so I run several tests and averaged them.)

Definitely decreasing the memory size is more efficient when using realloc(). That's probably because realloc doesn't need to search for a new memory block, it just uses the previous one and shrinks it. This is a big difference in performance if you're using allocation heavily.

Also, we can see that the increasing malloc is slightly slower than the decreasing one, even when both do basically the same: find a memory block and allocate it. This difference is probably because when searching for bigger blocks malloc needs to search longer in average than when searching for smaller blocks. For example, if there is a 30MB block, a malloc allocating 16MB would use it, but a malloc allocating 32MB would have to skip it and keep searching and using up time. This is probably why results varied so much in my tests.

In conclusion/TLDR:

  1. If you need to keep your data, use realloc(). It's ~4 times faster than using malloc()/free() and copying your data when scaling up. When scaling down it is 10,000-100,000 times faster. NEVER copy stuff manually.
  2. If you don't need to keep your data, you should use malloc()/free() to scale up (increasing memory size) but use realloc() when scaling down (reducing memory size).
  3. If you don't know the previous size (you don't know wether you're scaling down or up), use malloc()/free(). When scaling down, realloc() is ~40 times faster, but when scaling up, realloc() is ~7600 times slower. Unless your program does a few huge allocations and tons of little deallocations (~200 times more deallocations than allocations, which can be possible), you should use malloc()/free().

Here's my benchmark source: test.cpp

like image 146
negamartin Avatar answered Sep 27 '22 19:09

negamartin