Jump to content
  • Advertisement
Sign in to follow this  
CDProp

Are STL containers often too slow for professional game development?

This topic is 3452 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

...or is that just a myth? Back when I had a game programming job, we used a custom templated List class instead of using STL lists or vectors, because programmers there who were far senior to me wanted to avoid STL. I was just curious as to why that might be, because as far as I understand it, STL containers maintain memory pools to make sure that the data is in contiguous memory. So I'm curious as to what other optimizations they might have been making for the sake of speed. I know that programmers had to explicitly tell the list to re-size...if there was no more room in the list, the Add() function would return a NULL, and the programmer could check for that and resize if they wanted, instead of Add() handling it automatically. Maybe that was enough of a reason? I dunno. Or maybe they just felt more comfortable using a list class that they designed, understanding intimately the inner-workings of it. Our engine was cross-platform, and even though STL is fairly portable, maybe they just wanted to make sure that all platforms had the same implementation, internally. I dunno. I mean I know you can't read their minds or anything, but I am curious as to what your thoughts are. My game right now is tiny, running at 200fps, so the STL containers are working just fine for me. : )

Share this post


Link to post
Share on other sites
Advertisement
Definitely not slow, and definitely faster than the versions most programmers can write by themselves.

Note: If used correctly.

Share this post


Link to post
Share on other sites
Quote:
Original post by CDProp

I know that programmers had to explicitly tell the list to re-size...if there was no more room in the list, the Add() function would return a NULL, and the programmer could check for that and resize if they wanted, instead of Add() handling it automatically. Maybe that was enough of a reason? I dunno.


If using custom allocator, the proper way to signal such condition would be throwing std::bad_alloc. But this would be closer to abuse of exceptions:
std::vector<int, special_allocator> my_v;
try {
v.add(x);
} catch (std::bad_alloc) {
v.get_allocator().allocate_some_more();
v.add(x);
}
But this is ugly, since STL is designed to abstract away allocations, so it simply does that internally and automatically, so bad_alloc should get thrown only rarely.

Unfortunately, this makes std::vector suboptimal for certain types of tasks. Alternative would be to provide alternate interface to above functionality:
template < class T, class A > bool push_back(vector<T,A> & v, T & x) {
if (v.size() < v.capacity()) {
v.push_back(x);
return true;
} else {
return false;
}
};
...
if (!push_back(v, x)) {
v.get_allocator().allocate_some_more();
if (push_back(x)) {
// seems we're out of memory
}
}
Of course, we now end up with what vector already does, so unless the out of memory condition really requires some complex handling, then default implementation would do the just just fine.

Such patterns are idiomatic when avoiding use of exceptions, but they can result in somewhat simpler generated code, while source is somewhat more complex.

Quote:
Our engine was cross-platform, and even though STL is fairly portable, maybe they just wanted to make sure that all platforms had the same implementation, internally.


That is a valid reason. There are quite some differences in implementation. MVS's checked iterators can be a cause of problems, MVS's string uses internal (16 byte IIRC) buffer in every string, so that can cause different allocation patterns. Hash map is a mess since it resides in different namespaces.

Quote:
My game right now is tiny, running at 200fps, so the STL containers are working just fine for me. : )


For vector, element access should be exactly the same as with plain arrays.

Most of the time, bottlenecks occur due to allocations and re-allocations, but those commonly expose problem with algorithm, not so much with STL implementation.

If one needs a list of sorts to which elements are added, then it's reasonable to examine which method is most suitable. Can list be pre-allocated to fixed number of elements, can its storage be pre-allocated in single chunk, does it even need to be allocated or can it be re-used, and similar.

Share this post


Link to post
Share on other sites
This question comes back around every month or so.

The synopsis is that the standard containers were, once upon a time, slow. They have long since been improved and the popular implementations are now about as fast as they're ever likely to get (except the new-coming C++ standard will add move semantics which allows for minor improvements). If one is willing to bend the rules regarding the specification of these components then their efficiency can be improved for games.

