in reply to Data structures in Perl. A C programmer's perspective.
Be warned that with modern CPUs, the conventional wisdom that linked lists should be preferred to vectors when performing many insertions and deletions in the middle of the list is almost always wrong. From bulldozer blog:
The vector still kills the linked list in this test. And that’s all because vector stores its data in a contiguous block of memory. The vector has so much better performance (and as you increase the size of your data structure, the difference in performance becomes much more pronounced) because it accesses memory linearly.
The memory is so slow when you access it randomly, that the penalty for cache misses almost always dominates your CPU usage time. If you care at all about performance, the main memory should be considered a sequential-access device. You have been lied to all your life; RAM is not a random-access memory device!
This has been true in the last few years and in the future it will only become more so, barring any true revolutions in hardware technology (think Ansible!) or a fundamental change in computing model (think abandoning the von Neumann model,) of which there is no sign yet (and it would take decades, even if we had an alternative model.) This particular performance killer will get worse and worse with time.
References
- bulldozer blog: C++ vector vs list performance
- Stack Overflow question on C++ list vs vector
- blog: C++ vector vs list performance (broken link)
- Number crunching: why you should never use linked-list in your code again
- Bjarne Stroustrup: Why you should avoid Linked Lists (3:30-5:00) (youtube: from GoingNative 2012 Keynote)
- Herb Sutter talk (youtube, around 48:40 mark)
References Added Later
- What Every Programmer Should Know About Memory (pdf) by Ulrich Drepper
- The 10**21 Problem (Part 3) (see opening quote from Bjarne Stroustrup and the Prefetching section)
- The 10**21 Problem (Part 2) (see "Modern Memory Architecture" section)
- Re^3: [OT:] Is this Curriculum right? (my provocative response in a thread by the inimitable karlgoethebier) (Nov 2021)
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Data structures in Perl. A C programmer's perspective.
by BrowserUk (Patriarch) on Sep 07, 2013 at 00:33 UTC | |
Re^2: Data structures in Perl. A C programmer's perspective.
by bulk88 (Priest) on Sep 07, 2013 at 06:35 UTC | |
Re^2: Data structures in Perl. A C programmer's perspective.
by code-ninja (Scribe) on Sep 07, 2013 at 03:47 UTC | |
by davido (Cardinal) on Sep 07, 2013 at 04:56 UTC | |
by eyepopslikeamosquito (Archbishop) on Sep 07, 2013 at 04:13 UTC |