Sign in to follow this  

containers

This topic is 4855 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

In C++ game development, I have heard mixed opinions on STL containers. Some books and authorities recommend using them because they are fast and of high quality. Others I have spoken with still believe that STL containers are a source of bottleneck in game code, and either write their own containers or simply use arrays. Does anyone have any thoughts and/or specific examples to point to that demonstrate either that STL containers are too slow or they work fine? Thanks a bunch.

Share this post


Link to post
Share on other sites
I recommend you use the STL containers as they let you focus on the design of the program instead of having to worry about memory management (to an extent.)

I wouldn’t worry about performance; they have been optimised countless times by professionals after all! Once you have you program finished, go through it with a profiler and see which parts get called frequently and how you can speed those parts up, without affecting the rest of the program.

For example, you will get far fewer headaches using std::string then trying to use char * and the associated strcpy routines. Using these routines you are bound to use the wrong buffer size somewhere and then get all types of undefined behaviour.

In short, go with STL until you can prove it’s slowing your program down.

Share this post


Link to post
Share on other sites
Expanding on what SneftelStoffel said.

The STL gives you a number of different containers and algorithms, with different capability/performance trade-offs. It then up to you to know which one is appropriate to which situation. Newbs who slap linked lists everywhere because it's the only "advanced" data structure they've learned are making the same mistake. If you use a container/algorithm combination that has quadratic running time when there is another one with constant or logarithmic running time, you are the only one to blame, not the library.

They're probably also going to suffer from worse code bloat (if they write a container for each type) or from type unsafety (if they only make containers of void*) than with the (generally) hybrid approach STL implementers use (void* inside, templated interface).

STL containers are otherwise pretty standard: there aren't 500 ways to implement a dynamic array or linked list.
std::vector really is a thin wrapper around a new-allocated array, with two extra pointers, to keep track of the end of the allocated block and the last element actually in use.
std::list is a run-of-the-mill doubly-linked list (some STL implementations also provide slist, a slingly-linked list). A data field, a next and a previous pointer, standard traversal and manipulation functions.
std::deque are, I believe, often implemented as a dynamic array of arrays.
STL associative containers (set, multiset, map, multimap) are generally implemented using red-black trees, another industry standard data structure. Are you confident you can whip up a working (not to mention efficient) implementation yourself?

Now tell me you can implement either of those better? Why don't you just buy a commercial STL implementation, written and tuned by people whose livelihood it is to produce the very best library they can? (e.g. STLPort, Dinkumware, etc)

The only place, in my opinion, where the STL may be found lacking by game developers is in how it manages memory. The standard allocator is geared toward getting decent performance in most cases. If you know your memory allocation patterns in advance, you might do better. But wait! There is no need to throw the whole library away and start from scratch ... just write a custom allocator and plug it in.

Of course, all of that require actually knowing C++ and making the effort to learn how the STL works and has been designed. Do those people you have talked to qualify, or are they just reporting urban legends?

[Edited by - Fruny on August 27, 2004 5:49:18 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
But wait! There is no need to throw the whole library away and start from scratch ... just write a custom allocator and plug it in.


Or use some pre-written custom allocators for instance boost pool allocators ;-)

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
Or use some pre-written custom allocators for instance boost pool allocators ;-)


Sshhh! First you get them to accept the STL. Then you get them to accept Boost. [wink]

Share this post


Link to post
Share on other sites
^^^^He,he...:) I had hard time outpacing stlport. It's really fast, just don't run timing test in debug mode :) To people who want to write their own containers I say, don't worry, you'll have plenty of opportunities to design your own data structures in your programming travels. The only negative about STL is that you will have to know how your stl is implemented because some rules are open for interpretation by stl writers like size() of a list. I think dinkum's it's constant time but sgi/stlport is linear time. Like iterating over each node and counting it which is slow. But yeah, STL is super great and should be used a lot since it's really nice to understand the same syntax across various people's open source projects. You don't have to learn idiosyncracies of other's container code ie. whether you can also push_front or only push_back or vice versa, etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Expanding on what Sneftel said.

Sneftel must have a negetive rating, because I can't see his post. Oh well, he must've knew the anti-hotpants comments wouldn't fly...[grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by Chris Hare
Sneftel must have a negetive rating, because I can't see his post. Oh well, he must've knew the anti-hotpants comments wouldn't fly...[grin]


Sneftel, Stoffel ... sue me.

Share this post


Link to post
Share on other sites
I think it's worth mentioning again (fruny said it implicitly, but slightly hidden) that picking the right container, and storing the right thing in it is very important for performance critical sections, but the STL implementation of the containers is almost never the cause of performance problems.

About the only negative thing I can think of in the STL is that they don't provide a singly linked list, which is a basic data structure that could often be usefull in saving memory on very big lists of things that only need sequential processing. (I need to check if boost has one. - except I don't have anything memory critical to use it on)

I find that I use the std::deque and std::map classes in just about every program I write, and they are amazing. They make working in C#/.NET feel like writing in assembly sometimes (after becoming good at templates and the STL, you are so powerfull that any other langauge feels like the prehistoric ages).

Share this post


Link to post
Share on other sites
Quote:
Original post by Xai
About the only negative thing I can think of in the STL is that they don't provide a singly linked list, which is a basic data structure that could often be usefull in saving memory on very big lists of things that only need sequential processing. (I need to check if boost has one. - except I don't have anything memory critical to use it on)


There is list type implementated with a singly linked-list which is in STL extensions called slist note the fact its an STL extension like hashmap, rope etc these are not part of standard C++ as of yet so your not guaranteed an implementation on all compilers (but then again you could just download a copy it of it from the net).

Share this post


Link to post
Share on other sites
thanks snk_kid ... i probably won't grab it if it's not in either STL Port or Boost ... because I don't have time / energy and ability to verify code myself. But still good to know. I pretty much only use things that are pure standard C++, boost, or STL Port ... plus whatever platform libraries I need to get the job done (aka OpenGL, DirectX, MUSCLE, Torque, Xerces, etc).

Share this post


Link to post
Share on other sites
Quote:
Original post by Xai
thanks snk_kid ... i probably won't grab it if it's not in either STL Port or Boost ... because I don't have time / energy and ability to verify code myself. But still good to know. I pretty much only use things that are pure standard C++, boost, or STL Port ... plus whatever platform libraries I need to get the job done (aka OpenGL, DirectX, MUSCLE, Torque, Xerces, etc).


STLport has the STL extensions.

Share this post


Link to post
Share on other sites

This topic is 4855 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this