Stl in game programming

Active Oldest Votes. Use a profiler to see where you have problems. SigTerm That is true of all programming however leaning STL saves you from writing many algorithms and the much longer time spent in debugging. The main performance trap when using the standard containers is memory allocation. Make sure you understand when the container allocates and frees memory, how to avoid doing it when you don't need to, and how to use custom allocators when you really need fast, dynamic behaviour.

The standard algorithms, as Mark says, should be about as fast as can be, as well as generic and if you're using a popular implementation well tested. Mike Seymour, this is why I probe potential employees on their understanding of implementation of data structures, not just how to use them. You'd be surprised the number of people that don't realize the overhead of a std::map min 3 pointers typically per element, plus possibly duplicate storage of the key, if it's a member of the value.

SigTerm SigTerm This requires maintaining extra state, which costs much more than a few range checking here and there. Matthieu M: std::deque example in 4 10x slowdown happened on release build. Also, I think that there are other sanity checks, not only in iterators, but in [] operators, etc. There are. But from what I've seen iterators are the most costly.

The main issue is that the container should maintain a list of iterators observer pattern and check at each update which are invalidated.

Often times it's a linked list and it takes O N at each update where N is the number of iterators. Add to the fact that a linked list is not known for its cache-friendliness, and you get yourself a major slowdown. It's hardly a surprise that std::deque::iterator::operator- is 10 times slower than a vector's. The latter is typically a mere pointer operation. Timothy Baldridge Timothy Baldridge 10k 1 1 gold badge 39 39 silver badges 74 74 bronze badges.

A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. See the rest of my comment. I'm not saying he shouldn't optimize. I'm saying that in the end, the time spent in STL code is going to be dwarfed by the time spent in the rendering engine, physics code and math libraries. And if he's trying to write any of those from scratch, he's going to have bigger issues anyways.

What do you recomment? Cancel Save. Zakwayda 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. Melekor 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 is a generalized library and so, its components are parameterized. A working knowledge of template classes is a prerequisite for working with STL. STL has four components Algorithms Containers Functions Iterators Algorithms The header algorithm defines a collection of functions especially designed to be used on ranges of elements.

They act on containers and provide means for various operations for the contents of the containers. Skip to content. Change Language. Besides, you're working on a game so, use the tools you have at hand that makes your life easier and your code less prone to bugs. Why bother reinventing the wheel when you can be working on something else like the game's AI, user experience, or better yet; testing and debugging?

STL is absolutely fine for use in games, as long as you understand it well. Our engine makes pretty extensive use of it and it hasn't ever been an issue. The most important thing is to understand what the strengths and weaknesses of each container type are and pick the correct container for the job you are doing. My former employer shifted from using a robust set of custom container classes to STL. Build times went up and ease of debugging went down, both pretty significantly.

If we'd been starting from scratch, STL perhaps better used would likely have made sense, but it was never clear to me that we gained anything in switching to STL that would justify throwing out working, fast, debuggable code.

For my personal projects, whether STL fits or not depends on the project. If I'm trying to do some Mike Acton-style data-driven, memory-and-cache-access optimized work, I'll at least think about rolling my own custom data structures. If I'm prototyping some algorithms or gameplay and don't care about performance, scalability, target platform, etc.

I'll automatically grab STL. My 2 cents on this is that the STL works just fine. I've been developing a 3D game engine not AAA quality, but advanced enough - scripted entity types, deferred renderer, integrated Bullet physics for PC and I have yet to see containers become the main bottleneck. Incorrect 3D API usage and poor algorithms have been the best targets determined by profiling!

Good question! A more specific question is what are some common requirements that a game would have that cannot be met with STL and Boost. In my experience, the tight memory limitations of console hardware make any kind of dynamic sized container a bad idea regardless of how clever your custom allocator is.

Containers that have no deliberate bounds encourage programmers to write code that does not constrain the bounds of their data sets. Depending on countless variables that are difficult to track you may exceed your memory limitations.

I have a hunch that this is one of the primary causes of instability in modern games. Additionally, overuse of templates can lead to very long compile times in a large code base, and will bloat the size of your executable so that it would no longer fit within the cache of, say, an auxiliary core on a ps3.

While general-case solutions are not always ideal, they are often good enough. Your first solution to a problem is almost never ideal, and you improve or replace the inadequacies until it is good enough. As with all technology choices made during development, you need to weigh up the pros and cons -- will rolling my own library give me more beneficial memory usage, performance, and productivity than simply using the STL?

Possibly; though it's just as easy to create a vector implementation that uses more memory, is slower, and requires large amounts of maintenance to remain function compared to what already exists. People should not avoid using the STL in their games because other people avoid using the STL in games; they should avoid using it if they've weighed up all of their options and they genuinely believe that another implementation will improve the quality of their product.

As with most questions the answer is never "yea or nay", black or white. STL is a good fit for some problems, using it for those problems should be fine.

It's a mistake to assume it's useless, yet it's also a mistake to assume that it is appropriate to use in every situation. The biggest issue to watch out for when using STL in game development is memory allocation. STL's default allocators don't seem to fit well into preferred allocation strategies for game development.

Of course custom allocators can be used, but this makes the whole idea less appealing if you're considering whether to add STL to a non-STL codebase.

Add to this that if your codebase is non-STL, you may not have anyone familiar enough with STL or template concepts to implement the custom allocators correctly. Anyone whose home-grown solution would fall into category 3 surely knows the answer to the original question for their particular problem.

The STL falls into category 2. So for someone who needs to ask the question, "should I use the STL", the answer is probably yes. STL is all right for use on a PC, because its advanced virtual memory system renders the need for careful memory allocation a bit less crucial although one must still be very careful.

I think this question is really a larger unasked question -- should I use X in my Y? And the only way to really answer that is to try it for yourself.

For every person you find that says that X works great, you'll find someone who says it's horrible. And both of them are right -- for their project. The great thing about software, unlike most other disciplines, is that you can always change things later on if you find it's not working the way you would like it. You find out later that STL isn't working for you in this project? Rip it out, put something else in it's place. Don't like how you divided the duties among your objects?

Don't like that you used objects? Replace them with straight C methods. Don't like everything being stored in structs and methods to manipulate them? I hold iteration count to be of the highest importance, so I just stay away from the STL, and any other development technique that slows down iterations like architecting for the sake of it, or script languages that need to be compiled.

Costly iterations lead to huge development teams of people trying to get stuff done with very little actually happening. I've seen it and heard it, and one of the culprits seems to be compile times for template libraries. Sign up to join this community. The best answers are voted up and rise to the top. Stack Overflow for Teams — Collaborate and share knowledge with a private group.

Create a free Team What is Teams? Learn more. STL for games, yea or nay? Asked 11 years, 6 months ago. Active 4 years, 1 month ago. Viewed 46k times. Improve this question.