What data access pattern is as slow as possible?
The author benchmarks memory access patterns and finds that sequential access with a stride equal to the CPU page size (4K) can be as slow as random access due to TLB misses, negating the benefit of sequential memory access.
Background
- The post explores which in-memory data structure access pattern produces the absolute worst performance, benchmarking hash tables, B-trees, and other structures.
- Key context: modern CPUs rely on cache prefetching and branch prediction; "worst-case" access patterns deliberately defeat both — e.g., random pointer chasing in a large hash table causes a cache miss on nearly every access.
- The author compares sequential scans (fastest), random access within arrays, and linked-list-style pointer chasing, showing that random walks through a hash table with chaining are consistently the slowest.
- Why it matters: understanding the worst case helps developers reason about real-world performance cliffs, especially in databases, search engines, and real-time systems where latency tail behavior matters.