Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

(This is not game programming per se, but I'm certain if I asked this on SO I'd get told not to prematurely optimize, even though history tells us every large game ends up worrying about these things.)

Is there a document anywhere that summarizes the differences in performance, and particularly memory usage, between different C++ standard library implementations? The details of some implementations are protected by NDA, but a comparison between even STLport vs. libstdc++ vs. libc++ vs. MSVC/Dinkumware (vs. EASTL?) seems like it would be immensely useful.

In particular I'm looking for answers to questions like:

  • How much memory overhead is associated with the standard containers?
  • What containers, if any, do dynamic allocations merely by being declared?
  • Does std::string do copy-on-write? Short string optimization? Ropes?
  • Does std::deque use a ring buffer or is it crap?
share|improve this question
    
I was under the impression that deque was always implemented in the STL with a vector. –  Tetrad Jul 31 '11 at 7:55
    
@Tetrad: Until a few weeks ago I was too, but then I read it was often implemented by a rope-like structure - and that seems to be what's in STLport. –  user744 Jul 31 '11 at 8:05
    
The STL has an open working-draft, which can be used to find information regarding the various data structures (both sequential and associative), algorithms and helper classes implemented. However, it appears to be the case that memory overhead is implementation specific, rather than specification defined. –  Shaktal Jul 31 '11 at 11:46
2  
@Duck: Game development is the only place I'm aware of that regularly uses high-level C++ features yet needs to meticulously track memory allocations because it runs on low-memory no-virtual-memory systems. Every single answer on SO would be "don't prematurely optimize, the STL is fine, use it!" - 50% of the answers here so far are that - and yet Maik's test clearly shows a major concern for games wishing to use std::map, and Tetrad's confusion and mine about common std::deque implementations likewise. –  user744 Jul 31 '11 at 13:18
2  
@Joe Wreschnig I don't really want to vote to close because I'm interested in the outcome of this. :p –  The Communist Duck Jul 31 '11 at 14:18

3 Answers 3

up vote 5 down vote accepted

In case you don't find such a comparison chart, the alternative is to inject an own allocator to the STL classes in question and add some logging.

The implementation I tested (VC 8.0) uses no memory allocation just by declaring a string/vector/deque, but for it does list and map. The string has a short string optimization, since adding 3 chars didn't trigger an allocation. The output is added below the code.

// basic allocator implementation used from here
// http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <map>

template <class T> class my_allocator;

// specialize for void:
template <> 
class my_allocator<void> 
{
public:
    typedef void*       pointer;
    typedef const void* const_pointer;
    // reference to void members are impossible.
    typedef void value_type;
    template <class U> 
    struct rebind 
    { 
        typedef my_allocator<U> other; 
    };
};

#define LOG_ALLOC_SIZE(call, size)      std::cout << "  " << call << "  " << std::setw(2) << size << " byte" << std::endl

template <class T> 
class my_allocator 
{
public:
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef T         value_type;
    template <class U> 
    struct rebind 
    { 
        typedef my_allocator<U> other; 
    };

    my_allocator() throw() : alloc() {}
    my_allocator(const my_allocator&b) throw() : alloc(b.alloc) {}

    template <class U> my_allocator(const my_allocator<U>&b) throw() : alloc(b.alloc) {}
    ~my_allocator() throw() {}

    pointer       address(reference x) const                    { return alloc.address(x); }
    const_pointer address(const_reference x) const              { return alloc.address(x); }

    pointer allocate(size_type s, 
               my_allocator<void>::const_pointer hint = 0)      { LOG_ALLOC_SIZE("my_allocator::allocate  ", s * sizeof(T)); return alloc.allocate(s, hint); }
    void deallocate(pointer p, size_type n)                     { LOG_ALLOC_SIZE("my_allocator::deallocate", n * sizeof(T)); alloc.deallocate(p, n); }

    size_type max_size() const throw()                          { return alloc.max_size(); }

    void construct(pointer p, const T& val)                     { alloc.construct(p, val); }
    void destroy(pointer p)                                     { alloc.destroy(p); }

    std::allocator<T> alloc;
};

