Efficiency with Algorithms, Performance with Data Structures
summary
Claim: efficiency comes from doing less work (algorithms) and performance from making memory accesses fast (data structures). Evidence: CPUs spend ~50–75% of time waiting for memory, L1 vs main memory is ~100× latency, cache lines ~64 bytes, switching to reserve before push_back and to contiguous storage yields large wins; separate-node lists and bucketed unordered_map cause cache misses, while open‑addressed hash tables or plain vector-backed queues give 5–10× or greater speedups in practice.
AI-written summary · about
chapters (14)
- 0:00Start
- 10:47HIGH LEVEL THESIS
- 11:26EFFICIENCY: HOW MUCH WORK IS REQUIRED BY A TASK
- 13:32PERFORMANCE HOW QUICKLY A PROGRAM DOES ITS WORK
- 17:26ALL COMES BACK TO WATTS
- 19:20SUB-STRING SEARCHING
- 28:35DO LESS WORK BY NOT WASTING EFFORT
- 35:27MODERN CPUS ARE TOO FAST
- 37:26CPUS HAVE A HIERARCHICAL CACHE SYSTEM
- 41:57STACKSY QUEUES? MAPSY
- 47:01STD::UNORDERED MAP
- 49:06A GOOD HASH TABLE DESIGN
- 51:34DATA STRUCTURES AND ALGORITHMS
- 54:57CONCLUSION
related talks
01h 00mIntroduction to Hardware Efficiency in Cpp
01h 01mHigh performance data structures in boost
01h 09mComputer Architecture, C++, and High Performance
01h 06mUtilize your CPU power
56mC++ Relocation - How to Achieve Blazing Fast Save and Restore and More!
05mWhen every Microseconds counts: Lessons learned about performance
58mOptimizing Binary Search
48m[a bit noisy] Optimizing Generic Algorithms