STL – // info

Capacity Members for vector – shrink_to_fit()

C++11 introduced a new member function called shrink_to_fit() for the three sequence containers vector, deque, and string. Before shrink_to_fit() there was no member to reduce capacity on these containers, not even erase(). In fact, the standard made it very unlikely that any implementation would reduce capacity with any call. The standard provides the guarantee that if reserve() is called, then any subsequence addition to the container will not invalidate iterators (until an addition increases the size of the container above the reserve() point.

Since this guarantee is not relaxed even if the user calls erase(), a implementation that chose to reduce capacity would be required to track whether or not reserve had previously been called. It would be theoretically possible for an implementation to add this extra state to the container implementation, but in practice no implementation is going to do that.

Perhaps this lack of attention to minimizing capacity isn’t surprising. In most modern code, our concern is usually time performance rather than space requirements. But C++ is the language of choice for demanding situations and sometimes this means minimizing space requirements.

So what can users do if they want to reduce the capacity of a container? Is this not possible? It turns out that it is possible. In Item 17 of Scott Meyer’s Effective STL, Scott explains that there is a “Swap Trick” that we can use to reduce capacity.

Here is the quick synopsis of the Swap trick:

Container(begin(c), end(c)).swap(c);

where “c” is a container whose capacity we want to reduce and Container is it’s type.

What is happening is that we are creating a temporary container as a copy of our original container using the iterator range constructor and then swapping the contents of the our temporary container with our original container. This works because most implementations will implement the iterator range constructor to not make the capacity any larger than necessary. The reserve() guarantee is swapped to the other container with the call to swap().

In practice we’d almost certainly want to write this something like this:

if (c.capacity() > c.size())
  {
  Container(begin(c), end(c)).swap(c);
  }

or:

if (c.capacity() > (c.size() + some_value))
  {
  Container(begin(c), end(c)).swap(c);
  }

Because this trick involves copying all the items in the container, we don’t want to do it unless it saves enough space to be worthwhile. (In C++11 we could use moves instead of copies. This would make the technique less expensive, but we really only want to do this if the moves are no_except. This is a beyond the scope of what I want to discuss in this post.)

Meyers’ Swap Trick was state of the art, at least until C++11 where we can now do this:

if (c.capacity() > c.size())
  {
  c.shrink_to_fit);
  }

assuming type of c is vector, deque, or string. For vector and string the standard says “… request to reduce capacity() to size().” (We’ll consider the ellipse shortly.) For deque the standard says “… request to reduce memory use.”

Why is deque’s description different than vector and string? Because deque doesn’t have a capacity() member function. The point of the capacity member function is tell us how much we can grow the number of items in the container before an addition would invalidate iterators. This concept doesn’t make much sense for deque, so there is no such call as deque::capacity().

So let’s look at what I left out just now when I quoted the standard. What it really says for vector and string is “shrink_to_fit is a non-binding request to reduce capacity() to size().” The emphasis is mine. The standard has made shrink_to_fit() non-binding. (Also true for deque.) It can be implemented as a no-op!

Why would the committee do such a thing? The standard gives an answer: “[Note: The request is non-binding to allow latitude for implementation-specific optimizations. — end note ]” What this means is that the committee knows that there are implementations where doing the right thing might not result in size() == capacity().

Consider the “short string” optimization. A string is an allocated array and a straight-forward implementation would allocation an array even for a string that was only one character long. One character long strings are not particularly common, but short strings are. So an library might choose to implement the string class so that the class itself has (data member) space for “short” strings so that no allocation is necessary until the size of the string is no longer “short” for some value of “short.” Given this implementation how would capacity() be implemented? In particular would capacity() ever return a value less than the “short” string limit? No because we can always expand the string to the “short” string limit without invalidating iterators (assuming the current size() is less than this limit).

This means that if we currently have a string whose size() is less than the “short” string limit, a “request to reduce capacity() to size()” is going to fail. So the standard doesn’t want to say that the implementation must reduce capacity() to size().

But in my opinion the committee has let us down. While I’m all for giving implementers latitude for their implementations, I think the committee has underspecified this call. It is acceptable to say that the implementation need not reduce capacity() all the way to size(), but it should say that it will reduce capacity at least as far as the Swap Trick would have.

Since the Swap Trick is potentially expensive in time, it is likely only used in situations where users are very serious about reducing excess capacity. Given this, and faced with the fact that shrink_to_fit() may be a no-op, I think conscientious coders will choose to skip the new shrink_to_fit() and continue to use the Swap Trick.

And that is a shame. With shrink_to_fit() the user is very explicitly stating the desired outcome, so this has the potential to allow implementers to exploit interesting optimizations. This should be better than the somewhat obscure looking Swap Trick. But clarity and interesting optimizations aren’t of much use if users don’t use the new call. And they may avoid it because the old way gives them guarantees that the committee didn’t see fit to apply to the new call.

Please comment on Google Plus or reddit.

Capacity Members for vector – reserve()

