« Fake Interactivity | Main | More On Allocation »

August 19, 2006



I'd be curious to hear your pro-STL thoughts. I hate it because like anything that opacifies underlying data structures, it's murder on the PS2 cache and lends to spurious copying. But I do respect that STL lets you preallocate, and so between that and a fixed block allocator, anyone blaming fragmentation on STL just means they're not planning ahead and giving the STL-centric developers around them the tools the STL heads need in order to focus on coding.


I've shipped PS2 titles that extensively use STL. Like any set of data structures, you need to use them wisely.

Currently we're using a licensed engine that comes with a set of built-in containers. In practice, they are bug-prone, have *worse* allocator behavior than STL, bad cache coherency, and tend to lead to people writing bad algorithms.

Yet somehow, the other developers in the company accept these shoddy containers just fine, but you mention "STL" around them and they go into histrionics. I really think a lot of it is just religion at this point.


That should have read "some other developers." I didn't want to imply that everyone has those views.

In addition, there are varying qualities of STL implementations out there. Some of them, particularly in the console space, seem much worse than others.


I think "needs to be used wisely" is true of pretty much _any_ non-trivial technique. I'm of the opinion that anything that can't be justified as absolutely necessary is better off re-written as simpler (and hopefully cleaner). I've seen too many virtual-for-the-sake-of-it or massive-inheritance-trees.

I was stuck at a company for a long while that refused to use STL or dynamic allocation, and I can see why. We did a lot of Lua usage, in amongst large chunky dynamic allocations; and in a fixed memory environment where you're using it to its limits thats not acceptable. Now I'm clear of there, I'm shifting to an approach where dynamic allocation is fine, but all allocations have to be grouped into heaps with other similar usage items.

So level data goes to one place, transitory allocations go to another, and so on. The key thing is, there's no such thing as 'allocate into the main heap' - every allocation has to be put somewhere, and that forces developers to think about where things belong. And it means that if fragmentation does come up in one heap, we have a much reduced set of allocations to look at and identify the fragmentation.

Almost always, its going to be someone putting in a small, long term allocation in between two big short term allocations, meaning that the heap fragments in a major way. In that case, you can just log out the allocation frequency, and figure out which allocation to shift into another (or its own) heap.


heh, certainly not trying to start a flame war ... but what's your opinion on the managed code that Microsoft is introducing on the xbox360. I know they're starting relatively small with the indie developers in mind and XBLA, but I can only imagine that they'll open it up for full on commercial games at some point.

Do you think that the managed development will eventually outstrip this kind of development in whole or in part at some point?

I for one rather like the fact that I can for the most part avoid headaches such as this. Of course, that's not to say that you don't have to worry about memory at all, you still have to code with the garbage collector in mind ... but all in all, still a much easier process than having to worry about fragmentation and stuff ;-)


and just to anticipate some of the replies, I know that traditional c++ isn't going anywhere. Considering the fact that most platforms aside from windows and 360 won't support it, and it truly is the only way to get the fastest performance out of your code, it's clear to see that it will be around for a long while.

The main thing I was getting at with my question is, do you see some potential uptake where a studio might consider using it to have a smaller team, faster development cycle, less bugs due to memory issues, etc. etc. The way I look at it is that no, you likely won't be able to write the latest and greatest HDR enabled super graphics game. However, if you're forced to scale back on that front, maybe you can spend more time on the fun aspects of your game.

wow, I hope that doesn't sound like marketing fud ... I'm just a little indie guy who reads your blog and wanted to get your thoughts :-)


Vince: The reason we're not complaining about flakey data structures with the new engine is that we now have bigger things to worry about. :)


I worked on teams that used extensive dynamic allocation and didn't worry about memory. The team I'm on right now preplanned memory sections, used static allocation blocks (i.e. fixed block heaps) and is very aggressive about fitting within target memory and providing an overflow safety net just in case. I've seen the actual benefit of early, aggressive, and continuous monitoring of resource usage. By getting the memory issues out of the way early, we're spending a lot more time on polish at then end of the game now than dealing with all the memory issues instead.

Mike Enright

