Missing Optimizations on Node-based Containers
summary
Rewrites of std::list methods trade pointer-chasing for independent memory loads: run forward and backward iterators per loop, buffer reads then commit writes (double-swap write buffering) and add skip-links for multi-way traversal. Benchmarks over hundreds of thousands of 64-byte nodes show 1.84× speedup on random layouts (only ~5% on sequential), the double-swap approaches 2×, and a 3-way skip variant yields 2.56× with 3-way skipping. Compiler restrict hints help inconsistently; results are CPU-level, language-agnostic optimizations.
AI-written summary · about
chapters (9)
- 0:00Start
- 3:02Instruction-Level Parallelism
- 4:10Data dependencies in std-list-reverse
- 6:36Why does it fall short of 2x improvement?
- 7:00Optimizing swaps
- 7:58Benchmarks
- 8:15Other examples of unnecessary RAW dependencies
- 9:14Does the restrict keyword help?
- 10:47Loopidly linked lists
related talks
58mRefresher on Containers, Algorithms and Performance
01h 00mOLD VERSION: The Fine Details Behind C++ Containers And Algorithms
01h 00mMoving Faster: Everyday efficiency in modern C++
01h 00mThe 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
01h 01mRecipes for Reducing Allocations by C++ Containers
01h 17mWhat Do You Mean by "Cache Friendly"?
44mC++ Performance and Optimisation