What do you mean by "Cache Friendly"?
summary
A linked‑list timer implementation hits 75% CPU in one function when stressed with ~20–25k live timers because pointer chasing forces cache misses; a cache simulation shows roughly 70% L1 misses. Replacing pointers with a contiguous vector increases instructions but runs much faster due to prefetching; a binary search cuts misses but reveals speculative‑execution effects; a heap (std::priority_queue) is ~2× faster, and a cache‑aware b‑heap reduces L1 misses from ~120M to ~84M. Key rules: keep working set small and contiguous.
AI-written summary · about
chapters (20)
- 0:00Introduction
- 0:31Identifying the performance issue
- 2:52Analyzing the timer algorithm
- 4:26Cache-oblivious data structures
- 5:46Mental model of cache behavior
- 10:06Advanced considerations
- 12:56Testing with Valgrind
- 14:54Profiling methodology
- 17:20Profiling results
- 20:22Interpreting cache misses
- 25:01Linear array implementation
- 26:21Using Perf for system analysis
- 32:39Counter-intuitive performance findings
- 34:05Binary search implementation
- 38:40Evaluating std::multimap
- 40:45Data scale considerations
- 45:56Heap data structure
- 50:36Priority queue implementation
- 55:00B-heap optimization
- 59:28Conclusion
related talks
01h 00mCache Friendly C++
01h 06mCPU Cache Effects
55mWriting Cache-Friendly C++
01h 00mMoving Faster: Everyday efficiency in modern C++
58mOptimization Tips - Mo' Hustle Mo' Problems
58mC++ Performance and Optimisation
01h 03mInstruction Level Parallelism and Software Performance
01h 05mPerformance Optimization in Software Development - Being Friendly to Your Hardware