I used Borland's alternative to STL in DOS in 1994. I pretty much stuck with templates and the whole C++ thing until 1999 when I started working on under-powered embedded processors in set-top boxes (game consoles without the graphics). The memory allocation technique we used there was specifically designed for a low amortized time in the allocation function. But we built up and debugged our own template libraries for the situation.

The best stuff to read on allocation on multiprocessors is anything you can find on implementations of JVMs. Or read about lock-free queue implementations.

Hector Yee

I had problems with the malloc on gcc before while working on Shrek 2. The process would hang for like 3 hours on free(). Inside the free routine was something like if count == 63356 then garbe_collect(). So we switched to ptmalloc and the same process ran in seconds.

Its almost like the whole Java vs C memory management issue. Java has generational garbage collectors and in C we still have to manage it outselves.


Sounds like you were smashing your heap data structures. That doesn't sound right even with the most pathological behavior.


(Noone cares but) I agree, memory allocation and STL are best avoided. STL is a mixed bag of things some useful some not as much in different situtations. The template syntax for hooking in a custom allocator to use with STL is for sure mind boggling. Memory wise i'd say: (fixed memory mapped -> fixed -> stack -> fixed pool -> something more complex) would be my order of consideration. I'd really think twice before using anything more complex than stack since it's really nice for multithreaded apps - you don't have to worry about locking any globals, the hardware conveniently saves the stack pointer for you. Btw Jamie fixed pool is a shorthand for "fixed size pool", those only work for fixed sized objects. That doesn't work very well for entities unless you use a composition based approach (vs traditional hierarchy). I wonder how soon will mainstream programmers begin to realize that inheritance is bad? Oh wait that sounds like heresy :)

Hector Yee

Re: pathological. It was a hash data structure with variable sized data members. GCC's old allocator loved it when you allocated and released data in a consistent manner. But if you released data in a random manner (say in order of hash key which distributes the data pseudo randomly in your list or vector) it would perform poorly.

You can reproduce it by allocating blocks of random size in a for loop and release it in a for loop and time it. Then repeat the same experiment with the release order randomized.

Microsoft's malloc seems to handle it better than gcc 2.3.1.

Bryan McNett

"STL bad" is a gross oversimplification. Of course, the STL's heap-walking container classes are no good for videogames, but they are just one tiny part of the STL. Those who ignore the rest of the STL are doomed to reinvent it, poorly.

Here is just one tiny example: STL's nth_element will sort a range just enough such that only the nth element is guaranteed to be in the right place. On average this works in O(N), or linear time.

It is possible to find the 38th largest integer in an array of integers, in linear time, just by typing this:

int foo[100];
nth_element( foo, foo+38, foo+100 );

nth_element is just one in a great variety of optimally efficient, useful code in the STL. Forbidding STL in a game project because its containers are slow is an unfortunate mistake.


Enjoyable discussion! Long ago I worked at Rogue Wave working on their high-performance product line. There were some gaming customers that found 2 RW products useful:

*NewCode MTS -- an extremely high-performance malloc/free() replacement that RW exclusively licensed up to when RW was bought out by Quovadx and the rights were terminated. MTS is still available directly through NewCode... if you want the fastest malloc/free() implementation (without fragmentation or scalability concerns, then I encourage you to check them out.) http://www.newcodeinc.com

* The RW STL -- getting faster with every release and it was just donated earlier in the year to the Apache group (pretty flexible licensing terms.) Check it out:

I don't work for RW any longer, but I have friends at both RW and Newcode -- just trying to pass on information when it may be useful.

The comments to this entry are closed.

Jamie's Bragging Rights

  • Spider-Man 2
    The best superhero games of all time Game Informer
    Top five games of all time Yahtzee Croshaw
    Top five superhero games of all time MSNBC
    Top 100 PS2 games of all time Official Playstation 2 Magazine
    1001 Games You Must Play Before You Die Nomination for Excellence in Gameplay Engineering Academy of Interactive Arts & Sciences
  • Schizoid
    Penny Arcade PAX 10 Award
    Nominated for XBLA Best Original Game
    Nominated for XBLA Best Co-Op Game