C++ 25 Feb 2012 13:19:21
C++ vector vs realloc()
A comparison of how many reallocations a worse case poorly coded use of realloc() does, compared to just using std::vector. 10000000 integers are added to the containers one-by-one. Clearly you would never abuse realloc() like this in real code, but it’s interesting nonetheless. Idea from sacrebleu at Freenode’s ##C++.
The full source is available in svn as a CMake project for easy cross-platform testing. Primary source vector-realloc.cpp
| Allocs / OS | std::vector | realloc() |
|---|---|---|
| Windows 7 | 40 | 9526 |
| Linux: Arch | 24 | 367 |
| Linux: Fedora 10 | 24 | 438 |
| Mac OS X | 24 | 31 |
- Mac OS X: OS X 10.7.3, 2.3 GHz Core i5, 8 GiB RAM. XCode 4.3, clang++ 3.1 -std=c++0x -stdlib=libc++ -O3.
- Windows 7: 64 bit, 1.60GHz Core i7 Q720, 8 GiB RAM. MSVC++ 2010 _SECURE_SCL=0
- Linux: Arch: VirtualBox on the Windows machine, VT-x, Arch Linux, kernel 3.2.7-1-ARCH x86_64, 1 GiB RAM. GNU g++ 4.6.2 -std=c++0x -O3
- Linux: Fedora 10: Fedora 10, kernel 2.6.27 x86_64, 2.66GHz Xeon, 8 GiB RAM. GNU g++ 4.4.1 -O3
on 12 Aug 2012 at 13:01:39 1.Ivan said …
This test incorrect. Try to swap “realloc” and “vector.resize”.
When copying by realloc, frees block of memory that allows the vector to take it without a copy.
on 12 Aug 2012 at 13:21:31 2.Tino Didriksen said …
I like the way you think, but you clearly didn’t try that yourself.
It makes no difference, and couldn’t make a difference as the chunk that realloc() releases is not the right size for std::vector’s growth factor, so std::vector does not grab it.
on 12 Aug 2012 at 22:25:39 3.Ivan said …
OK. I tried =) You are right.
But if you act according to “vector” logic and do small optimization:
if(cap < i + 1) {
cap += cap / 2;
if(cap < i + 1) {
cap = i + 1;
}
c = (int*)realloc(c, sizeof(*c)*cap);
}
c[i] = i;
On windows 7:
realloc() reallocations: 18
std::vector reallocations: 40
on 12 Aug 2012 at 22:42:44 4.Tino Didriksen said …
Sure, but then it devolves into what the “correct” growth factor is and whether you should use custom code or just trust the stdlib. The various C++ stdlibs grow std::vector at a pace that fits 99% of use cases.
This really was just a silly “what if the coder was a moron” test, which realloc() naturally loses. Except on OS X, which is in the same order of magnitude.