C++ Algorithmic Complexity, Data Locality, Parallelism, Compiler Optimizations, & Some Concurrency

on YouTube ↗48m

" summary

Concrete claims, measurements, and fixes: traversing a 4096×4096 double matrix rowwise takes row: 21 ms vs column: 912 ms, measured with valgrind; L1=32 KB L2=256 KB L3=8 MB and cache line 64 B explain it; D1 miss rates fall from 12.5% to 2.1% when access is cache-friendly. Blocking (32×32) or copying a submatrix removes conflict misses, false sharing creates ping‑pong between threads, and practical advice is: prefer contiguous containers (vector/flat_map), eliminate pointer/virtual chasing on hot paths, use PGO and benchmark.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 0:30Hardware
3. 3:00Caches
4. 3:53My Machine
5. 4:50Cores
6. 5:18Latency
7. 6:13Cache Models
8. 8:23Cache Lines
9. 12:59Cache Misses
10. 15:20Cache Miss Example
11. 21:05False Sharing
12. 24:50Cache Line Example
13. 26:37Main Cache
14. 27:18Memory
15. 28:01Summary
16. 28:54ObjectOriented Example
17. 36:21Cash oblivious
18. 37:36Guidelines for code
19. 39:28Benchmarking

" related talks

• 28mCommunication Avoiding Algorithms for Linear Algebra and BeyondJim Demmel · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 00m“Want fast C++? Know your hardware!"Timur Doumler · CppCon 2016
• 01h 04mDesign for PerformanceFedor Pikus · CppCon 2018
• 58mC++ Performance and OptimisationHubert Matthews · NDC Oslo 2017
• 01h 00mMoving Faster: Everyday efficiency in modern C++Alan Talbot · CppCon 2018
• 01h 02mSqueezing the Hardware to Make Performance JuiceSasha Goldshtein · NDC London 2017
• 01h 00mCache Friendly C++Jonathan Müller · Meeting C++ 2025
• 01h 04mCompile-time sparse matricesDaniel Withopf · Meeting C++ 2023