int main(int argc, char *argv[])
{

    {
        typedef std::basic_string<char, std::char_traits<char>, my_allocator<char> > my_string;

        std::cout << "===============================================" << std::endl;
        std::cout << "my_string ctor start" << std::endl;
        my_string test;
        std::cout << "my_string ctor end" << std::endl;
        std::cout << "my_string add 3 chars" << std::endl;
        test = "abc";
        std::cout << "my_string add a huge number of chars chars" << std::endl;
        test += "d df uodfug ondusgp idugnösndögs ifdögsdoiug ösodifugnösdiuödofu odsugöodiu niu od unoudö n nodsu nosfdi un abc";
        std::cout << "my_string copy" << std::endl;
        my_string copy = test;
        std::cout << "my_string copy on write test" << std::endl;
        copy[3] = 'X';
        std::cout << "my_string dtors start" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "vector ctor start" << std::endl;
        std::vector<int, my_allocator<int> > v;
        std::cout << "vector ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            v.push_back(i);
        }
        std::cout << "vector dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "deque ctor start" << std::endl;
        std::deque<int, my_allocator<int> > d;
        std::cout << "deque ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "deque insert start" << std::endl;
            d.push_back(i);
            std::cout << "deque insert end" << std::endl;
        }
        std::cout << "deque dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "list ctor start" << std::endl;
        std::list<int, my_allocator<int> > l;
        std::cout << "list ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "list insert start" << std::endl;
            l.push_back(i);
            std::cout << "list insert end" << std::endl;
        }
        std::cout << "list dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "map ctor start" << std::endl;
        std::map<int, float, std::less<int>, my_allocator<std::pair<const int, float> > > m;
        std::cout << "map ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "map insert start" << std::endl;
            std::pair<int, float> a(i, (float)i);
            m.insert(a);
            std::cout << "map insert end" << std::endl;
        }
        std::cout << "map dtor starts" << std::endl;
    }

    return 0;
}

So far VC8 and STLPort 5.2 tested, here is the comparison (included in test: string, vector, deque, list, map)

                    Allocation on declare   Overhead List Node      Overhead Map Node

VC8                 map, list               8 Byte                  16 Byte
STLPort 5.2 (VC8)   deque                   8 Byte                  16 Byte
Paulhodge's EASTL   (none)                  8 Byte                  16 Byte

VC8 output string/vector/deque/list/map:

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    128 byte
my_string copy
  my_allocator::allocate    128 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  128 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    12 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate  12 byte
  my_allocator::allocate    24 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  24 byte

===============================================
deque ctor start
deque ctor end
deque insert start
  my_allocator::allocate    32 byte
  my_allocator::allocate    16 byte
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
  my_allocator::allocate    16 byte
deque insert end
deque dtor starts
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
  my_allocator::allocate    12 byte
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
  my_allocator::allocate    24 byte
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

STLPort 5.2. output compiled with VC8

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::deallocate   0 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
deque ctor start
  my_allocator::allocate    32 byte
  my_allocator::allocate    128 byte
deque ctor end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque dtor starts
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

EASTL results, no deque available

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
  my_allocator::allocate     9 byte
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
  my_allocator::deallocate   9 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
share|improve this answer
    
This is useful to get the details of the underlying allocations, but unfortunately tells us nothing about overhead and expected cache performance. –  user744 Jul 31 '11 at 11:58
    
@Joe right, it's hard to address all your questions in one answer. I'm not sure what exactly you mean with "overhead" and moreover, compared to what? I thought by overhead you mean the memory consumption. –  Maik Semder Jul 31 '11 at 12:27
    
By "overhead" I meant more the size of an empty instances of the structures and all their associated iterators, and how the more complicated ones handle allocation - e.g. does std::list internally allocate more than one node at a time, or do I pay the base allocation cost for each node, etc? –  user744 Jul 31 '11 at 12:31
1  
The question isn't so much "Please do this comparison" as "where is a resource for this comparison" - I don't think SO is a good place to "maintain" it. Perhaps you should start throwing it up on a Google site or wiki or something. –  user744 Jul 31 '11 at 15:41
1  
@Joe well now its here :p I'm not very interested in moving it to another site, I was just interested in the results. –  Maik Semder Jul 31 '11 at 16:15

std::string does not do copy on write. CoW used to be an optimization, but as soon as multiple threads enter the picture it's beyond a pessimisation- it can slow the code by massive factors. It's so bad that the C++0x Standard actively bans it as an implementation strategy. Not just that, but the permissiveness of std::string with dishing out mutable iterators and character references mean that "write" for std::string entails almost every operation.

