Thoughts on the STL?

    This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

    • Thoughts on the STL?

      What's everyone's thoughts on STL? Right now a small war has sprung up here at work over e-mail regarding it's usage. Mr. Mike, are you going to be including any stuff on the STL in the book?
    • There are upsides and downsides to the STL (I shall assume containers here, not the other (lightweight) goodies). The upsides are quite apparent and rarely in dispute (it's handy to use).

      What were the listed downsides to STL?

      For starters, there is standardization. Are you maintaining a PC build? Is there concern over subtle variations in implementations between MS and your compiler. Perhaps writing your own STL or modifying SGIs can get around this; but I don't know what the limitations of your compiler are. . . .

      I think that there are certainly some objectionable uses of STL in a console environment. . . These are certainly an issue in areas where you would not want to be paying the price for that STL container's implementation. Take, for instance, some per-frame operation that checks a number sequence for a repetation. This can be elegantly represented in an std::map<>; but if those numbers range from (0-small known value), you could implement it much faster, without allocations, using a fixed-length array of chars (or bits). Extreme example; but I don't think you'd EVER want a TRUE tree-based STL map in your game.

      In short, one concern is that someone will casually use a list/map where he just shouldn't be using a list/map.

      Now, std::vector<>. This is a valid substitute for an allocated array, to be sure. But if you trip its resizing (through failing to reserve), it will eat you alive in fragmentation and reallocations.

      Discuss a compromise: Write your own containers, a couple that have valid implementations. These can be recreations of slist and list (list is double-linked), and a modified vector. Modified vector? Yes, give this modified vector proper asserts/guards, change its constructor to take a reservation (and pre-reserve space), and have it assert if it EVER goes over the limit, and NEVER resize.

      Now, you likely don't want to ship with an std::map in your game. However, I would recommend you implement your own maps on a per-case basis.

      Why?

      Let's imagine we end up with a family of data structures for which you WOULD have used std::map (speed permitting), and they are all indexed with a GoblinId.

      I suggest this - that you implement a special GoblinIdMap<>.

      Early in the project, you can quickly get it up and running by defining GoblinId to merely be a string, and GoblinIdMap to merely be a std::map<GoblinId, Data>

      When it gets a little later in the project, and everyone's already been using GoblinIdMap, you look at what GoblinId-related activities have developed. You soon discover that you can represent GoblinIds, instead of as strings, as some numerical from 0-10, or maybe some hash value. You can switch GoblinId, behind the scenes, without anyone having to change their code to reflect this implementation detail.

      Now, you figure that you can rewrite GoblinIdMap to, while exposing the same functions to the outside world, be implemented as a hash map, or some data structure based upon a compile-time fixed-length sparse array. Again, you can make this switch without anyone else having to know (except now, when release build compiles, their GoblinIdMap lookups are optimized to the max, with searches now being direct numerical lookups). Or perhaps later you think of an even BETTER implementation of GoblinIdMap later - you now have latitude to change it, safetly. If everyone was passing around ints (in place of GoblinIds) from day one, and was implementing their OWN sparse arrays, you would not have the power to make such a change that would impact the entire project - instead, one would think: "Well, they do this in too many parts of the code, we'll just put off the switch indefinitely).

      Pseudocode (abbreviated, rushed and exaggerated):

      What you use to get everyone up and running:

      typedef GoblinId std::string;

      teplate <class Data>
      class GoblinIdMap : public std::map<GoblinId, Data>
      {
      };




      What you ship with:


      #define MaxGoblinId 10
      class GoblinId
      {
      GoblinId(int const val)
      {
      Assert(val < MaxGoblinId);
      }

      int mVal;
      }

      template <class Data>
      class GoblinIdMap
      {
      public:
      const_iterator const find(GoblinId const & key) const
      {
      // do direct lookup
      }

      // Here, implement a bunch of other functions to
      // make this class "feel" like std::map

      private:
      char mData[sizeof(Data) * MaxGoblinId];
      bool mDataPresent[MaxGoblinId];

      }



      So what's the conclusion? I guess, largely, don't use the ACTUAL STL; but do things in an STL-style manner as much as possible. You can cover you a** without sacrificing any real speed or ram.
    • There is some EXCEEDINGLY heated argument over it all, but in the end I agree with one of the comments that was put forward:

      Without going into specifics, there was a fairly serious bug in a container class that was written here.

      So someone commented (and I agree) that one should use the STL first, and optimize later. You'll be using a class that's already (hopefully) tested, and is known to work. If it's too big/slow/evil whatever, you can write your own LATER.

      There were a variety of anti-STL arguments, two of the larger ones being that the object code size increases dramatically (a big issue on consoles) and compile times increasing. I won't try and defend or uphold any of their arguments, because I don't know any of the specifics.
    • Thoughts on the STL

      STL is supposed to be a black box, and programmers are supposed to just use it without knowing how the guts work.

      Baloney.

      I say, use STL unless you can make a case for why you can do something better. To make that case, you must know the implementation details. So much for the black box - and that includes keeping track of different STL implementations on different systems, OS's, compilers, etc.

      Never assume anything - including your ability to write something better than STL.

      At worst - it's a great way to get some complicated stuff up and running in a snap.
      Mr.Mike
      Author, Programmer, Brewer, Patriot
    • Is there a good resource that tells you what each STL implementation is doing?

      I still stand by the fact that you can always go back and rewrite problem areas if you have to. Doug Church cited an example of saving 3.1MB (!!) of RAM by writing their own String class over cStr!
    • I don't know of any...
      Mr.Mike
      Author, Programmer, Brewer, Patriot
    • The STL standard doesn't really define implementations.

      However, the implementations I've seen for map are always rb trees, list is, well, a list, and std::vector is a vector that doubles in size when it goes over capacity.

      You CAN write something better by writing something more specific to the task. For example, std::vector - no matter HOW it's implemented, there's no way it can optimally store 27 elements without reservation - it can't guess "27", and any implementation would either have to waste extra space or re-allocate. Even if you implement a reserved_vector in terms of std::vector, you want the one that people are allowed to use to force a reservation value and stick to it, not allowing size to go beyond that value.

      Vector is a nasty one in this respect. It's easy to know you don't want to waste space/time with an rb tree; and don't want to allocate for a list. . . . but a normal std::vector<> can look very benign (used properly it is not significantly worse than an allocated array); but if you forgot to reserve it will cause fragmentation/reallocations in a manner that will not be readily apparent.

      Here I've described an area where, at the very least, a wrapper with guards and a constructor would yield significant benefits on a console over developing with pure std::vector<>.

      Another thing to worry about, with stock STL implementations, is that many lack asserts (MS's does, for sure). With stock std::vector<>, or map, you will receive no assert or warning if you read past the end, or dereference a bad iterator (yes, the latter CAN be implemented in a debug-only fashion).

      If the standard stl is to be used in any fashion, even as primitives, it may pay to wrap the TRUE stl containers, once, and use THESE from then on, if nothing else but to have predictable asserts. (I've come to regret not doing this with Microsoft's).

      The post was edited 2 times, last by mlamari ().

    • Another thing to keep in mind with stl containers, their insertion mechanisms.

      container.insert(blah) cause a copy of a blah. Even if you build blah on the stack (or run constructor between the params - which puts it on the stack) you WILL have 2 copies of your object generated. This can become an issue if said objects are sizeable, or they cannot be copied (yes, one could use pointers here; but shame to be FORCED to merely to be able to insert).

      In the past (in a custom STL) I've used an alternate insert, that, instead of taking the object, takes something that can placement new the object (essentially, an object that contains the construction params and a Build(T *) function). But here we're really starting to deviate from STL.

      Duplication of an object upon insertion to an STL container is something to keep in mind.

      The post was edited 1 time, last by mlamari ().

    • Before complaining so much about any particular STL container, keep in mind what that we have lots of containers because no single one does all jobs equally well. That's part of why it's still fun to be an engineer. Ok, so std::vector's allocation scheme doesn't fit your problem--that's not a shortcoming of STL. If MS didn't implement the STL well, then shame on MS, but it's not a shortcoming of STL.

      Those complaints about vector, for example. I keep hearing these all the time and I just don't understand. I've been using this baby problem-free for years and years. If somebody's doubling scheme implementation (not STL, per se) is too expensive, then consider that you DON'T have to reinvent STL to avoid it--STL already allows you to write a custom allocator! You can write your own non-doubling, non-fragmenting, whatever memory pool-based allocator all within the scope of STL. I don't need to throw out the baby with the bathwater, to be horribly cliche.

      The fact is that we often have problems where array size is actually unknown ahead of time, precluding a reserve call. Consider reading from disk or generating simulation states, until reaching a termination value, for example. Just because I can't call reserve() doesn't mean I have a horrible problem that can't be solved with std::vector. It might be worth considering another container, yes, but it's not necessarily a disaster for relatively small arrays. std::vector's automatic resizing has often worked just fine for me here.

      Once when I had a modest-size array, one to two hundred elements. The elements were of substantial size, so I put my own incremental resize() calls in the simulation loop, to preempt the std::vector doubling. It wasn't sexy and I'd do it differently today, but I didn't have to reinvent a new container to do it and I spend my development time on the simulation problem instead. After profiling, we found that the best place to apply optimization was still in the simulation, and not reallocation, so I never had to optimize that allocation scheme.

      If reallocation and lots and lots of insertions are a problem, then it's probably not the fault of vector for doing it poorly--it's the fault of an engineer not choosing a more appropriate container.

      Copy-on-insert efficiency is a general container efficiency problem, not an STL problem per se. You can use STL to build containers of pointers or smart pointers (but then why not just use a list?), so that insertion, sorting, etc, will avoid copy costs, and that doesn't seem different than any new non-STL container that you would write on your own, so why bother?

      I won't defend MS's omission of out-of-range vector indexing asserts (that's heinous), but frankly, I still actually never miss it. Same for dereferencing bad iterators. Why don't don't these cause me problems? Well, because somebody else already figured out the most common uses for container iteration, and they made a bunch of code that I can already reuse--all the STL's <algorithm> code. Using these algorithms and functors, I find that the times where I actually use an indexing operator, or iterators other than begin() and end(), are now so rare that (again), over many years now of STL use, I just don't experience problems due to MS's implementation deficiencies. And that is, perhaps, yet another testament to the design of the STL.

      Because STL is templated, code bloat can be an issue if you linker sucks, and this may be the case on a new console. Some crappy linkers will not detect and merge the duplicated container code from all your OBJ's. I know of one place where this was such a problem that it required an unpleasant solution: they turned the project into a single CPP file that #included all the other CPP files. In short, they bypassed the linker by using the compiler to generate a single OBJ file. Probably a horrendous compile, but it apparently resulted in a huge decrease in the EXE footprint.

      I'm not sure that I like your proposal to wrap the STL. The main reason is because of the "S" in STL. Why should I have to learn your wrapper? Will your wrapped containters work with the <algorithm> code? Do your wrappers allow custom allocators? Maybe I misunderstand the degree of wrapping you imply?

      So I can't agree with the earlier conclusion that we should not use "ACTUAL STL". Maybe you just meant don't use an unmodified MS STL, and don't be careless about the MS implementation details?

      It's not wrong to write your own containers when you have specific domain knowledge that you can apply to your container problem. But several authors do point out that you really should first have that special domain knowledge, because all too often, you won't end up fewer CPU cycles or fewer bugs. Sometimes though, but I'd always start with STL. Like Mr. Mike (and many other authors) say: use STL until you can make a case for doing something better, and don't assume you can do better. There's a lot of work behind the STL.

      There was a post-mortem article in GameDevMag a few years ago, where the lead programmer started out banning the STL, claiming that any programmer who couldn't write a linked list wasn't a real programmer (or something). Then he himself wrote a linked list bug a couple weeks later, and changed his decision. By the end of the project, his post-mortem conclusion was that using the STL was the right thing to do. I wish I could find that article, but it's pretty old now.

      -dclark
    • Originally posted by dclark
      There was a post-mortem article in GameDevMag a few years ago, where the lead programmer started out banning the STL, claiming that any programmer who couldn't write a linked list wasn't a real programmer (or something). Then he himself wrote a linked list bug a couple weeks later, and changed his decision. By the end of the project, his post-mortem conclusion was that using the STL was the right thing to do. I wish I could find that article, but it's pretty old now.


      I wish you could, too.
    • I've one thing to add to this discussion - this is a theory but based upon observations of the various code bases ( basi ? ) I've worked on since 1989. I actually have a perfect test case on hand right now at work, but not the time to truly do the test. Maybe later this spring.

      Templated code use can cause an indirect negative effect on your production team, specifically by the nominal pattern of completely inline implementation requiring full definition of related constructs the compiler ends up needing much more context in the compile-time environment per-module processed ( where a module is a single cpp file ). This, I theorize, significantly expands the intermediate file(s) - .obj - and potentially the debug symbology. On a large code base, and mind you I think my test case has a number of other problems but that this is a major contributor, this can significantly slow build times owing the dramatically larger disk-space in use and sheer number of bytes processed both at compile and link.

      Currently, the code base I am working against results in a debug build with four executables totally 56 Mb of disk space and program database files totalling 125Mb of disk space - the intermediate files consume over 1.5 Gb of disk space and the link phase for each executable consumes over 200 Mb of system memory - on a Windows 2000 machine we need more than 512 Mb of memory to avoid a swap-storm with only devtudio ( albeit .NET ) loaded. Running a command-line build environment does not help in our case because we need to use the devenv.com frontend since our projects are not makefile-based.

      The short of my theory is that there is simply too much implementation code in header files, and most template code is built this way, and when template based constructs are used as member data this blossoms out.

      This does NOT have to be this way, there is no requirement that template implementations be inline at all, nor globally available. Segregating declaration and implementation works just fine on them, and further gives you control over how many instances of the code end up existing, and how much is inlined.

      Geeze, this seems like stream-of-conciousness stuff ... sorry.
    • Oh, one other gotcha related to template constructs - watch out for class-specific static elements. The MS implementation uses this in a few of the containers / iterators. The problem this creates is that each link-unit will get a discrete copy of the static data, and the one that is updated will depend on the running context of the code - whether it is "in" the exe or in dll 'a' or dll 'b' or whatnot.

      This kind of problem will not bite you if you use statically linked CRT and monolithic executables, but that is not always an option.

      I have had to make isolation layers to get around this on projects where DLL files were used, and IIRC we had an "interesting" time running down a problem caused by this back at Retro - I don't remember who found it but I do remember it happened.