Cache-friendly Design in Robot Path Planning with C++
Talkat CppCon 2023 · on Monday, 2023-10-02· at 16:45· Maple 3/4/5, 6700 North Gaylord Rockies Boulevard·
summary
Implements Dijkstra/A style point-to-point planning in C++ and measures real cache behavior with cachegrind and perf/vtune, replacing std::map/multimap with unordered_map then packed std::vector-of-vectors and finally a single edge array exposed via subranges. Uses reserve and spatially sorts vertex IDs so adjacency accesses become contiguous. Reports instruction count roughly halved, L1 miss rate dropping by about 60%*, and wall‑clock search time cut substantially; code and benchmarks live on the provided GitHub.
AI-written summary · about
chapters (19)
- 0:00Cache-friendly robot path planning
- 5:53Motivating problem
- 10:09Shortest path search algorithms
- 14:23Implementing D* in C++
- 21:23First implementation with std::map and std::multimap
- 28:07Measuring cache performance
- 32:42Cache-friendly design principles
- 35:11Problems with std::map and std::multimap
- 37:20Switching to unordered containers
- 41:53Adjacency lists with std::vector
- 44:41Memory layout with subranges
- 47:52Performance improvements
- 50:23Q&A: Subranges and locality
- 51:26Q&A: Boost Graph vs STL
- 52:08Q&A: Detecting cache misses
- 54:19Q&A: Multiple pathfinding agents
- 57:37Q&A: Early stopping in D*
- 59:01Q&A: Multithreading and cache
- 1:00:24Q&A: Dynamic graphs and memory
related talks
01h 00mCache Friendly C++
55mWriting Cache-Friendly C++
58mC++ Performance and Optimisation
01h 00mMoving Faster: Everyday efficiency in modern C++
01h 01mWhat do you mean by "Cache Friendly"?
51m“Cache Optimized Hash Tables”
01h 01mFaster, Easier, Simpler Vectors
01h 01mRefresher on Containers, Algorithms and Performance in C++