Hello, world! Today, I (Stephan T. Lavavej, library dev) would like to present one question and one Orcas bugfix.
First, the question: What is the future of C++? Or, phrased crudely, does C++ have a future? Will it grow and evolve, with programmers using it in new application domains and finding ways to use it more effectively? Or will it stagnate, with programmers using it in fewer and fewer application domains until nothing new is being invented with it and it enters "maintenance mode" forever? After C++'s explosive growth over nearly the last three decades, what is going to come next?
This question has a finite horizon. No language can possibly be eternal, right? (Although C is certainly making a good run for it.) I don't expect C++ to be vibrant in 2107, or even 2057. 50 years is an almost incomprehensible span of time in the computer industry; the transistor itself is turning 60 years old this year. So when I ask, "what is the future of C++?", I'm really asking about the next 10, 20, and 30 years.
Here's how I see it. First, consider C++'s past. As it happens, Bjarne Stroustrup recently released an excellent paper covering C++'s recent history, "Evolving a language in and for the real world: C++ 1991-2006", at http://research.att.com/~bs/hopl-almost-final.pdf . There's also a wonderful 1995 interview with Alexander Stepanov at http://stepanovpapers.com/drdobbs-interview.html which explains C++'s machine model.
C++'s machine model has a relentless focus on performance, for several reasons. Being derived from C, which was "fat free", is one reason - in the realm of performance, C++ has never had to lose weight. It's just had to avoid gaining weight. Additions to C++ have always been structured in such a way as to be implementable in a maximally efficient manner, and to avoid imposing costs on programmers who don't ask for them. (As the Technical Report on C++ Performance, now publicly available at http://standards.iso.org/ittf/PubliclyAvailableStandards/c043351_ISO_IEC_TR_18015_2006(E).zip , explains, exception handling can be implemented with the "table" approach, which imposes minimal run-time overhead on code that doesn't actually throw. VC uses the "code" approach on x86 because of historical reasons, although it uses the "table" approach on x64 and IA-64.) Historically, C++ ran on very small and slow machines that couldn't bear any unnecessary costs. And now, C++ is used to tackle huge problems where performance is critical, so unnecessary costs are still unthinkable!
Aside from the elevator controllers and supercomputers, does performance still matter for ordinary desktops and servers? Oh yes. Processors have finally hit a brick wall, as our Herb Sutter explained in 2005 at http://gotw.ca/publications/concurrency-ddj.htm . The hardware people, who do magical things with silicon, have encountered engineering limitations that have prevented consumer processors from steadily rising in frequency as they have since the beginning of time. Although our processors aren't getting any slower, they're also not getting massively faster anymore (at least, barring some incredible breakthrough). And anyways, there isn't plenty of room at the bottom anymore. Our circuits are incredibly close to the atomic level, and atoms aren't getting any smaller. The engineering limit to frequency has simply arrived before the physical limit to circuitry. Caches will continue to get larger for the foreseeable future, which is nice, but having a cache that's twice as large isn't as nice as running everything at twice the frequency.
As programmers, we are faced with a future that looks radically different from what we're used to: the processors we have today are about as fast as we will ever have. The computer industry undergoes constant change, of course, but we rather liked the kind of change that made our programs run twice as fast every couple of years with no extra work on our part.
Undaunted, the hardware engineers have begun putting multiple cores in each processor, which is actually increasing overall performance quite nicely. (I'd sure like to have a quad-core machine at work!) But not everything is as embarrassingly parallel as compiling. Single-core performance still matters. And the problems that we, as programmers, are asked to solve are getting bigger every year, as they always have.
Therefore, I say that C++ is uniquely positioned to weather this performance storm. Other languages will continue to find uses in application domains that aren't performance-critical, or that are embarrassingly parallel. But whenever the speed at which an individual core crunches stuff matters, C++ will be there. (For example, 3D games. When Halo Infinity is released in 2027 - and yes, I totally just made that up - I fully expect it to be written in C++.)
Among C++0x's biggest core language changes will be variadic templates, concepts, and rvalue references. The first two will make writing templates a lot more fun. That's great, because templates are a powerful way to produce highly efficient code. And the third will address one of the flabbiest areas in C++03 - its tendency to make copies of values. (Things that have value semantics are great - unnecessary copies aren't.) By eliminating unnecessary copies through "move semantics", rvalue references will make value-heavy code, like any code that uses the STL, significantly faster. The future is bright!
Why am I thinking about performance? Well, because one of my fixes has reduced the performance of the Standard Library. Before you scream in agony, let me explain...
In my first VCBlog post, I mentioned that I was working on something which has since been checked into Orcas (VC9). I call it The Swap Fix. To recap, Visual Studio 2005 (VC8) introduced new iterator debugging and iterator checking features. Iterator debugging, enabled by _HAS_ITERATOR_DEBUGGING, performs powerful correctness verification. Iterator checking, enabled by _SECURE_SCL, performs minimal checks that serve as a last line of security defense. For example, _SECURE_SCL will terminate a program that triggers a heap overrun with a vector iterator.
All that is explained by MSDN documentation. The story behind this is interesting. The _HAS_ITERATOR_DEBUGGING functionality was provided by Dinkumware, the company that licenses their most triumphant implementation of the Standard Library for inclusion in Visual Studio. The _SECURE_SCL functionality was added by Microsoft, in order to improve the security of programs running on Windows. In order to perform their checks, both _HAS_ITERATOR_DEBUGGING and _SECURE_SCL make iterators contain additional data members, such as pointers to their parent containers. _HAS_ITERATOR_DEBUGGING, because it is enabled by default in debug mode (and not obtainable in release mode), also builds singly linked lists that allow containers to refer to all of their iterators. This is expensive performance-wise, but performance is not critical in debug mode, and this enables excellent checks.
_SECURE_SCL, because it is enabled by default in release mode, strives to impose minimal performance penalties. Therefore, when it is enabled, although iterators have pointers back to their containers, containers don't have pointers to their iterators. (Updating "iterator lists" is too time-consuming for release mode.)
Now, VC8 RTM/SP1 had a bug when _HAS_ITERATOR_DEBUGGING was disabled and _SECURE_SCL was enabled (e.g. the default for release mode). When you have persistent iterators into two containers, and then swap the containers, the Standard requires that the iterators remain valid (23.1/10). Unfortunately, the parent pointers that _SECURE_SCL added to iterators were broken by such a swap. (The containers being swapped have no way to find the iterators which point into them.) Dinkumware's _HAS_ITERATOR_DEBUGGING is immune to this problem since it can walk the iterator lists and update all of the parent pointers. This option is not available to _SECURE_SCL.
In order to fix this conformance bug, The Swap Fix in Orcas makes every Standard container own an additional dynamically allocated object, imaginatively called "the aux object". Each container holds a pointer to its aux object, which holds a pointer back to the container. Each iterator, instead of holding a pointer directly to its parent container, now holds a pointer to its parent container's aux object. It's true: everything can be solved by an extra level of indirection. When containers are swapped, they also swap their aux objects. This allows the containers to "tell" their iterators their current location, without having to know where they all are. The result is that VC9 will be conformant even under _SECURE_SCL.
The performance issue is that the aux object, while unavoidable (without "pimpling" the containers, which would probably be even more expensive for performance), is not free. Each Standard container is now larger because it has to hold a pointer to its aux object. The aux object has to be dynamically allocated, occupying more space and taking more time. And _SECURE_SCL has perform a double indirection when going from an iterator to its parent container. I've measured the cost of the double indirection, and it is nontrivial: programs that use iterators in deeply nested loops may run at half the speed as before. (In general, only hand-written loops will be significantly affected. The Standard algorithms perform checking once and then "uncheck" their arguments for increased speed. It's yet another reason to avoid hand-written loops!) Most programs should not experience noticeable performance changes because of this fix, and some programmers' lives will be made easier because of the increased conformance, but other programmers will have to deal with the fallout of The Swap Fix. That's why I write it with capital letters.
This is something to keep in mind: although performance is important, it is not all-important. Correctness and security trump performance. _SECURE_SCL increases security, and this fix is necessary to restore correctness. The performance in VC8 was an illusion, since it was obtained at the cost of correctness. Orcas's performance will reflect the true cost of _SECURE_SCL. As before, programs will be able to turn off _SECURE_SCL in order to extract maximum performance. How to disable _SECURE_SCL (and _HAS_ITERATOR_DEBUGGING) properly might be a topic for a future blog post - it's easy to do incorrectly, and we're thinking about ways to make this process more robust in Orcas + 1.
The usual trick in situations like this is to add a bit of extra space to the size of the container's first heap-allocated memory (for vectors, the block, for node-based containers, the first node), and store the aux data there. This avoids increasing the size of the fixed portion of the container, the overhead of an additional allocation, and (potentially) the extra indirection as well (if you store all necessary information for iterator validation in that extra storage rather than in the fixed portion of the container). Would this solution work here?
That is an excellent observation. It could work. We considered this, but it had a number of downsides.
First, it requires per-container logic. Four different kinds of containers were affected: vector, deque, list, and the tree-powered set/multiset/map/multimap. (string was considered too risky to fix for Orcas.) Five, if you count the unspeakable vector<bool>. That increases the complexity, and hence the risk, of the fix.
Specifically, containers would have to be taught to keep the aux data allocated even when they'd rather be empty. Node-based containers would also have a "special node". If the special node is actually a "fat node" that holds data, what happens if the data is erased and the node is no longer necessary? If the special node doesn't hold data, then it has few advantages over an aux object.
Second, for block-based containers, it requires the Struct Hack. (A use for the Struct Hack! I was quite surprised when I realized this.) Unfortunately, the Struct Hack is not portable C++03. VC actually prohibits it under /Za (see http://msdn2.microsoft.com/en-us/library/d88dx3xf(VS.80).aspx ). Therefore, the Standard headers, which must be usable under /Za, cannot use the Struct Hack. There are various non-Standard ways to cope without compiler support for flexible array members, but using them runs the risk of the compiler doing something strange for certain types (or certain platforms, such as x64 or ia64). There is a reason that the Struct Hack was legitimized in C99 - it provides layout guarantees that are not otherwise obtainable. It would be quite unfortunate if this fix, whose sole purpose was to increase conformance, actually decreased it in certain cases.
Because the Swap Fix was checked in right before Beta 1, and indeed wasn't truly finished until Beta 2 and beyond, we believed that a container-independent (and portable) approach would be robust and quick to finish. It ended up taking longer than expected to nail down everything (specifically, some threading and allocator mischief), but the container independence did greatly simplify the fix.
We may want to change how this works in Orcas + 1, especially if many customers find that the Swap Fix introduces unacceptable overheads into their applications. (We have gotten no such reports through Microsoft Connect or otherwise since Beta 1 was released, so our current understanding is that the overheads do not significantly impact most applications.)
I should also point out that Visual Studio 2008 will include several performance improvements to the Standard Library. While writing the Swap Fix, I noticed that many iterators contained unnecessary data members. They have been removed, making them smaller and hence faster. (They also became slightly more conformant, although no one will probably notice this.) For example, in VC8 SP1 debug mode with _HAS_ITERATOR_DEBUGGING disabled, deque<int>::iterator was 16 bytes. In VC9 Beta 1 and above, it is 8 bytes. These improvements are small (although I'm sure someone somewhere will sure appreciate their iterators being half the size), but every bit counts. If anyone is interested, I can present the full matrix of what iterators are changing size and by how much.
Stephan T. Lavavej
Visual C++ Libraries Developer
John, if you tack this extra structure at the end of the first heap allocation then you're going to free it when that allocation is freed (e.g. due to a resize). You'd need immutable containers of pre-determined size for this to work on a general heap that cannot free at a smaller granularity than was allocated. Or maybe I missed something?
Back to Stephan now, interesting post! I love the opportunity to get insights into what you guys are doing.
I agree with you that C++'s future is probably bright indeed, though we have examples of highly performant hardware that cannot easily be programmed in C++ due to conflicting memory model assumptions. This doesn't apply to your example of single-threaded performance, but it might hurt somewhat on the multi-threaded side.
Very interesting post!
Congratulations and thank you :-)
Nice blog. Just a snippet from your post "Correctness and security trump performance..."
this is true in most cases, and most programmers will nod and say "yah, thats true... I can accept that". However what about the applications that cant deal with it. Example communication applications, where every milisecond is a slow death.
Now I like the fact that this conformance can be fixed simply by an option, but what happens when you guys run into a similar scenario where an option wont be available? do you always sway towards security over performance?
in short, what type of criteria do you use to evaluate these situations ?
> However what about the applications that
> cant deal with it. Example communication
> applications, where every milisecond is
> a slow death.
There's always the big hammer of disabling iterator checking. This makes STL-using code run as fast as possible. Removing a line of security defense shouldn't be done unless absolutely necessary, though.
When performance is critical, there are many other options. For example, as I mentioned in the post, the Standard algorithms achieve high performance even when iterator checking is enabled because they lift out the checks and then work with unchecked iterators. If hand-written algorithms are necessary, using pointers will bypass the checking (of course, that works for vectors only and not deques, etc.).
And finally, there is perhaps the biggest hammer of all, using hand-written data structures and algorithms. The STL is a very general, very high performance library, but these are sometimes in conflict. Specialized data structures can be more efficient for certain tasks. Hand-written code should be necessary in very few situations - as ever, performance hotspots are usually very localized.
> Now I like the fact that this
> conformance can be fixed simply
> by an option
I'm not sure what you mean. VC9 will conform to 23.1/10 in all modes for all containers (except std::string).
Great post Stephan!
Well said, but I do believe C++ will still be kicking in 2057. In fact I think it will outlive .NET. (I think .NET will eventually, yet again, be marketing-driven into a new technical entity, but I digress).
The big change (I believe) we'll see with C++ is improved configuration and built-in type/performance/security/etc checking. So, I believe the future of C++ is exactly what you are currently doing today: extending, improving, optimizing, and securing C++ while at the same time providing the actual user (i.e. the developer, architect, and further in the future: executives) with the ability to specify exactly how they expect C++ to operate (e.g. _SECURE_SCL). For example, a development team will simply decide which security, performance, or reliability features to enable at compile time (Design and Development time too). In truth, these are just a bunch of trade-offs, albeit highly-important, and rightly managed by the enduser (i.e. product development team). Right now, Microsoft is currently infatuated with Dynamic languages, with .NET leading the way. Doing everything at run-time initially seems really cool, but looking years forward, this is fraught with peril, pain and results in a significant rise in management complexity, and lowers performance to the lowest common denominator). With clever (and IMHO sure-to-happen) C++ extensions (for lack of a better word), you will be able to securely enable a certain check a compile time, and they check will always be compiled into code. So, the enduser makes the final call on what checks auto-magically occur. On the flip side, excluding these “extensions” at compile time results in no performance degradation. Ideally, a vast amount of earth-shattering-functionality will be enabled (added) in the language. Take something like Numega’s Bounds Checker product: overtime stuff like this will be baked-into VC++. If you think this model through a bit (over years and years), it sure does look like this is the future of C++. Then, over time as more language “extensions” proliferate, we’ll need, and thus see, greatly improved configuration… leading to a significantly improved and truly awesome VS IDE.
These are just my own view, and I’d love to hear others thoughts.
Wow, what a surprise to see this bug mentioned in a post. Coincidentally, I was the fellow who posted the problem a year ago (I just set _SECURE_SCL=0 and went on my way). I had no idea it would be such a hassle to fix!
> Doing everything at run-time initially seems really cool, but
> looking years forward, this is fraught with peril, pain and
> results in a significant rise in management complexity, and
> lowers performance to the lowest common denominator
Throughout the industry, "dynamic" is often intended to mean "good", and "static" to mean "bad". "dynamic" has a bunch of connotations: "flexible", "adaptive", etc. Who wouldn't want to be "dynamic"?
The problem is that run-time is a very late time to be doing anything. It's much better to perform correctness checks as early as possible, so that code fails to compile on the developer's machine instead of throwing some exception on the user's machine. It's also a lot easier to perform optimizations at compile-time, when you have almost all the time in the world, than at run-time, when every millisecond counts. Being "dynamic" is thus a burden in several ways, though it has advantages. (Using a language I'm familiar with as an example, there is no way that C++ can manipulate its own source code in the way that Scheme does.)
C++0x concepts will move correctness checks to an even earlier point in compilation, so that things blow up as soon as you try to instantiate a template incorrectly, rather than having the instantiation proceed and fail miserably later.
Of course, it takes a certain level of understanding to appreciate why hideous template errors are actually a good thing, which is why "static" checking is underappreciated.
> I was the fellow who posted the problem a year ago
Hey, you are! Thanks again for filing that bug. As far as I can tell, you were the first one to find it.
Like I said in my first post, Microsoft Connect does indeed work. :->
> I had no idea it would be such a hassle to fix!
The problem was that an incorrect assumption (that containers could not move around in memory) had been baked into the _SECURE_SCL machinery. Fixing this involved modifying all Standard containers and iterators, which is why the fix was so extensive. Then a bunch of little things added complexity (deque, for example, was broken even when _SECURE_SCL == 0; fixing that required more machinery in <xutility> and more preprocessor magic. Then that broke debugger visualization of deque iterators...).
The extensiveness of the Swap Fix is why there are no plans to include it in any service pack for VC8.
I enjoyed reading your post! In particular I think the insight into what you guys are doing is priceless to users like us.
I am somewhat concerned with the future of performance-driven code in C++ though. Not alarmed, just concerned. The peformance issues that dominate with 100+ threads on a single CPU die are very different from those that dominate with 2~8, though you get to see the trend starting down there.
With enough threads running the instructions become free, in fact you'll be lucky to fill up the instruction slots you already have. Very quickly Amdahl's law pins you at the interface to memory. In the past we fended it off with L[N] cache designs, but these need more spatial coherence than you're likely to see on average with a superthreaded workload.
So the largest threat to C++'s position in performance is probably hardware that cannot easily be programmed using the memory model assumed by C++. There are many examples out there already if you look outside traditional processors (e.g. Cell is one). For many high-profile workloads it's more important get the most out of that hardware than it is to write clean/simple/happy code using C++.
That's my C++ performance concern... but no alarm just yet!
(I hope this didn’t post twice, I had a glitch when I posted)
I am somewhat concerned with the future of performance-driven code in C++ though. Not alarmed, just concerned. The peformance issues that dominate with 100+ threads on a single die are very different from those that dominate with 2~8, though you get to see the trend starting there.
With enough threads running the instructions become free, and you'll be lucky to fill the instruction slots you already have. Very quickly Amdahl's law pins you at the interface to memory. In the past we fended it off with L[N] cache designs, but these need more spatial coherence than you're likely to see on average with a superthreaded workload.
So the largest threat to C++'s position in performance is probably hardware that cannot easily be programmed using the memory model assumed by C++. There are many out there already if you look outside conventional CPUs (e.g. Cell is one).
> The peformance issues that dominate with 100+ threads on a
> single die are very different from those that dominate with 2~8
Yes! That is a deep insight.
> With enough threads running the instructions become free
Amdahl's Law actually says that almost everything has serial bottlenecks, and the efficiency with which they are executed will continue to matter.
> Very quickly Amdahl's law pins you at the interface to memory.
That would be Amdahl's Rule Of Thumb (or Amdahl's Other Law; see http://en.wikipedia.org/wiki/Amdahl's_law ).
> In the past we fended it off with L[N] cache designs, but these need more
> spatial coherence than you're likely to see on average with a superthreaded workload.
Caches are continuing to get bigger, and so is bandwidth to main memory. There's definitely more and more stress being placed on the memory subsystem, though (and latency continues to be killer).
One advantage that C++ has here is that deterministic destruction allows it to consume as little memory as possible. Hertz and Berger's paper "Quantifying the Performance of Garbage Collection vs. Explicit Memory Management" at http://www.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf is a fascinating read.
> So the largest threat to C++'s position in performance is probably hardware
> that cannot easily be programmed using the memory model assumed by C++.
I completely agree. Like Stepanov said, C "is the best representation of an abstract computer that we have", as of the 1970s. And it continues to be the best representation even today. (This is probably not coincidental - hardware has evolved to preserve the C machine model.)
A significant change in the hardware model would demand a significant change in programming languages. C++0x threading support should make multithreaded programs easier to write and maintain, but I don't think anyone knows what will really work best in the far future era of highly multicore systems. That's why the future is a mystery. :-)
> [...] I don't think anyone knows what will really work best in the far future era of highly multicore systems
> That's why the future is a mystery
Indeed, but the solution space has been explored in a limited sense, enough so we kind of know the shape of it. Consumer productization hasn't really taken off, but every major processor vendor has looked at it, and some have even shipped niche products that are superthreaded. The signs from Intel point at a mass market attempt soon-ish with Larrabee, and similar work came out of Nvidia and AMD/ATI already.
In almost all solutions you'll find the concept of a memory hierarchy in the shape of a tree, rather than a stack. Threads are attached to the leaf nodes of this hierarchy and have variable-speed access to the rest of the system. The major difference between the solutions (with respect to memory specifically) is whether they allow automatic peeking in other branches or not. And this is where C++'s future comes in...
In general only the solutions that do not allow peeking come close to achieving maximum throughput, but only those that allow peeking can actually run C++ code. To be clear, all solutions can be made to offer a "slow" mode for C++ compatibility, but supporting peeking is always really expensive even when you don't peek.
For C++ to run on the no-peeking systems at all (and run fast on peeking systems) you'd need the ability to define "memory domains", as if independent heaps, inside the program. The programmer would have to promise that some domains can only be accessed by some threads, hence determining how the threads/domains are overlaid on top of the hardware hierarchy. What happens when you make a mistake could range from a hard fault, to a kernel-managed re-alignment.
In the market today NUMA is an early example of a solution with peeking. Cell and CUDA are examples without peeking. One day I may blog about STL allocators I developed to better leverage NUMA. They do work, but it's a great deal of pain to scrub a program to use them well. :^(
I invite you to proactively think about this problem from your own perspective, as the library provider. We can talk about it again some day... :^)
No offense, but I'm sick and tired and totally pissed off at hearing how key fixes are being pushed off to a mysical "Orcas + 1" release.
Visual Studio 2005 was a major disappointment as far as C++ is concerned. I have beta tested Visual Studio 2008 and it's still a major disappointment as far as C++ is concerned. The answer seems clear; all the core things that were going to be fixed in Orcas are now in Orcas + 1. I strongly suspect come Orcas + 1, they'll be in Orcas + 2.
Here's a suggestion. Stop adding bizarro features; even put off C++ 0x, which I don't even want, and fix the core product!
In plain English, STOP ADDING FEATURE AND FIX THE ONES YOU HAVE. Print this in 48 point Times New Roman and staple it to the forehead of all your product managers.
> For C++ to run on the no-peeking systems at all (and run fast
> on peeking systems) you'd need the ability to define "memory
> domains", as if independent heaps, inside the program.
C++ actually has support for "weird memory models" (i.e. evil 16-bit segmented architectures). That's responsible for some of the weird weak guarantees around pointers (you can compare any two pointers for equality/inequality, but ordering comparisons require pointers to the same array), and some of the weirdness of STL allocators. That flexibility might be what allowed your NUMA STL allocators to actually work. :-)
> No offense, but I'm sick and tired and totally pissed off at hearing
> how key fixes are being pushed off to a mysical "Orcas + 1" release.
What exactly are you referring to?
The Swap Fix is in VC9. To our knowledge, it is complete and correct. (With the exception of std::string, which was not modified.)
Detecting _HAS_ITERATOR_DEBUGGING/_SECURE_SCL mismatch between translation units that are linked into the same binary will be investigated for VC10. By the time that I joined the team, dug through the STL implementation, realized the badness of this problem, and figured out how to implement detection machinery, it was way too late to add it to VC9. To my knowledge, no one thought of it earlier, and no customers requested it either. Does that seem reasonable?
I also mentioned Orcas + 1 while discussing possible performance improvements to the Swap Fix. That will be driven by customer demand. We know it's a potential issue because I crafted a worst-case test case that demonstrates a 2x slowdown, but we don't know how much it will actually impact code in the real world. Indications right now are "not much".
> Visual Studio 2005 was a major disappointment as far as C++ is concerned.
VC8 was actually significantly more conformant than VC7.1. VC8 also added iterator debugging and checking, both great features for STL programmers.
> I have beta tested Visual Studio 2008 and it's still a major disappointment as far as C++ is concerned.
VC9 has several important conformance fixes. Aside from the Swap Fix, there's also the iterators-living-beyond-their-containers crash under /MDd (or /MTd) /D_HAS_ITERATOR_DEBUGGING=0. That was a regression introduced in VC8 SP1. Fixing it also improved performance. And that's just in the libraries - the compiler is getting a very nice fix that significantly improves compilation speed with PCHs and templates.
> Stop adding bizarro features
> FIX THE ONES YOU HAVE.
I am very interested to hear your specific thoughts on how VC can help native C++ programmers be more productive.