STL: Destructor of Bugs
I’m the newest developer on the Visual C++ Libraries team. My true name is Stephan T. Lavavej, but I often use my extremely convenient initials. I moved here at the beginning of this year after working on and finishing Outlook 2007 Search.
You know how some people are fans of the Harry Potter novels, standing in line outside a bookstore at midnight in order to be one of the very first to experience a new adventure of wizardry? I’m that way with the International Standard for C++. (My following comments apply to “native” C++. I don’t do managed code.) It’s a big document, describing the biggest of languages. Its standard library is of moderate size, but with heavy emphasis on general computation, which is far from being the solved problem (in terms of abstractions, not Turing-completeness) that it is often considered to be.
There’s something about the container-iterator-algorithm-functor structure made possible by C++ and introduced by the Standard Template Library which makes it simultaneously powerful and lightweight. By attacking old problems (how do we generalize containers and algorithms?) in new ways (with templates at compiletime, not inheritance at runtime), the STL pushed bugs – the bane of programmers – to compiletime instead of runtime. Finding errors earlier is always better than finding them later, even if you have to decode unwieldy template error messages (something that the next C++ Standard should help with). Making errors more obvious and quicker to find isn’t the only great thing that the STL does, but it’s certainly one of the most important.
Of course, not all badness can be found at compiletime. The STL has a fairly comprehensive focus on performance, as does all of C++. This means that Standard Library implementations aren’t required to perform bounds checking. The structure of the STL makes it harder for properly written programs to commit bounds errors, but not impossible. Also, some forms of checking are inherently incompatible with maximum performance. The STL permits advanced container manipulations, like inserting and erasing ranges of elements into a container, or removing all duplicates from a container, and so forth. Programs can simultaneously maintain iterators into containers, and these iterators can be invalidated when their containers are modified. For example, when enough elements are pushed back into a vector, the vector eventually runs out of capacity and must reallocate its elements into a larger chunk of memory. Iterators which used to point to the elements in their old locations are thereby invalidated. (So are pointers and references.) Performing runtime checking for invalidated iterators imposes a significant performance cost, so Standard Library implementations aren’t required to do it.
Iterator invalidation isn’t a huge, nasty problem. But it’s also nice for programmers to be able to have their compiler perform thorough correctness checks. Hence, Visual Studio 2005 provides iterator checking and debugging. Iterator checking (controlled by _SECURE_SCL) is enabled by default in both release and debug mode, and detects bounds errors. Iterator debugging (controlled by _HAS_ITERATOR_DEBUGGING) is enabled by default in debug mode (it cannot be enabled in release mode), and detects invalidation errors. You don’t have to do anything special to use iterator checking and debugging, you just get them for free.
However, everything has bugs, including bug-finding machinery. So far I’ve worked on a couple such bugs. One of them, a regression in Visual Studio 2005 SP1, was triggered by compiling a program in debug mode, with iterator debugging disabled (which is not the default), obtaining an iterator into a container, and destroying the container before the iterator. The reason why this triggers a crash is long and complicated, and figuring out the history was fun. We’ve fixed this regression in Orcas.
Another bug, triggered by less obscure code, involves compiling with _SECURE_SCL enabled but _HAS_ITERATOR_DEBUGGING disabled (the default in release mode, obtainable in debug mode) and swapping two containers. Iterators pointing into those containers should still be valid after the swap, but the iterator checking machinery gets confused, triggering an assertion. We’re working on fixing this in Orcas.
Bugs in the Standard Library implementation, which hundreds of thousands (probably millions?) of programmers count on to function properly, aren’t fun. Here’s the good news: we’re aware of these two bugs, and many others, thanks to customers who reported them through Microsoft Connect. Our human testers and their automated tests find many bugs, but they’ll inevitably miss bugs that programmers worldwide will go on to encounter. You, our customers, have tens (probably hundreds?) of millions of lines of source code, exercising every dark corner of the core language and standard library. If you find a bug, and you’re very confident that it’s not in your code, create a good test case and submit it to Microsoft Connect. It’ll wind its way through our processes, and eventually end up on the desk of a real person like me. You’ll even get a response from us when we resolve it. I’m still impressed every time I see it in action.
Stephan T. Lavavej
Visual C++ Libraries Developer