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 / OSstd::vectorrealloc()
Windows 7409526
Linux: Arch24367
Linux: Fedora 1024438
Mac OS X2431
  • 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
Share

4 Responses to “C++ vector vs realloc()”

  1. 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.

  2. 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.

  3. 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

  4. 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.

Subscribe to the comments through RSS Feed

Leave a Reply

*
To prove you're a person (not a spam script), type the security word shown in the picture. Click on the picture to hear an audio file of the word.
Anti-spam image