The Biggest Misconception of Computer Science
summary
Argues that asymptotic Big‑O misleads because real performance is dominated by hardware: cache lines, latency, SIMD and branch predictors. Shows Dijkstra’s textbook O(E log V) but reminds about heap and memory costs, explains vector amortized reallocations and shows multiplication/shift beats division, measures a parallel reduce that is slower on 10 million elements due to cache and SIMD, and a histogram with 64 bins that is ~4x faster using a cache‑friendly vector versus unordered_map and discusses AVX/AVX‑512 tradeoffs.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 3:20Big O limitations
- 13:38Amortized time complexity
- 22:13CPU hardware basics
- 27:40CPU latency tricks
- 33:24CPU caches role
- 35:52Threading cache misses
- 38:40Cache-friendly vs Big O
- 42:15Theory versus hardware
related talks
59m“Is Parallel Programming still hard? PART 1 of 2”
43mWhat Every Programmer Should Know about How CPUs Work
48m“Is Parallel Programming still hard? PART 2 of 2”
50mFrom Concurrent to Parallel
51mThe Need for Async
01h 11mProgramming language memory models: Problems, solutions, and directions
48mConcurrency: It’s Harder (and Easier) Than You Think
50mThe Hidden Art of Thread-Safe Programming: Exploring java.util.con...