How does benchmarking measure data locality?

Benchmarking measures data locality by evaluating how efficiently a system accesses and utilizes data stored in memory hierarchies (e.g., cache, RAM, disk). Data locality refers to how often data needed by a program is located in fast, nearby storage layers versus slower, distant ones. Benchmarks quantify this by tracking metrics like cache hit rates, memory access latency, or data reuse patterns. For example, a benchmark might run a workload and measure how frequently the CPU retrieves data from the L1 cache versus fetching it from main memory. High cache hit rates indicate strong temporal or spatial locality, meaning the system effectively keeps frequently used data close to the processor.

To assess data locality, benchmarks often simulate or execute real-world scenarios. Tools like LMbench or Cachegrind profile memory access patterns, revealing how data is distributed across cache lines or pages. For instance, a matrix multiplication benchmark might show that a row-major traversal (accessing contiguous memory addresses) has better spatial locality than a column-major approach, reducing cache misses. Similarly, a database benchmark could measure the impact of indexing on disk I/O: a well-indexed query with localized data access will perform faster than one requiring scattered disk seeks. These tests highlight whether code or data structures align with hardware expectations, such as cache line sizes or prefetching algorithms.

Developers use benchmarking results to optimize data placement and access strategies. For example, reorganizing a struct to group frequently accessed fields (improving spatial locality) or redesigning loops to reuse cached data (enhancing temporal locality). A common optimization is blocking (loop tiling), where large datasets are processed in smaller chunks that fit into cache. Benchmarks like STREAM or synthetic microbenchmarks can validate these changes by showing reduced memory latency or higher throughput. By linking performance metrics directly to data access patterns, benchmarking provides actionable insights for tuning systems to exploit locality, balancing algorithmic efficiency with hardware constraints.