STL interface

As you are probably aware, game developers have mixed feelings about STL. Sure, it has advantages, it’s already there, doesn’t have to be coded from scratch, it’s standard. On the other hand, the guidelines are very broad, implementations can vary wildly. Performance/memory guarantees seems to be hard to enforce. Even if the interface is always the same, there’s enough wiggle room underneath to seriously break some applications. Take clear() method for example. All it guarantees is that _size() == 0 _afterwards. It doesn’t say anything about memory. I’ve heard of at least one STL implementation that would free container memory in clear().

Paradoxically, in many cases it’s easier to get unified, standard behavior if using own STL version (or portable implementation with known characteristics like STLPort). When creating your own container/algorithm library, you have a choice of dropping STL compatibility completely and use your own system or trying to basically build your own, custom version of STL. That’s what EASTL or RDESTL do. This means it’s relatively painless to convert between STL/your library. The problem is, STL interface is not flawless either. The whole allocator model is quite weird, people have been proposing alternatives to iterators, etc.

When experimenting with RDESTL I was mostly concerned with performance and one of the things that’s frustrating is that in some areas I am limited by the way STL has been designed. Consider map/hash_map insert method. Signature looks like this:

typedef pair value_type;
pair insert(const value_type& x);

Now, imagine having a hash_map with key that’s expensive to copy. std::string is good example, because people like to use it in all kinds of performance comparisons… You probably do not want to do this in real application, and definitelly not in game, but hey, it’s supposed to be a library for everyone, right? Now, let’s see what happens if we want to insert a new element:

mymap.insert(std::make_pair(mystring, myvalue));

Looks innocent enough. Problem is, it’ll copy the string at least twice! First, when creating temporary object of value_type, then again when copying it to map node. One copy could be easily avoided if only insert signature looked like:

pair insert(const Key& key, const T& value);
...
mymap.insert(mystring, myvalue);

Now, STL being so universal library, there’s usually rationale behind design decisions, I’m guessing there’s one here too, but I’m not seeing it. I’m not even trying to say STL should change, rather that if you want to really benefit from writing your own version, it’s sometimes worth deviating a little bit more and not sticking to standard interfaces.

Old comments

wiewior 2011-07-25 05:55:21

Correct me if I’m wrong, but didn’t C++0x solved this particular issue? Aside from insert() You spoke of there is:
template pair insert(P&& x);
With r-value references and move semantics You won’t get at least second copy( from temp to node).
As a sidenote I’d love if iterators would go away ( ranges looks more awesome!)

terrymah 2011-07-25 06:06:34

mymap[mystring] = myvalue;

zsol 2011-07-25 06:16:12

I would say (this is just my best guess) that insert’s interface is like that because map’s iterators dereference to a pair. If you want to support standard algorithms like copy, you have to have an insert that takes the return value of dereferencing the container’s own iterator.
I think it’s worth to note that in this particular case, “sane” std::string implementations use COW, so it’s not that huge of an overhead (but I see your general point).
With all that said, I don’t have a clue why they didn’t include an insert(const Key&, const Value&).

sellibitze 2011-07-25 07:33:08

C++11 containers will provide “emplace” functions which exploit move semantics and perfect forwarding.

petke 2011-07-25 11:39:50

Your consern about the performance of your example is a bit naive. I know of no C++98 compiler that fails to optimize away the second copy. The make_pair function will simply be inlined into the map::insert function. No temporary pair will be made. Returning an expensive to copy object by value costs nothing. I suggest reading up on return value optimization. With C++0x and move constructors the few cases where unnesseary copies where still made have now been taken care of.
As for your advice that companies should make their own STL implementations, because different compilers STL implementations have different implementations. Why bother, instead of choosing one and sticking with it. There are man-decades of expert work in any good STL implementation. You would crazy to throw that away, and you would be naive thinking you could do better.

ed 2011-07-25 14:44:32

insert(const Key&, const Value&) makes more sense than insert( PAIR ). Method taking pair as an argument is unintuitive.
.NET collections use insert(const Key&, const Value&) semantic.
terrymah: i have no idea about STL standard, but in .NET, difference between map[string] = value and insert( string, value ) is that second method with throws an exception if there’s already an element with that key. And I guess, this can be usefull sometimes.

victor bogado 2011-07-25 15:03:12

zsol COW on strings are forbidden on the c++11 standard. The wording on the standard says that str.data() should point to an allocated copy of the source.
This choice has been made to make the string object performance good on multi-trheaded environments, a lock on every copy is more expensive that most string copy. This might not be true for everybody, but at least the standard body thought so.

admin 2011-07-25 23:58:15

@petke - you seem to be making an awful lot of assumptions. Compiler I’m typically using for tests is MSVC 2008. Feel free to do the same, examine generated code and you might be in for a big surprise. As for building ‘own’ STL… If you really need exact copy, than yeah, it might be an overkill. For games, we have the advantage of not having to be so universal. See EASTL document for more detailed info.
@terrymah - yeah, but again – it all depends on how operator[] is implemented. For MSVC, it checks if element is there, if not - it constructs a pair and calls insert(same with STLPort)

admin 2011-07-26 01:16:21

Re C++0x - yeah, move semantics will help a fair bit here and is a step in good direction. Not sure how soon we can expect it (if at all) on consoles.

sirius 2011-07-26 12:52:26

@ed
I wonder if locks are necessary. Why they don’t use interlocked/atomic functions on string’s refcounter…