I want to talk about a couple of the lesser known member functions of the best known STL container: reserve() and shrink_to_fit(). These members manipulate the vector’s capacity. The reserve() member is original and I discuss it in this post. New with C++11 is shrink_to_fit(). I’ll talk about it in a future post.

Note: The use of kittens in explaining C++ is patented by STL. This image used without permission.

The vector class stores data in an allocated array whose allocation the class handles for us. Each call to push_back() does a check to see if the array has space for the new item. If not, the class must perform a reallocation. This involves allocating a larger array and copying all existing items into the new array before destroying the originals in the old array and releasing the old array. This is expensive, but the cost is amortized so that order of push_back() is amortized constant time.

How can it be constant time when copying all existing items will take time proportional to the number of existing items? The trick is that when push_back() triggers a reallocation, the new array is not a constant size increase of the existing array, but is proportional to the existing array (e.g. doubling in size). This approach means that although each reallocation is more expensive (due the increased number of exiting items), the allocations end up being required exponentially less often. The result works out to average (or amortized) constant time.

This is a great way to deal with allocations when we don’t know how many items we will need the vector to hold. But what if we do know how many items will be required? Suppose we know in advance that our vector will need to hold a thousand items. If vector initially allocates enough space for eight items and allocates an array twice as large as the existing one with each reallocation, we’ll need seven reallocations (and copies of all existing items) before we are finished adding our thousand items. This may be optimal if we have no idea how many items we’ll need to handle, but it is wasteful if we know in advance that we will need to hold a thousand items. We’d like a way to tell vector upfront that we need to hold a thousand items so it can create this space with one allocation and avoid needlessly copying items.

One way to do this to pre-fill our vector. If we are working with a vector of ints we can do something like this:

#include <iostream>
#include <vector>

using Ints = std::vector<int>;
// some how we know the upper bound of our storage requirement
const int vector_limit(1000);

int main()
{
    Ints v(vector_limit); // pre-fill a thousand ints

    std::cout << v.size() << std::endl;
    std::cout << v.capacity() << std::endl;
}
1000
some value >= 1000, likely 1000

The drawback to this approach is that we’ve not just changed the vector’s capacity, but its content as well. If we know we need to store a thousand ints, pre-filling the vector may not be a problem, but consider some other cases. Suppose we know only the upper bound of the number of items, but not the exact number and the item type has an expensive constructor. Or no default constructor. In these cases, pre-filling the vector is problematic.

What we need is a way to increase a vector’s capacity without changing it’s size.

Enter reserve(). reserve() takes a parameter that tells the vector class how many items we expect to hold. In our example we can call reserve() with the value one thousand before pushing back any items. This would trigger a single allocation and since we haven’t added any items to the vector, there are no existing items that need to be copied. Big win.

#include <iostream>
#include <vector>

using Ints = std::vector<int>;
// some how we know the upper bound of our storage requirement
const int vector_limit(1000);

int main()
{
    Ints v; // creates an empty vector

    v.reserve(vector_limit); // increase capacity only

    std::cout << v.size() << std::endl;
    std::cout << v.capacity() << std::endl;
}
0
some value >= 1000, likely 1000

One of the reasons that I wanted to discuss reserve() is because of a discussion I had with some very experienced and knowledgable C++ programmers. I was surprised to learn that they believed that reserve() is only an optimization-enabling hint to the library and that the library has the option of implementing it as a no-op. This is wrong on two counts. The standard does not allow reserve() to be a no-op (unless the passed values is already less than or equal to the vector’s current capacity).

Further, the standard guarantees that adding items to the vector up to the reserve() limit, will not only not cause a reallocation, but that iterators will not be invalidated. This is not just an optimization, but is an important guarantee because in general, we always assume that push_back() and insert() will invalidate iterators. (You can verify that these calls will not invalidate iterators for a specific call by checking the current capacity before the call.)

Because of this guarantee we can be confident that iterators (and references and pointers) are not invalidated as long as don’t increase the size of our vector beyond our reserve.

#include <cassert>
#include <iostream>
#include <vector>

using Ints = std::vector<int>;
// some how we know the upper bound of our storage requirement
const int vector_limit(1000);

int main()
{
    Ints v; // creates an empty vector

    v.reserve(vector_limit); // increase capacity only

    // add a single element and remember its address
    v.push_back(0);
    const int* start_of_allocated_array(&v[0]);

    // fill the vector to our limit
    for (int i(1); i < vector_limit; ++i) v.push_back(i);

    // verify no invalidation of iterators, pointers, or references
    assert(start_of_allocated_array == &v[0]);
}

