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“.