Vectors And Lists
In C++ programming, everybody knows that when an application requires lots of dynamic insertions into (and deletions from) an ordered sequence of elements, a linked list is much faster than a vector. Err, is it?
Behold the following performance graph that Bjarne Stroustrup presented during his keynote speech at “Going Native 2012“:
So, “WTF is up wit dat?”, you ask. Here’s what’s up wit dat:
The CPU load happens to be dominated by the time to traverse to the insertion/deletion point – and KNOT by the time to actually insert/delete the element. So, you still yell “WTF!“.
The answer to the seeming paradox is “compactness plus hardware cache“. If you’re not as stubborn and full of yourself as BD00, this answer “may” squelch the stale, flat-earth mindset that is still crying foul in your brain.
Since modern CPUs with big megabyte caches are faster at moving a contiguous block of memory than traversing a chain of links that reside outside of on-chip cache and in main memory, the results that Bjarne observed during his test should start to make sense, no?
To drive his point home, Mr. Stroustrup provided this vector-list example:
In addition to consuming more memory overhead, the likelihood that all the list’s memory “pieces” reside in on-chip cache is low compared to the contiguous memory required by the vector. Thus, each link jump requires access to slooow, off-chip, main memory.
The funny thing is that recently, and I mean really recently, I had to choose between a list and a vector in order to implement a time ordered list of up to 5000 objects. Out of curiosity, I wrote a quick and dirty little test program to help me decide which to use and I got the same result as Bjarne. Even with the result I measured, I still chose the list over the vector!
Of course, because of my entrenched belief that a list is better than a vector for insertion/deletion heavy situations, I rationalized my unassailable choice by assuming that I somehow screwed up the test program. And since I was pressed for time (so, what else is new?), I plowed ahead and coded up the list in my app. D’oh!
Update 4/21/13: Here’s a short video of Bjarne himself waxing eloquent on this unintuitive conclusion: “linked list avoidance“.
Leave a comment
Why am I here?
WTF?
Meh!
D'oh!
My BTC Address
Bulldozer00's Blog 
I love seeing such performance measurements. Theory doesn’t always translate to machines quite the way you would expect. The CPU caches make such a huge impact. It does matter quite a bit what type of data you’re storing. Small flat data objects can be copied quickly, but with larger objects the copy may be slow (of course then you can just use pointers). Though honestly, I rarely use a list for anything. I use vector or map most of the time and otherwise resort to custom data structures (often built on top of vector or map).
Me too. I hate when people say “don’t code it that way, XXX is obviously faster” – except when it’s me doing the saying 🙂
I have carefully listeed to Mr. Stoustrups argument for using vectors rather than lists. He states that one should always use vectors due to performance and that there effectively is no gain using lists at all.
The basic reason (and also the premis) is that the memory cache will assist a vector to outperform a list. If the system has no (effective) chache this may not be the case.
Mr. Stoustrup argues therefore that programmers should always use vectors when a list is needed.
Why is it so that there is a specialised list class template?
If the compiler ‘knows’ that an effective cache is available, then it sould replace any list instance with a vector instance and by that way give equal performance to lists and vectors.
This approach will relinquish the programmer from deciding on vector or list.
This sort of abstraction may provide less confision if some algorithm is easier understood when using lists instead of vectors. Eventually could one of list or vector render redundant.
Thanks for your comment Carsten. I don’t think Bjarne or any other C++ guru has ever said “always” use a vector over a list. They say “prefer” vector first, measure if unsure.