How Much Linear Memory Access Is Enough?

The article delves into the crucial relationship between memory layout, access patterns, and high-performance computation, aiming to experimentally pinpoint the minimum effective block size for linear memory access to maximize throughput. It acknowledges that the intuitive preference for large, contiguous blocks might yield diminishing returns and sets out to find the sweet spot.

• Research Question: How large do individual linear memory blocks need to be to amortize the overhead of jumping between them, thereby achieving peak performance?
• Experimental Design: A specialized benchmarking setup was crafted to isolate and control the effects of the CPU's complex memory hierarchy. It utilized a span<span<float const> const> structure to represent data as 'vectors of blocks'.
• Cache Mitigation: To ensure realistic 'cold cache' measurements, the setup randomized block order, placed blocks at random positions within a 4 GB backing memory, and explicitly clobbered caches before each test run.
• Workloads Examined: Three distinct kernels were used:
  • scalar_stats: A lightweight scalar computation (e.g., running statistics), serving as a baseline.
  • simd_sum: A highly optimized SIMD (AVX2/NEON) sum, representing maximum memory throughput.
  • heavy_sin: A CPU-bound sin calculation, simulating heavy, slower, computationally intensive tasks.
• Key Findings (Cold Cache):
  • simd_sum (most memory-intensive): Requires approximately 1 MB blocks for peak throughput.
  • scalar_stats (moderate): Optimal performance is achieved with around 128 kB blocks.
  • heavy_sin (CPU-intensive): Achieves near-peak performance even with very small 4 kB blocks.
• Warm Cache Effects: In scenarios where data partially remains in cache ('repeated' runs), smaller working sets reach peak performance with even smaller block sizes, demonstrating the impact of cache reuse.
• Cross-Platform Consistency: The general trends observed were consistent between a Ryzen 9 7950X3D and a Macbook Air M4, suggesting broad applicability of the findings.

Ultimately, the author concludes that while there's no singular 'universal answer,' block sizes exceeding 1 MB are generally overkill for most linear, per-block computations. For many practical workloads operating above 1 cycle per byte, 128 kB blocks prove more than sufficient. This work highlights the nuanced trade-offs in data structure design, demonstrating that while full contiguity has benefits, chunked data structures can still achieve peak throughput with surprisingly modest block sizes.