I’ve been using the STL since before it became part of the 1998 standard, so I’ve heard a number of opinions on it. Still it was a little surprising to hear Alex Stepanov, the library’s creator, say that it was out-of-date. We both work for A9.com, one of the perks of which is that I have occasional conversations with him. (Submit your resumes to jonkalb (at) a9.com.)
He knew he had my attention.
Alex has devoted his professional life to the intersection of mathematical purity and hardware-based practicality. The STL is the product of that work and is the best expression of applying mathematics to the hardware of its day.
But hardware has changed since the STL was designed. In at least two important ways. The first is that multi-core and even many-core machines are the common target so heap allocation, always expensive, now requires a lock. The second is that the assumption that all memory accesses are equally expensive is no longer valid. Caching has a huge impact on performance. Accessing memory in the near vicinity (a cache hit) is dramatically less expensive than arbitrary memory accesses.
So what are the implications for STL users?
One implication is that allocators are becoming more and more important. Allocators as originally designed were not created to deal with allocation performance, but to deal with near and far pointers (if you don’t know about them, count your 32-bit blessings). For this reason, the standard definition of allocators hasn’t been sufficient to deal with some of the allocation strategies users want to exploit.
This has changed in C++11.
Alisdair Meridth is the Chair of the Standard Library Subcommittee and an employee of Bloomberg, one of the companies that is really concerned about the impact of allocators on performance. Alisdair spoke on “Allocators in C++” at C++Now 2013. I’ll refer you to that talk because it brings you up to date on what is in C++11 and what is being proposed for future standards and because referring you to it allows me to pretend that I actually understand it all.
In a future posts, I’ll discuss the implications of containers, both for contiguous containers and node-based containers.