Algorithm Performance in the New Machine Age
summary
Benchmarking with JMH and perf counters shows linked lists blow CPU caches as size grows (tests at 1K, 7K, 63K, 511K). L1 ≈ 1 ns, L2 ≈ 4 ns, L3 ≈ 60 ns, main memory >100 ns so cache misses dominate (roughly a 300x main memory penalty). A primitive array traversal stays linear and yields ~8 ns vs 28 ns for a cache-unfriendly allocation pattern. Recommendation: reduce memory footprint and improve data locality or copy dynamic maps into immutable, contiguous layouts for predictable speedups.
AI-written summary · about
chapters (19)
- 0:00Intro
- 1:14Your Father's Complexity
- 6:01What is Computational Complexity?
- 10:32Who Is Your Father? Another Candidate
- 12:14What Josh Told Me...
- 14:02Which List Implementation?
- 17:55pre-1980
- 21:06The Golden Age of Complexity Analysis
- 23:35Keeping the Cores Running Today
- 24:14The Memory Hierarchy
- 29:04Stride Prefetching
- 32:23How Does Caching Play With Complexity? First issue: cache capacity
- 36:28What's Going On?
- 38:00Primitive Array
- 39:54Populating LinkedList "Naturally"
- 43:04Poor Unloved Linkedlist...
- 44:25HashMap collision
- 47:15Improving Data Locality
- 49:26Conclusion, of sorts...
related talks
40mHidden GEMMs: How Optimized Math Libraries Work
15m3L-Cache: Low Overhead and Precise Learning-based Eviction Policy for Caches
52mComputing Performance 2022: What's on the Horizon
56mReduce, Reuse, Recycle: Is this Mantra under attack with Proliferation of Machine(…)
44mJava for AI
18mLet the machines optimize the machines
33mOptimizing Java on the EU processor platform
20mAccelerating Model Loading in LLM Inference by Programmable Page Cache