What Do You Mean by "Cache Friendly"?
summary
A 20,000-entry intrusive linked list (≈40 bytes per timer) causes ~70% L1 misses and pegs a control daemon; valgrind/cachegrind and perf pinpoint the while-loop pointer chasing as the hotspot. Replacing with a contiguous vector plus binary search roughly halves time, plain linear insert is faster up to ~200 elements, and a heap (split payload + index) cuts cycles further (measured up to ~4× faster). Tools: valgrind/cachegrind, perf and flame graphs; experiment with B‑heap block layout for cache-line locality.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 5:53Cache oblivious structures
- 12:07Timer performance with cache simulation
- 27:14Cache profiling tools
- 36:13Rewriting timers with linear arrays
- 42:43Binary vs linear search in timers
- 44:27Evaluating std::map for timers
- 50:26Heap data structures for timers
- 59:51Optimizing heap with mini heaps
- 1:07:14Timer implementations compared
- 1:14:17Cache-friendly code rules
- 1:16:17Q&A
related talks
13mMissing Optimizations on Node-based Containers
01h 00mMoving Faster: Everyday efficiency in modern C++
01h 30mTuning C++: Benchmarks, and CPUs, and Compilers! Oh My!
57mThis Videogame Programmer Used the STL and You Will Never Guess What Happened Next
55mAbusing Your Memory Model for Fun and Profit
05mMaximising Throughput & Minimising Latency in High-Performance C++ Code
44mC++ Performance and Optimisation
16mMind the Gap (Between Your Code and Your Toolchain)