Replacing The STL

There is often a lot of debate amongst game developers about whether we should be using STL in development code or whether it can, in the long run, cause more problems than it solves. Unfortunately, ignoring the STL and dismissing it as a complicated and bloated set of containers can lead to development teams missing out on a lot of fantastic features and a lot of time saving classes that end up being written from scratch, debugged and tested every time a new member wants a container to work ‘just a little bit differently’.

The reasons for these worries are well documented and without doubt well founded. A lot of them were explained in a paper written by Paul Pedriana of EA, where he described their implementation of STL called EASTL (which I hope is read by all members of the C++ Standards Committee before the final release of the C++09 Standards Document). What was interesting about the EASTL document was that at the time I was in the middle of writing a set of internal containers based on the STL specification for many of the same reasons he stated.

While our current internal implementation (currently called the Framework Template Library or the FTL) in no way covers as much ground as the EASTL, it is slowly making ground with the most commonly used containers developed (and various other elements) while being widely used on some of our projects. Over the next few weeks, this Blog will focus on the various design decisions I made while developing an STL replacement for Blitz, while still keeping it as tight to the STL (and TR1) specification as possible.

To start off, I want to list a few of the decisions that led me to develop our own STL style implementation before going onto the differences that out implementation has compared to the majority of implementations out there.

Platform Support
Without doubt the main reason for developing an internal STL implementation was platform support. Blitz currently supports 9 (at the last count) platforms with our internal tool chain. To keep up with development needs, new platforms have to be investigated and preliminary development started as soon as the tools become available. Initially these new platforms might not support even templates, let alone have a fully featured and stable STL implementation. Having our own internal implementation at least gives us some protection against this.

One of the most vocal opponents to the internal implementation voiced a valid argument – “If you are developing your own implementation, why limit yourself to a fixed interface”. My counter argument was simple and one I stick with today. The STL is widely used by both game developers and other industry programmers, so why not use something that a new developer to the company will instantly feel comfortable with. Also, with the fantastic amount of tutorials out there on STL, if we stick with the STL specification people will be able to the find the answers they need without additional documentation which I would inevitable have to write.

Memory Allocation
I have yet to talk to someone who has enjoyed writing an STL Allocator replacement. It is quite obvious that allocators were tagged onto the end of the specification when it was realised that not everyone would want the default memory model. Since Blitz has an extensive collection of memory allocation and debugging tools, we needed containers that took advantage of this while making it easy for developers to alter them slightly without having to spend a few days figuring out some of the nuances of Allocators.

Have you seen some of the STL implementations? Some of the code could make even the most hardened C++ developer weep, let alone allow us mere mortals to understand what is going on under the hood. You might say that you don’t need to know what’s happening when you push_back a vector element, but I am always wary of tools that do things I don’t fully understand (you could say that’s my problem, but then I’m not the only one).

Feature Bloat
STL contains a wide range of container classes, tools and objects that can be used quite easily. Unfortunately, as mentioned a few of them are simply not suited for game development. It becomes even more complicated when what you think is a simple container actually uses another STL class that is wholly inappropriate for game development. By only implementing the classes that are deemed ‘suitable’ this problem can easily be removed.

So for the next few weeks I am going to concentrate on the main differences between the FTL and the STL in both implementation details and content. Hopefully most of them will make sense!

6 thoughts on “Replacing The STL”

  1. “… we needed containers that took advantage of this while making it easy for developers to alter them slightly without having to spend a few days figuring out some of the nuances of Allocators.”

    How am I not supposed to read this as meaning: We wanted a new structure written by ourselves which we understood (obviously), rather than making the effort to understand STL allocators. Too many times I’ve seen developers spent months writing something from scratch just so they could understand it, when one or two difficult weeks mastering what’s available would have done the trick. Or am I mistaking your intent?

  2. The difficulty of using allocators was simply another element that lead me to believe that a custom STL implementation was the way to go. If none of the other factors existed, and it was simply down to wanting to avoid a difficult period of understanding how standard STL allocators worked then I would agree with you.

    Since that wasn’t the case, and since different implementations of STL can have widely differing Allocator models, this was (to me) an obvious decision to take.

    We now have a simple (and consistent) allocation model that ties in very nicely with out current memory systems, and allows anyone (not just the STL guru’s) to play around with allocators and get the best out of the systems they are working with.

  3. The EASTL seems not that good to me. e.g. It proposes to improve the value-copy in STL container, however, don’t they know that there is a proposal about rvalue reference and move construct? I think it’s more elegant solution because we can go on using contructor, and value-copy like style as we like.

  4. We wrote our own, too. In hindsight, this was a mistake.

    The array wasn’t too bad, but the balanced binary tree was bug-ridden and slowed the project down months after its inception. Performance of the STL was superior as well.

  5. hayate, keep in mind that the EASTL implementation has been around for a while. Most of the implementation (and likely this paper) was written long before the rvalue reference proposal.

    EA also needs similar performance characteristics on compilers for several platforms (PC, 360, PS3, PS2, Xbox, etc). Even when the rvalue optimization comes along, it may not be supported for all of EAs current platforms within an acceptable timeframe (ie yesterday 🙂 )

  6. “…when what you think is a simple container actually uses another STL class that is wholly inappropriate for game development. By only implementing the classes that are deemed ’suitable’ this problem can easily be removed.”

    If you don’t know what you are doing, you shouldn’t blame the tools you are misusing; it makes as much sense as using nails because you don’t want to buy a screwdriver.

    Moreover, what makes data structures and algorithms ‘wholly inappropriate for game development’ or ‘suitable’? How can you tell before having an actual need? The STL provides some general purpose data structures, while this design attitude is likely to constrain you with overspecialized solutions.

Leave a Reply to Lee Winder Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s