Beyond that there is very little room for improvement in building generic containers. Custom made equivalents are more likely to be slower and less thoroughly tested. You can beat the standard containers on performance iff you let aspects of the problem you're trying to solve leak into the design of your custom containers, but only because you're injecting some non-generality into them allowing you to optimise for specific circumstances. Fortunately, this is not necessary most of the time.

Share this post


Link to post
Share on other sites
The STL in itself is very fast, in fact is is very hard to write your own versions which will be faster. Many game studios cook up their own versions of containers for many different reasons.

One big reason is knowing how that container will act. Meaning, knowing when and how basic functions access the data structure. Or knowing, for instance, how large, or when a vector will resize. By making your own container, you know for certain how each container will behave under different conditions.

For console developers there are a few good reasons not to use the STL. Biggest is memory issues; the console only has a fixed amount of memory. STL containers could easily grow in size or fragment memory. As mentioned before, it is not always wise to resize a vector by doubling the size or something similar. Instead, it is a better use of memory to only add enough space for eight or 16 new items at a time.

Another important thing for consoles to watch for is cache coherency. Node based data structures (list, map, etc. ) can easily have to load in new data every step. Instead you can cook up a version of these containers which hold everything in contiguous memory, but acts like a node based structure, this way there is a better chance of the node already being loaded into memory.

Lastly, there may be feature that you wish to add or remove from the STL. For instance, it is usually undesirable for a map to create a new element when one does not exist using operator[]. Or you may wish for push_back() to return a reference to the newly inserted element. These are small things that can prevent bugs and make development go much faster.

Share this post


Link to post
Share on other sites
Well. The EAStl document covers a lot of the issues.
One of the reasons we avoid STL at work is the debugger, by default(ie not writing a tonne of scripts for it), can't view the content of most STL containers.

Share this post


Link to post
Share on other sites
Quote:
Original post by CDProp

I know that programmers had to explicitly tell the list to re-size...if there was no more room in the list, the Add() function would return a NULL, and the programmer could check for that and resize if they wanted, instead of Add() handling it automatically.


I'm having trouble seeing the advantage of this. All it really does is set an upper size limit on the vector, which is quite easily done with a push_back wrapper.

Share this post


Link to post
Share on other sites
Quote:
Original post by scjohnno
Quote:
Original post by CDProp

I know that programmers had to explicitly tell the list to re-size...if there was no more room in the list, the Add() function would return a NULL, and the programmer could check for that and resize if they wanted, instead of Add() handling it automatically.


I'm having trouble seeing the advantage of this. All it really does is set an upper size limit on the vector, which is quite easily done with a push_back wrapper.


That's right. Why go through all the trouble of implementing your own containers, making sacrifices in performance (since the people who write implementations of STL usually know very well what they're doing), when you can just make a wrapper? Make an inherited class Vector<> that checks for the capacity and pre-allocates the way you want when adding a new element. You may not be able to override many functions (I'm not sure but I think most of them aren't virtual) but you can certainly add your own.

Share this post


Link to post
Share on other sites
Quote:
Original post by Jotaf
Make an inherited class Vector<> that checks for the capacity and pre-allocates the way you want when adding a new element. You may not be able to override many functions (I'm not sure but I think most of them aren't virtual) but you can certainly add your own.
The standard containers don't have any virtual functions and weren't actually intended to be inherited from (although reasons do exist to do that) or used polymorphically.

I think scjohnno meant, very simply, a push_back wrapper:

template <class T, class A>
bool push_back(std::vector<T, A> & v, const T & item)
{
if (v.size() == v.capacity()) return false;
v.push_back(item);
return true;
}

// example use
if ( !push_back(myvec, x) )
{
myvec.reserve(myvec.capacity() + some_more);
if ( !push_back(myvec, x) )
{
// something has gone terribly wrong :'(
}
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!