Designing Fast and Efficient List-like Data Structures
summary
Claims a redesign of list-like containers that packs elements into page-based chunks with inline or pointer slots, trading per-node pointers for contiguous slots and cache-line friendliness. Benchmarks and profiling report 2+ times faster than STL equivalents and a big reduction in cache misses. Implements fixed-size stacks, growable page queues, and a task queue prototype used in real scheduling; library is experimental, not yet public but planned for release around November–December.
AI-written summary · about
chapters (10)
- 0:00Efficient list-like structures
- 1:51C++ standard containers
- 6:49CPU cache and memory access
- 9:14Cache locality in linked lists
- 11:00Fixed-size stack for small objects
- 13:11Page container for queues/stacks
- 16:03Dynamic queue with page lists
- 18:29Benchmarking cache-aware structures
- 20:19Project status and plans
- 21:03Q&A
related talks
45mBeyond Lists: High Performance Data Structures
48mC++ Data Structures That Make Video Games Go Round
06mUsing STL containers efficiently
01h 02m“Lightweight Object Persistence With Relocatable Heaps in Modern C++"
48mA Helicopter Tour of Purely Functional Data Structures
55mIntroduction to C++ Containers - Know Your Data Structures
01h 13mC++ Memory Model Meets High-Update-Rate Data Structures
01h 04mBack to Basics: Standard Library Containers in Cpp