Senior LevelData Structures & Algorithms
How do Cache-Efficient Algorithms and Memory Hierarchy affect real-world performance?
❓ Interview Prompt: Explain cache lines, spatial/temporal locality, cache-oblivious algorithms, and why array-based data structures outperform pointer-based ones in practice.
Memory Hierarchy (registers → L1 → L2 → L3 → RAM → disk) creates latency gaps of 4-5 orders of magnitude between cache hits and disk I/O.
Cache Efficiency Principles:
•
Spatial Locality: Access nearby memory addresses → full cache line (64 bytes) loaded, benefitting sequential accesses.
•
Temporal Locality: Reuse recently accessed data before it evicts from cache.
Why Arrays Beat Linked Lists in Practice:
•
Array elements are contiguous → one cache line prefetch loads multiple elements.
•
Linked list nodes are scattered → each pointer dereference is a potential cache miss.
Cache-Oblivious Algorithms:
•
Optimal for all cache line sizes without explicit tuning (e.g., cache-oblivious matrix multiply, van Emde Boas layout).
•
Merge Sort and FFT are nearly cache-oblivious.
Code Implementation Example
typescript
// Cache-friendly matrix multiply (i-k-j order for row-major access)
function matMulCacheFriendly(A: number[][], B: number[][], C: number[][]): void {
const n = A.length;
for (let i = 0; i < n; i++) {
for (let k = 0; k < n; k++) { // reorder: k outer, j inner
const aik = A[i][k]; // A[i][k] cached once per k-loop
for (let j = 0; j < n; j++) {
C[i][j] += aik * B[k][j]; // B[k][j] sequential — cache friendly!
}
}
}
}
// Naive i-j-k: A[i][k] causes random row access = cache thrashing
// i-k-j: B's row is accessed sequentially = much better cache utilisation💡Cache-friendly matrix multiplication reordering loops for sequential memory access.
🎯 Interview Key Takeaway
Cache efficiency often matters more than algorithmic complexity. An O(N²) cache-friendly algorithm can outperform O(N log N) cache-thrashing code for real-world N.
#DSA#Cache Efficiency#Memory Hierarchy#Performance#Senior
Back to all Data Structures & Algorithms Questions→