Refresher on Containers, Algorithms and Performance
summary
Benchmarks on x86_64 (8 cores) using gcc 10, libstdc++, Google Benchmark and valgrind cachegrind show concrete wins and tradeoffs: vector beats list for accumulate because continuous storage yields far fewer cache misses (about one miss every two accesses on list for 100k items), inserting at front makes vector cost explode but remains faster until ~800 elements, post-fill + std::reverse or reserve helps, parallel execution sometimes hurts, and flat containers (boost::container::flat_set / absl / EA fixed containers) plus id mapping eliminate string comparisons and give the best query and storage tradeoffs.
AI-written summary · about
chapters (18)
- 0:00Intro
- 1:29Performance of containers
- 2:02Time complexity and big O notation
- 5:25Big O classes of typical operations
- 7:46Experiments. Basic setup
- 9:54Memory access. Organization of std::list
- 11:14Memory access. Caches
- 14:16Code complexity. Iron Law of Performance
- 15:39Code complexity. Generated code
- 21:15Insertion into front. Parallel algorithm
- 30:22Sorted sequence. Improvements for std::vector
- 37:40Sorted sequence. Deferred removal
- 39:07Sorted sequence. Deletion optimization trade-off
- 41:17Unordered containers. Insertion
- 44:43Container combination. Trivial approach
- 45:16Container combination. Avoiding indirection
- 46:24Container combination. Avoiding string comparison
- 48:24Container combination. Sorted sequence
related talks
01h 00mMoving Faster: Everyday efficiency in modern C++
01h 00mOLD VERSION: The Fine Details Behind C++ Containers And Algorithms
01h 31mNew (& Old) C++ Standard Library Containers - How to Choose the Right Container in C++26 and Beyond
13mMissing Optimizations on Node-based Containers
01h 00mThe Fine Details Behind C++ Containers And Algorithms
57mThis Videogame Programmer Used the STL and You Will Never Guess What Happened Next
01h 30mTuning C++: Benchmarks, and CPUs, and Compilers! Oh My!
01h 06m“Improving Performance Through Compiler Switches..."