Cache-Efficient Algorithms

Discrete Math · Axiom Academy

REAL WORLD Cache-Efficient Algorithms Discover why "theoretically optimal" algorithms can fail in practice, and how understanding memory hierarchy transforms performance on modern hardware. You're working at a tech company, and your team is processing large datasets. Two algorithms both traverse a 2D matrix: Algorithm A (Row-major): Processes row by row Algorithm B (Column-major): Processes column by column Both algorithms have identical time complexity: O(n²) . According to theoretical analysis, they should perform equally. But when you run them on a 10,000 × 10,000 matrix... Why does Algorithm B run 20 times slower? Both algorithms do the same number of operations. Both have O(n²) complexity. What could cause such a dramatic difference? Traditional complexity analysis assumes all memory operations cost the same. But modern computers have a memory hierarchy where access speeds vary dramatically: Key Insight: Accessing RAM is 100× slower than accessing L1 cache. This means cache hits vs. cache misses can make or break performance, even when the number of operations stays the same! When the CPU loads data from memory, it doesn't fetch just one element—it loads an entire cache line (typically 64 bytes). This is like grabbing a whole box of items instead of one at a time. The Code: Identical Operations, Different Patterns Let's examine both algorithms. They perform the same operations, but in different orders:

This is the written version of the interactive lesson above. See the full Discrete Math course.