std::list vs std::vector iteration

Question

It is said that iterating through a vector (as in reading all it's element) is faster than iterating through a list, because of optimized cache.

Is there any ressource on the web that would quantify how much it impacts the performances ?

Also, would it be better to use a custom linked list, whom elements would be prealocated so that they are consecutive in memory?

The idea behind that is that I want to store elements in a certain order that won't change. I still need to be able to insert some at run time in the midle quickly, but most of them will still be consecutive, because the order won't change.

Does the fact that the elements are consecutive have an impact in the cache, or because I'll still call list_element->next instead of ++list_element it does not improve anything ?

Answer 1

The main difference between vector and lists is that in vector elements are constructed subsequently inside a preallocated buffer, while in a list elements are constructed one by one. As a consequence, elements in a vector are granted to occupy a contiguous memory space, while list elements (unless some specific situations, like a custom allocator working that way) aren't granted to be so, and can be "sparse" around the memory.

Now, since the processor operates on a cache (that can be up to 1000 times faster than the main RAM) that remaps entire pages of the main memory, if elements are consecutive it is higly probable that they fits a same memory page and hence are moved all together in the cache when iteration begins. While proceeding, everything happens in the cache without further moving of data or further access to the slower RAM.

With list-s, since elements are sparse everywhere, "going to the next" means refer to an address that may not be in the same memory page of its previous, and hence, the cache needs to be updated upon every iteration step, accessing the slower RAM on each iteration.

The performance difference greatly depends on the processor and on the type of memory used for both the main RAM and the cache, and on the way the std::allocator (and ultimately operator new and malloc) are implemented, so a general number is impossible to be given. (Note: great difference means bad RAM respect to to the cache, but may also means bad implementation on list-s)

Answer 2

The efficiency gains from cache coherency due to compact representation of data structures can be rather dramatic. In the case of vectors compared to lists, compact representation can be better not just for read but even for insertion (shifting in vectors) of elements up to the order of 500K elements for some particular architecture as demonstrated in Figure 3 of this article by Bjarne Stroustrup:

http://www2.research.att.com/~bs/Computer-Jan12.pdf

(Publisher site: http://www.computer.org/portal/web/csdl/doi/10.1109/MC.2011.353)

I think that if this is a critical factor for your program, you should profile it on your architecture.

Answer 3

Not sure if I can explain it right but here's my view(i'm thinking along the lines of translated machine instruction below:),

Vector iterator(contiguous memory): When you increment a vector iterator, the iterator value is simply added the size of the object(known at compile time) to point to the next object. In most CPUs this is anything from one to three instructions at most.

List iterator(linked list http://www.sgi.com/tech/stl/List.html): When you increment a list iterator(the pointed object), the location of the forward link is located by adding some number to the base of the object pointed and then loaded up as the new value of the iterator. There is more than one memory access for this and is slower than the vector iteration operation.