Relative Performance of Std::Vector VS. Std::List VS. Std::Slist

Relative performance of std::vector vs. std::list vs. std::slist?

As usual the best answer to performance questions is to profile both implementations for your use case and see which is faster.

In general if you have insertions into the data-structure (other than at the end) then vector may be slower, otherwise in most cases vector is expected to perform better than list if only for data locality issues, this means that if two elements that are adjacent in the data-set are adjacent in memory then the next element will already be in the processor's cache and will not have to page fault the memory into the cache.

Also keep in mind that the space overhead for a vector is constant (3 pointers) while the space overhead for a list is paid for each element, this also reduces the number of full elements (data plus overhead) that can reside in the cache at any one time.

Vector vs list according to Stroustrup

The most important motivation for preferring std::list over std::vector is the validity of iterators, not performance. If at the time you're inserting or erasing, you have other iterators into the container, then you probably need std::list, since it insertion doesn't invalidate any iterators, and erasure only invalidates iterators to the element being erased. About the only time std::list will win on performance is when copy and assignment are extremely expensive, and in such cases, it's often a better choice to modify the contained class to reduce the cost of copy and assignment, rather than switching to std::list.

Substituting `std::vector` with more appropriate class

Could you suggest the best container/doubly-linked list for my scope?

If you access elements by index, a linked list is not a good solution: you have to traverse the list from the beginning, so it is an O(N) operation. And for this reason, std::list and std::forward_list have no such access in their interface.

Is it possible to seamlessly substitute std::vector with any other standard container?

Not with an std::list, since it has no access by index. std::deque could be suitable, but only if you do not rely on the underlying data being in one continuous block (I assume you don't, since you are asking about linked lists)

Are there special issues I have to pay attention to?

As always with performance, you should first be sure whether you have a problem or not. If you have a performance issue with std::vector, then try something else, and measure the difference in performance in a realistic running scenario. The performance characteristics of different containers can be quite counter intuitive, so measuring is specially important here.

Related links: std::vector vs. std::list vs. std::deque comparison. Bjarne Stroustrup's Going Native 2012 keynote speech.

Benefit of slist over vector?

For starters, slist is non-standard.

For your choice, a linked list will be slower than a vector, count on it. There are two reasons contributing to this:

1. First and foremost, cache locality; vectors store their elements linearly in the RAM which facilitates caching and pre-fetching.
2. Secondly, appending to a linked list involves dynamic allocations which add a large overhead. By contrast, vectors most of the time do not need to allocate memory.

However, a std::deque will probably be even faster. In-depth performance analysis has shown that, despite bias to the contrary, std::deque is almost always superior to std::vector in performance (if no random access is needed), due to its improved (chunked) memory allocation strategy.

Why is it so slow iterating over a big std::list?

Lists have terrible (nonexistent) cache locality. Every node is a new memory allocation, and may be anywhere. So every time you follow a pointer from one node to the next, you jump to a new, unrelated, place in memory. And yes, that hurts performance quite a bit. A cache miss may be two orders of magnitudes slower than a cache hit. In a vector or deque, pretty much every access will be a cache hit. A vector is one single contiguous block of memory, so iterating over that is as fast as you're going to get. A deque is several smaller blocks of memory, so it introduces the occasional cache miss, but they'll still be rare, and iteration will still be very fast as you're getting mostly cache hits.

A list will be almost all cache misses. And performance will suck.

In practice, a linked list is hardly ever the right choice from a performance point of view.

Edit:
As a comment pointed out, another problem with lists is data dependencies. A modern CPU likes to overlap operations. But it can't do that if the next instruction depends on the result of this one.

If you're iterating over a vector, that's no problem. You can compute the next address to read on the fly, without ever having to check in memory. If you're reading at address x now, then the next element will be located at address x + sizeof(T) where T is the element type. So there are no dependencies there, and the CPU can start loading the next element, or the one after it, immediately, while still processing an earlier element. That way, the data will be ready for us when we need it, and this further helps mask the cost of accessing data in RAM.

In a list, we need to follow a pointer from node i to node i+1, and until i+1 has been loaded, we don't even know where to look for i+2. We have a data dependency, so the CPU is forced to read nodes one at a time, and it can't start reading future nodes ahead of time, because it doesn't yet know where they are.

If a list hadn't been all cache misses, this wouldn't have been a big problem, but since we're getting a lot of cache misses, these delays are costly.

vector vs. list in STL

Situations where you want to insert a lot of items into anywhere but the end of a sequence repeatedly.

Check out the complexity guarantees for each different type of container:

What are the complexity guarantees of the standard containers?

---

Related Topics