Short string optimization is about 6 characters, I believe, or something in that region. Ropes are not allowed- std::string must store contiguous memory for the c_str() function. Technically, you could maintain both a contiguous string and a rope in the same class, but nobody ever did it. Moreover, from what I know of ropes, making them thread-safe to manipulate would be incredibly slow- maybe as bad or worse than CoW.

No containers do memory allocation by being declared in modern STLs. Node-based containers like list and map used to do so but now they have an embedded end optimization and don't need it. It's common to perform an optimization called "swaptimization" where you swap with an empty container. Consider:

std::vector<std::string> MahFunction();
int main() {
    std::vector<std::string> MahVariable;
    MahFunction().swap(MahVariable);
}

Of course, in C++0x this is redundant, but in C++03 then when this was commonly used, if MahVariable allocates memory on declaration then it reduces the effectiveness. I know for a fact that this was used for faster reallocations of containers like vector in the MSVC9 STL which removed the need to copy the elements.

deque uses something referred to as an unrolled linked list. It's basically a list of arrays, usually fixed-size in-node. As such, for most uses, it retains the benefits of both data structures- contiguous access and amortized O(1) removal and being able to add to both front and back and better iterator invalidation than vector. deque can never be implemented by vector because of it's algorithmic complexity and iterator invalidation guarantees.

How much memory overhead is associated? Well, honestly, that's a bit of a worthless question to ask. The STL containers are designed to be efficient, and if you were to replicate their functionality, you'd either end up with something that performs worse or in the same spot again. By knowing their underlying data structures, you can know the memory overhead they use, give or take, and it'll only be more than that for a good reason, such as small string optimization.

share|improve this answer
    
"It's so bad that the C++0x Standard actively bans it as an implementation strategy." And they ban it because previous implementations used it, or tried to use it. You apparently live in a world where everyone is using the latest optimally-implemented STL all the time. This answer is not at all helpful. –  user744 Jul 31 '11 at 11:56
    
I am also curious what properties of std::deque you think prevent a contiguous underlying storage - iterators are only valid after removals at the start/end, not in the middle nor after any inserts, which can easily be done with a vector. And using a circular buffer seems to meet all the algorithmic guarantees - amortized O(1) insert and delete at the ends, O(n) delete in the middle. –  user744 Jul 31 '11 at 12:04
3  
@Joe: I think that CoW has been noted to be a bad thing since the late 90s. There are string implementations that used it- notably CString- but that doesn't mean that std::strings of the time did. You don't have to be using the latest and greatest in STL implementations for that. msdn.microsoft.com/en-us/library/22a9t119.aspx says "If an element is inserted at the front, all references remain valid". Not sure how you intend on implementing that with a circular buffer, since you're going to need to resize when it gets full. –  DeadMG Jul 31 '11 at 13:09
    
gotw.ca/publications/optimizations.htm. July 1999. –  DeadMG Jul 31 '11 at 13:15
    
I'm certainly not going to defend COW as an implementation technique, but I am also not naive as to how often software continues to be implemented using poor techniques long after they are identified as poor. For example, Maik's test above reveals a modern stdlib that does allocate on declaration. Thanks for the pointer about deque reference validity. (To nitpick, a vector can meet all the guarantees about iterator invalidation and algorithmic complexity; that requirement is neither.) If anything, I see this as further need for a document like my question asks for. –  user744 Jul 31 '11 at 13:28

The question isn't so much "Please do this comparison" as "where is a resource for this comparison"

If that's really your question (which is most assuredly not what you said in your actual question text, which ended in 4 questions, none of which were asking where you might find a resource), then the answer is simply:

There isn't one.

The majority of C++ programmers don't have to care that much about the overhead of standard library structures, cache performance of them (which is highly compiler dependent anyway), or that sort of thing. Not to mention, you usually don't get to pick your standard library implementation; you use what comes with your compiler. So even if it does some unpleasant things, the options for alternatives are limited.

There are of course programmers who do care about this sort of thing. But they all swore off using the standard library a long time ago.

So you have one group of programmers who simply don't care. And another group of programmers who would care if they were using it, but since they aren't using it, they don't care. Since nobody cares about it, there is no real information about this sort of thing. There are informal patches of information here and there (Effective C++ has a section on std::string implementations and the vast differences among them), but nothing comprehensive. And certainly nothing kept up-to-date.

share|improve this answer
    
Speculative answer. +1 for probably true, -1 for no way of proving it. –  Daniel Aug 3 '11 at 5:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.