STL Alternative

I really hate using STL containers because they make the debug version of my code run really slowly. What do other people use instead of STL that has reasonable performance for debug builds?

I'm a game programmer and this has been a problem on many of the projects I've worked on. It's pretty hard to get 60 fps when you use STL container for everything.

I use MSVC for most of my work.

From stackoverflow Tod

• I'll bet your STL uses a checked implementation for debug. This is probably a good thing, as it will catch iterator overruns and such. If it's that much of a problem for you, there may be a compiler switch to turn it off. Check your docs.

  From Fred Larson

• STL containers should not run "really slowly" in debug or anywhere else. Perhaps you're misusing them. You're not running against something like ElectricFence or Valgrind in debug are you? They slow anything down that does lots of allocations.

  All the containers can use custom allocators, which some people use to improve performance - but I've never needed to use them myself.

  Tod : You've obviously never written a game with STL. The problem isn't the games algorithms, it's the stl overhead. When stl isn't optimized it calls like 100 functions when it would be completely inlined and that overhead kills the game's framerate.

  MarkR : I've written several games with STL, but perhaps not on the same scale as you have; I've not found it to be a problem (but imagine it's possible)
  From MarkR

• If you're using Visual C++, then you should have a look at this:

  http://channel9.msdn.com/shows/Going+Deep/STL-Iterator-Debugging-and-Secure-SCL/

  and the links from that page, which cover the various costs and options of all the debug-mode checking which the MS/Dinkware STL does.

  If you're going to ask such a platform dependent question, it would be a good idea to mention your platform, too...

  From Will Dean

• Check out EASTL.

  Torlack : I don't think EASTL is available to the public. But the document covers a lot of problems with current STL implementations.
  From Mark Ransom

• Ultimate++ has its own set of containers - not sure if you can use them separatelly from the rest of the library: http://www.ultimatepp.org/

  From Nemanja Trifunovic

• If your running visual studios you may want to consider the following:

  #define _SECURE_SCL 0
  #define _HAS_ITERATOR_DEBUGGING 0
  

  That's just for iterators, what type of STL operations are you preforming? You may want to look at optimizing your memory operations; ie, using resize() to insert several elements at once instead of using pop/push to insert elements one at a time.

  From rhinovirus

• What about the ACE library? It's an open-source object-oriented framework for concurrent communication software, but it also has some container classes.

  Bklyn : To paraphrase jwz: if you think "I know, I'll use ACE", now you have two problems (see http://regex.info/blog/2006-09-15/247)
  From koschi

• My experience is that well designed STL code runs slowly in debug builds because the optimizer is turned off. STL containers emit a lot of calls to constructors and operator= which (if they are light weight) gets inlined/removed in release builds.

  Also, Visual C++ 2005 and up has checking enabled for STL in both release and debug builds. It is a huge performance hog for STL-heavy software. It can be disabled by defining _SECURE_SCL=0 for all your compilation units. Please note that having different _SECURE_SCL status in different compilation units will almost certainly lead to disaster.

  You could create a third build configuration with checking turned off and use that to debug with performance. I recommend you to keep a debug configuration with checking on though, since it's very helpful to catch erroneous array indices and stuff like that.

  From rasmusb

• EASTL is a possibility, but still not perfect. Paul Pedriana of Electronic Arts did an investigation of various STL implementations with respect to performance in game applications the summary of which is found here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

  Some of these adjustments to are being reviewed for inclusion in the C++ standard.

  And note, even EASTL doesn't optimize for the non-optimized case. I had an excel file w/ some timing a while back but I think I've lost it, but for access it was something like:

         debug   release
  STL      100        10
  EASTL     10         3
  array[i]   3         1
  

  The most success I've had was rolling my own containers. You can get those down to near array[x] performance.

  paercebal : +1 for the Link.

  paercebal : Well, if I could add another +1, I would. The link http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html is very VERY enlightning.

  Viktor Sehr : Assuming the array is allocated on the heap, range checking is disabled\compiler is set to optimize, I dont belive that an C array has fast access times than a std::vector.
  From Jeff

• For big, performance critical applications, building your own containers specifically tailored to your needs may be worth the time investment.

  I´m talking about real game development here.

  Tod : Yeah, this is actually what I've done for all the games where I didn't inherit the code. And since you control the allocators it's probably the best answer. I'm just hoping to fine something better!
  From Vicent Marti

• Checkout Data Structures and Algorithms with Object-Oriented Design Patterns in C++ By Bruno Preiss http://www.brpreiss.com/

  From Roger Nelson

• MSVC uses a very heavyweight implementation of checked iterators in debug builds, which others have already discussed, so I won't repeat it (but start there)

  One other thing that might be of interest to you is that your "debug build" and "release build" probably involves changing (at least) 4 settings which are only loosely related.

  1. Generating a .pdb file (cl /Zi and link /DEBUG), which allows symbolic debugging. You may want to add /OPT:ref to the linker options; the linker drops unreferenced functions when not making a .pdb file, but with /DEBUG mode it keeps them all (since the debug symbols reference them) unless you add this expicitly.
  2. Using a debug version of the C runtime library (probably MSVCR*D.dll, but it depends on what runtime you're using). This boils down to /MT or /MTd (or something else if not using the dll runtime)
  3. Turning off the compiler optimizations (/Od)
  4. setting the preprocessor #defines DEBUG or NDEBUG

  These can be switched independently. The first costs nothing in runtime performance, though it adds size. The second makes a number of functions more expensive, but has a huge impact on malloc and free; the debug runtime versions are careful to "poison" the memory they touch with values to make uninitialized data bugs clear. I believe with the MSVCP* STL implementations it also eliminates all the allocation pooling that is usually done, so that leaks show exactly the block you'd think and not some larger chunk of memory that it's been sub-allocating; that means it makes more calls to malloc on top of them being much slower. The third; well, that one does lots of things (this question has some good discussion of the subject). Unfortunately, it's needed if you want single-stepping to work smoothly. The fourth affects lots of libraries in various ways, but most notable it compiles in or eliminates assert() and friends.

  So you might consider making a build with some lesser combination of these selections. I make a lot of use of builds that use have symbols (/Zi and link /DEBUG) and asserts (/DDEBUG), but are still optimized (/O1 or /O2 or whatever flags you use) but with stack frame pointers kept for clear backtraces (/Oy-) and using the normal runtime library (/MT). This performs close to my release build and is semi-debuggable (backtraces are fine, single-stepping is a bit wacky at the source level; assembly level works fine of course). You can have however many configurations you want; just clone your release one and turn on whatever parts of the debugging seem useful.

  From puetzk

• Qt has reimplemented most c++ standard library stuff with different interfaces. It looks pretty good, but it can be expensive for the commercially licensed version.

  From Greg Rogers