What if we want to maintain stable access to items in the face of iterator invalidation (where we are adding items beyond the vector's capacity)? The trick is to use index values instead of iterators, pointers, or references. The Nth item in the vector will still be the Nth items after a reallocation.

The other reason I wanted to discuss reserve() is because of a nasty performance bug that some of my co-workers found within the last few days. Proper use of reserve() can be a nice performance win, but there is a gotcha scenario. In the bug, the code was calculating how many items needed to be added to the vector and then calling reserve() before adding them. This seems like a good use, until you realize that this code is being called in a loop. So what is happening is, each time through the loop we find that we need to add a few more items so we call reserve() which has the result of copying all existing items. What leads to this result is one of the characteristic of reserve() that isn't mandated by the standard, but it is usually the way that it is implemented. Let me explain.

As I said before, when a reallocation happens, the new size of the array is some proportion, usually double, of the old size of the array. The standard doesn't mandate any particular ratio. It also doesn't provide an upper limit on the capacity after a call to reserve(). An implementation is free to allocate an array double the value of the reserve() parameter. But that isn't what users would usually want or what most implementations provide. Usually reserve() will create a capacity exactly equal to the value passed. The passed value is a very good hint about the upper bound of the vector's size, and implementations take advantage of this hint.

Consider the implication of this on our performance bug. Without the call to reserve(), the push_back() in the loop would have added items with amortized constant time. But by calling reserve() in the loop, each reserve() resulted in copying every item in the vector every time through the loop and also pinning the capacity to exactly the reserve() value rather than a proportionally larger value, with disastrous performance consequences.

reserve() is a great tool for optimizing vector performance, but keep in mind the optimal use case for it. We want to call reserve() once when we can determine the upper bound on the vector's size requirement before we have added any values to the vector. There are many cases were we can't predict the size requirement upper bound, so we can't implement this optimal strategy and we may have to modify it. But calling reserve() several times with increasing estimates of the required capacity is not a strategy likely to yield success.

Please comment on Google Plus or reddit.

Ode to a Flat Set

In my previous post I discussed the most important changes in hardware since the STL was created. These changes are the increasing cost of malloc and the increasing importance of caching considerations.

I’ll group the standard containers into contiguous containers: vector, string, and deque, and node-based containers: list, *set, *map, and unordered*. The implications are that we want to favor contiguous containers over node-based containers both because they have fewer allocations per item and also because they are more cache friendly.

This isn’t earth shaking news. Alex Stepanov, the STL’s creator, has been quoted as saying, “Use vectors whenever you can. If you cannot use vectors, redesign your solution so that you can use vectors.”

Using vector, which has always been good advice, is now even better advice. It has always been true that for small values of N, vector beats containers with better order operations. Do we care about performance if N is small? If don’t have much data, why worry about which container might be faster? It is true that a small data set may mean that cost is insignificant in any one operation, but we may still be concerned about optimizing container performance . If our look-ups are in a small data set, but we are doing them in a loop, performance is still a consideration. With modern hardware the values for N where contiguous containers can beat node based containers can be larger than ever. How large? Follow Andrei Alexandrescu’s advice: measure.

If your entire vector fits in the cache, it will be hard to beat by a node-based container such as list, set, or map and perhaps even for unordered containers (with their constant-time accesses).

That is, if your vector is sorted.

In Item 23 of Effective STL, Scott Meyers discussed replacing associative containers with sorted vectors. There are trade-offs, of course. If you are doing inserts, erases, and lookups in an unpredictable pattern, then sorted vector looks less attractive. They also look less attractive if the container holds a very large number of items. Large numbers of items make cache misses likely even for vector and also favor the constant time access of hashes.

They look more attractive as the ratio of lookups to modifications gets larger or if you can segregate the container modification phase from the lookup phase. The ideal scenario for sorted vector is that you populate the vector, sort it once, then read it many times.

Lookups on sorted vector use lower_bound, upper_bound, or equal_range which have the same order (log) as associative container lookups. Although the order is the same, sorted vector will out perform tree-based containers because tree-based containers are dereferencing pointers and often getting cache misses while sorted vector is calculating offsets and getting cache hits.

The story for populating the container is more nuanced. An arbitrary insert into a sorted vector will be order N because vector will need to move all the elements following the insertion point. The log order of associative containers is better. On the other hand, the associative container is going to allocate a node. Vector can move a lot of elements in the time it takes to allocated a node.

Of course the interface for vector isn’t the same as that of an associative container. In order for lookups to be log order, the vector must be sorted and it must stay sorted (or be re-sorted) in the face of modifications. Insertions will need to be preceded by calls to lower_bound to find the insertion point. A single lapse may create a hard to find bug.

Enter flat_set.

The Boost Container library has a family of flat_* containers that have associative container interfaces and semantics, but are implemented as sorted vectors.

In addition to faster lookup, the flat_* containers have much faster iteration, less memory overhead, fewer allocations, and improved cache performance.

However, as with all things, there are trade-offs. Unlike items in an associative container which are allocated into their own nodes and are never moved or copied (and thus never throw while being moved or copied), items in a flat_* container must be movable or copyable and may throw when being moved or copied during insertion or erasure. Further, insertion and erasure invalidates iterators and may be slower (particularly for non-movable types).

In short, the smaller your container and the closer your usage is to read-only, the better flat_* containers look as replacements for associative containers.

In a future post I’ll discuss an alternative to consider when the sorted vector’s limitations make it unattractive.

Please comment on Google Plus or reddit.

STL is Dated

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.

Please comment on Google Plus or reddit.