STL Optimization Techniques

GDC 2001 Roundtable Report

  Pete Isensee

Introduction

In March 2001, I presented a roundtable at the Game Developer's Conference in San Jose. The roundtable was held an hour a day for each of the three days of the conference. The roundtable generated excellent and thought-provoking conversation among game developers using or considering the STL. Discussion centered on the best ways to get good STL performance and improve performance. We talked about common STL mistakes and how to avoid them. We also discussed various STL implementations, debugging issues, custom containers and allocators, as well as libraries similar to STL.

83 total people attended the roundtable. 79 of those attendees were software developers. Of the 79 developers, 74 had written STL code, and over 40% had used STL in shipped games, with an estimate of 50+ titles represented. Two-thirds of the developers reported using STL for games in progress.

PCs represented the platform of choice for most of the developers, with over 80% reporting developing for PCs and 20% for consoles. A single attendee reported using STL for a handheld device (GameBoy Advanced).

The STL implementation most widely used was Dinkumware, the implementation that ships with Microsoft Visual Studio, used by 3 out of 4 developers. 15% use STLport, a highly cross-platform implementation based on the SGI implementation. The SGI implementation is used by 6%.

Three-fourths of the developers use the Visual C++ 6.0 compiler. 13% use GCC, 9% use Metrowerks, and a handful of developers use other compilers.

In the course of the three days, we generated the following list of STL optimization techniques and resources. Each of these techniques merits much more detail than a single line, but that work is left to a future article.

General

  • Use the appropriate container for the task
  • Wrap the STL so that functions can be customized
  • Wrap the STL with your own debugging layer
  • Don't return containers by value
  • Avoid STL in time-critical areas (controversial)
  • Use STL to build containers when number of objects is unknown; use static array or buffer when number is known
  • Use partial specialization (void*) to avoid code bloat
  • Evaluate different STL implementations (see list below)
  • Use the latest version of your STL implementation
  • Use function objects (functors) instead of callbacks
  • Compilation Speed

  • Use pre-compiled headers
  • Evaluate and customize the compiler method you use for pre-compiled headers; the Visual C++ default method is not necessarily the fastest
  • Use external header guards (see Lakos section 2.5)
  • Containers

  • Understand the O(x) guarantees of each container
  • Store the appropriate data structure in the container
  • Store pointers to objects rather than the objects themselves
  • Store "smart" pointers (see Boost libraries)
  • Don't store auto_ptrs<> (not allowed by Standard C++, but some implementations incorrectly allow this)
  • Hand optimize the red-black tree implementation of STL map/set
  • Write/use custom stack-based container using vector semantics around an array (see Stroustrup section 17.5.4)
  • Write/use custom vector-style container
  • Write/use custom container that doesn't call individual object destructors
  • Write/use custom allocators (e.g. memory pool allocators with no delete time overhead)
  • Consider using vector instead of list for better cache coherency
  • Remove and insert elements at the end of the container
  • Don't remove/insert elements in the middle of the container
  • OK to treat vector as contiguous memory array as long as it's non-empty; T* p = &vec[0];
  • Use vector.reserve()
  • Be aware of vector.capacity() vs. vector.size()
  • Use std::vector<T>( c ).swap( c ) to shrink vector to fit (see Guru of the Week tip 54)
  • Use std::vector<T>().swap( c ) to free vector memory (see Guru of the Week tip 54)
  • Use map::insert instead of map::operator[]
  • Vector[i] is faster than vector::at(i) because no error checking
  • For small numbers of objects, vector in combination with sort can be faster than map
  • Non-standard hash containers can be faster than standard map containers
  • Non-standard singly-linked list container can be faster and more space efficient than standard list container
  • Use vector<bool> or bitset<N> for compact bit list storage
  • Be aware of the limitations of vector<bool> (see Guru of the Week tip 50)
  • Pass containers by reference
  • Objects

  • Use inheritance method to avoid space used by empty objects (see Empty Member Optimization)
  • Optimize contained object copy constructors (reference counting, smart pointers)
  • Optimize contained object destructors
  • Hand optimize string implementation so that string reference count is stored in string-allocated memory instead of in string object
  • Iterators

  • Use pre-increment instead of post-increment when using STL iterators
  • Use iterators instead of [] operator access for speed
  • Hoist c.end() out of for() loops when container end doesn't change
  • Cache the iterator dereference in loops
  • Understand the rules of iterator invalidation
  • Pass iterators by value
  • Algorithms

  • Be aware of what algorithms are available so you don't recreate work that's already been done
  • Use std::swap() or container.swap() to swap objects and/or containers
  • Use template specialization to optimize algorithms for common objects, e.g. std::copy( char*, char* )
  • STL Implementations

  • Dinkumware STL library
  • SGI STL library
  • STLport STL library
  • Roguewave STL library
  • STL-compatible Libraries

  • Boost portable C++ STL-compatible libraries
  • Crypto C++ cryptography library
  • Blitz high speed math C++ library
  • GTL graph template library
  • Regex++ regular expression library
  • Matrix TCL C++ template library
  • VTL View template library
  • Web Resources

  • Guru of the Week C++ tips
  • C++ Users Journal
  • Dr. Dobbs Journal
  • C++0x draft standard (not the final standard, but close -- and free)
  • Articles

  • Interview with Alex Stepanov, creator of the STL
  • The Empty Member Optimization
  • Books and Authors

  • The C++ Standard Template Library, Plauger, et al.
  • The C++ Standard Library, Josuttis
  • Modern C++ Design, Alexandrescu
  • Generic Programming and the STL, Austern
  • Exceptional C++, Sutter
  • STL Tutorial and Reference Guide, 2nd Edition, Musser, et al.
  • The C++ Programming Language, 3rd Edition, Stroustrup
  • Effective C++, Meyers
  • More Effective C++, Meyers
  • Effective STL, Meyers
  • The C++ International Standard, ISO/IEC 14882
  • Large Scale C++ Software Design, Lakos
  • C++ Gems, Lippman
  • More C++ Gems, Martin
  • Last update Jan 2009

    © 2009 Pete & Kristi Isensee. All Rights Reserved