Sign in to follow this  

How much is STL used in game programming?

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

Since games have to be optimized as fast as they can be, I was wondering if STL structures work at the required speed, or do experienced programmers use their own lists, hash tables etc? I'm only at the planning phase of my game, and I need to decide whether I should use char* or string, my own list or STL's etc. What do you recomment? Btw. is there a circular list in STL where I can just go to the next item forever, or do I have to simulate it with the regular list, like if (item == list.end()) item = list.begin(); ?

Share this post


Link to post
Share on other sites
I can't tell you for sure how much stl is used in commercial games. I can tell you that id rolled their own container classes for Doom 3.

FWIT, though, my advice is to use stl where applicable. In most cases, it's highly unlikely that it will become a bottleneck.

It's often said that any experienced programmer should be able to write a linked list, array, stack, binary tree, or whatever. But the fact remains that there are a lot of subtleties to implementing these basic data structures efficiently and robustly. Not to mention that programming and testing such a library yourself could take tens (or even hundreds) of hours.

The stl was designed for efficiency and is extremely robust due to its prevalent use. (There's an article in GPG 1 that addresses some of the issues with using stl in games that might interest you.)

One last thing. If your goal is to be a professional (non-game) programmer or software developer, writing these classes yourself would probably be a good exercise. But if your goal is to complete a game successfully, using the stl will save you countless hours and many debugging headaches.

All IMHO.

Share this post


Link to post
Share on other sites
If you want the best(fastest and smallest), definately go with custom structures. Use of custom structures slightly decreases reusability because it adds another dependancy. It also slightly decreases readability to other programmers because they have to learn your library. However, this shouldn't be a big deal if you use standard sort of names like push_back, remove, etc. The main disadvantage of using your own structures is of course the time it takes to write them and debug them. In my project, I felt that the gain of writing my own justified the cost, but you may not. Weigh these advantages and disadvantages and see what's best for you.

Share this post


Link to post
Share on other sites
I should also add that should you choose to use stl, there are steps you can take to maximize its efficiency (such as choosing the most appropriate data structures, reserving memory in advance, supplying a custom allocator, using appropriate stl algorithms, etc.). Developing a good understanding of the stl will help you to use it in the most efficient way possible.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Melekor
If you want the best(fastest and smallest), definately go with custom structures.


You kidding, right?

Quote:
Original post by Melekor
Use of custom structures slightly decreases reusability because it adds another dependancy. It also slightly decreases readability to other programmers because they have to learn your library.


This alone is the killer of writing your own stuff

Quote:
Original post by Melekor
However, this shouldn't be a big deal if you use standard sort of names like push_back, remove, etc. The main disadvantage of using your own structures is of course the time it takes to write them and debug them. In my project, I felt that the gain of writing my own justified the cost, but you may not. Weigh these advantages and disadvantages and see what's best for you.


I highly doubted that you could write better then stl containers.

Share this post


Link to post
Share on other sites
Quote:
Original post by gcsaba2
Since games have to be optimized as fast as they can be, I was wondering if STL structures work at the required speed, or do experienced programmers use their own lists, hash tables etc?


So long as you know how to use them you'll do fine.

Quote:
I'm only at the planning phase of my game, and I need to decide whether I should use char* or string, my own list or STL's etc. What do you recomment?


Go with the STL. If at some later point you realize it's a bottleneck, you can always swap it with your own implementation.

Quote:
Btw. is there a circular list in STL where I can just go to the next item forever, or do I have to simulate it with the regular list, like if (item == list.end()) item = list.begin(); ?


There isn't. But writing an iterator adaptor to do it shouldn't be too difficult (and it'd work with any container).

Share this post


Link to post
Share on other sites
Ouch, I got critisized by an AP :(
If you're too afraid to show yourself, then STFU.

I'm not sure what you mean by "better" but if you mean more optmized, then yes, I *can* write them, easily. STL uses the right algorithms, but the implementation isn't exactly optimized for speed in case you haven't noticed.

Share this post


Link to post
Share on other sites
Quote:
Original post by Melekor
the implementation isn't exactly optimized for speed in case you haven't noticed.


Which specific implementation are you talking about?
Can you give more details as to where exactly the performance bottlenecks are and what can be done to improve the library?

We all stand to learn something from anything you might tell us, so please do speak up.

Share this post


Link to post
Share on other sites
Quote:
Original post by Melekor
but the implementation isn't exactly optimized for speed in case you haven't noticed.


On modern & good implementations of STL algorithms, techniques such as type traits are used that detect the type at compile-time then do a dispatch on type (at compile-time) to the most optimized method to perform the operation depending on the type, for example std::copy when used with POD-types can select to use memcpy at compile time this all inlined out too usually done on nearly all modern vendors.

@ALL:

In general STL containers aswell as algorithms are implementated with alot of very advance C++ techniques & optimizations some of which are described in the book "Modern C++ Design: Generic Programming and Design Patterns Applied" some of which are not described there e.g. EBO, EDO, EMO etc.

If a compiler vendor implements the standard c++ library them-selfs they already know about all of these, they know or should know the C++ standard like the back of there hand and they certainly know there own compiler operates inside-out so they can take advantage of that.

So i have to ask how in the hell are going to compete with that? (answer is very diffcult if the implementation is rock solid) if your concerned with compiler's implementation look into the headers, if you find problems or see something not wright report to them they should sort it out.

Don't forget you can customise STL to certain degree so your not completely restricted, you can provide custom allocator types to STL containers, your allowed to do template specializations for your own types etc.

[Edited by - snk_kid on February 10, 2005 7:21:00 PM]

Share this post


Link to post
Share on other sites
On second thought, maybe I should have posted anonymously too; Looks like anyone who ever says anything negative about STL gets bashed + rated down.

STL is about making life easier for the programmer. It's higher level, more abstract and generic. It's great because it's standard and it saves you a lot of work reinveting the wheel. I'm not disputing those things. What I am saying is that if you want the *fastest* data structures, you get them by tailoring them specifically to their use and working at a lower level of abstraction. I don't think you can really argue with this, it's quite a general concept in computer programming.

Share this post


Link to post
Share on other sites
really depends on the complexity of your game, SDL means less coding and the speed is a little slower but usally not a big deal, howerver when you get into serius sprite magment you hit a point where you really need something more customized to your needs

Share this post


Link to post
Share on other sites
Quote:
Original post by Melekor
On second thought, maybe I should have posted anonymously too; Looks like anyone who ever says anything negative about STL gets bashed + rated down.


I'm not bashing anybody - I'm genuinely interested in any actual insight you are willing to share with us.

Quote:
What I am saying is that if you want the *fastest* data structures, you get them by tailoring them specifically to their use and working at a lower level of abstraction.


What data structures do you have in mind. I'll happily grant you that things like winged-edge data structures have nothing to do in a library of generic data structures. Yet, even in a game, things like that do not make up the bulk of your code.
So it ain't really a STL vs. custom data structures dichotomy - rather, which custom data structures commonly show up in game programming that aren't already provided by the STL.

By all means, do share your experience, instead of being so negative.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
I can't tell you for sure how much stl is used in commercial games. I can tell you that id rolled their own container classes for Doom 3.


Theres probably a good reason for that and probably related to compiler tech around at the time of writing the code (i'm 99% sure it was started when VC6 was about) and less todo with the performance issues.

Ofcourse, I could be wrong, they might well have benchmarked things and in their case found the STL to be too heavy.

Share this post


Link to post
Share on other sites
I'm not the authority on the matter, but if it means anything, i've never had a time where i regretted using STL.

If you are not sure of the speed of STL, i dare anyone to do this: make your own container and make the equivilent STL container, add 100,000 elements, and race 'em.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
By all means, do share your experience, instead of being so negative.


For example, some code I've been working with uses a lot of list operations. Because my list is not so generic(it doesn't have to work with every data type) I required that it can only use classes with a prev and next member, which lets nodes remove themselves instead of having to search the whole list before removal(like std::list does). If I was being negative, I appologize, but getting rated down will do that to a person.

Share this post


Link to post
Share on other sites
Quote:
Original post by leiavoia
I'm not the authority on the matter, but if it means anything, i've never had a time where i regretted using STL.

If you are not sure of the speed of STL, i dare anyone to do this: make your own container and make the equivilent STL container, add 100,000 elements, and race 'em.


Agreed! I know that STL is saving me lots for my Audio Library. I know I will have to do something different when it comes time to cross platform it, but maybe I can use STLPort or something.

- Drew

Share this post


Link to post
Share on other sites
Quote:
Original post by Melekor
I required that it can only use classes with a prev and next member, which lets nodes remove themselves instead of having to search the whole list before removal(like std::list does). If I was being negative, I appologize, but getting rated down will do that to a person.

std::list does not require the entire list to be searched in order to remove an element. Removal is guaranteed to be performed in constant time given that you have an iterator to your object.

Share this post


Link to post
Share on other sites
Quote:
Original post by _the_phantom_
Quote:
Original post by jyk
I can't tell you for sure how much stl is used in commercial games. I can tell you that id rolled their own container classes for Doom 3.


Theres probably a good reason for that and probably related to compiler tech around at the time of writing the code (i'm 99% sure it was started when VC6 was about) and less todo with the performance issues.


i have doom 3 sdk 2, the project is in VC++ 7.0, i'm sure it has to do with more of portability than anything else because each implementation of STL will be slightly different on different compiler vendors that can be abit unsettling.

I've looked into ID's container library and in terms of C++ its pretty mediocre and use of templates is very minimal, no separation of de/allocation de/construction that the STL allocator concept do an important thing to do (although they have custom memory managers). Compared to some of the implementations of STL i've seen its nothing.

Quote:
Original post by _the_phantom_
Ofcourse, I could be wrong, they might well have benchmarked things and in their case found the STL to be too heavy.


Maybe i should do some profiling over the weekend and post some results if i'm not bussy [smile].

Share this post


Link to post
Share on other sites
Quote:
Original post by Polymorphic OOP
std::list does not require the entire list to be searched in order to remove an element. Removal is guaranteed to be performed in constant time given that you have an iterator to your object.


Hm, I must have missed something, what function does that? As far as I can see in the Docs there is only one overload of the list::remove function and it takes a const T&, not an iterator.

Share this post


Link to post
Share on other sites
Quote:
Original post by Melekor
For example, some code I've been working with uses a lot of list operations. Because my list is not so generic(it doesn't have to work with every data type) I required that it can only use classes with a prev and next member, which lets nodes remove themselves instead of having to search the whole list before removal(like std::list does).


OK. So the assumption is that an object can only belong to one list at a time. In such a case, my approach would probably be to stick a list iterator in the element instead of rewriting the whole list class itself. But I can see where you're coming from.

Quote:
If I was being negative, I appologize, but getting rated down will do that to a person.


I just don't like it when people "cry XYZ sucks" - which doesn't help us, rather than telling us "doing FOO with BAR will give you better results than a plain XYZ" - which takes longer to type, but actually teaches us something. Aren't those forums intended for us to share experiences?

Share this post


Link to post
Share on other sites
Quote:
Original post by Melekor
Hm, I must have missed something, what function does that? As far as I can see in the Docs there is only one overload of the list::remove function and it takes a const T&, not an iterator.


You are correct. It is list::erase(iterator p) that you want. [grin] That function is provided by all containers (see the Sequence concept)

May I humbly suggest you invest in a real C++ library reference. The SGI docs do not accurately reflect the library as implemented in standard C++.[wink]

Share this post


Link to post
Share on other sites
Just to backup Melekor's point, there can be times when the STL is sub-optimal. An example being Andrei Alexandrescu's Loki library's AssocVector. He provides a replacement for std:map, which is optimized for infrequent inserts and frequent reads - which is the way I usually use a map.

So there are times when the STL performs sub-optimaly. However, I've never found the need for me to write replacement code, as there is usually a well tested bit of code that does what you need already out there. And if there isn't its probably a good sign that the STL implementation is as fast as it can get without becoming excessively application specific.

I do recall there being a whole library of stl-replacements for specific optimizations, but I can't remember the name right now. If anyone knows what I'm talking about, I'd appreciate a link.

Share this post


Link to post
Share on other sites
Ah, thanks for clearing that up about the remove and erase functions. BTW if you reread my posts you will see that I never said STL sucked anywhere. The ONLY negative thing I said was that it's not the fastest(which makes sense since it's designed to be generic, not specific.)

Share this post


Link to post
Share on other sites
Quote:
Original post by aboeing
He provides a replacement for std:map, which is optimized for infrequent inserts and frequent reads - which is the way I usually use a map.


He's also produced yasli::vector, which provides move semantics (for fast return-by-value).

Quote:
I do recall there being a whole library of stl-replacements for specific optimizations, but I can't remember the name right now. If anyone knows what I'm talking about, I'd appreciate a link.


I'm also interested.

Quote:
Original post by Melekor
BTW if you reread my posts you will see that I never said STL sucked anywhere.


Fair enough. It wasn't intended as a personal attack but a general observation. Excuse me if it appeared that way.

Share this post


Link to post
Share on other sites

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