Differences between using realloc vs. free -> malloc functions
I had a program that was doing a bunch of free() and malloc() calls to make a dynamic array, and I thought I'd optimize by reusing the existing array when possible. Benchmarks showed that realloc() on average is slower than just calling free() and malloc(). I guess it makes sense, since sometimes it would grow, and maybe require copy.
The advantage is that realloc will preserve the contents of the memory. With free + malloc you'd need to reset the data in the array.
Well, realloc may change the size of the block in place, or allocate a new one and copy as much as will fit. In contrast, malloc and free together can only allocate a new one, and you have to do your own copying.
To be frank, realloc doesn't get as much use these days because it doesn't work well with C++. As a result, there's been a tendency for memory managers not to optimize for it.
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:
- Increasing Lossful Malloc: free() and malloc() more memory.
- Decreasing Lossful Malloc: free() and malloc() less memory.
- Increasing Malloc: malloc() more memory, copy data and free() previous memory.
- Decreasing Malloc: malloc() less memory, copy data and free() previous memory.
- Increasing Realloc: realloc() more memory.
- 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:
- 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.
- 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).
- 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