Spatial and temporal locality, cache lines and hardware prefetching, row-major layout of C# multidimensional arrays, arrays of structs versus arrays of references, struct-of-arrays layouts, and benchmarking the effects.
CPUs load memory in cache lines of 64 bytes, so after one access the neighbouring bytes are already in cache (spatial locality), and recently used data is likely still there (temporal locality). Hardware prefetchers also spot sequential access and fetch ahead. A C# int[,] is stored row-major: one row's elements are next to each other. Walking row by row uses every byte of each line and the prefetcher keeps up; walking column by column jumps a whole row each step, wasting most of each line and missing cache, often 5–10× slower for large arrays. The same logic favours arrays of structs over lists of objects scattered on the heap, and struct-of-arrays layouts for hot numeric fields.
a[i], a[i+1] to about a[i+15] (for int) are now in L1, so they're almost free.A rectangular int[,] of 4,096 × 4,096 is one 64 MiB block, rows laid out one after another.
| Loop order | Access pattern | Effect |
|---|---|---|
for r { for c { m[r, c] } } |
Sequential addresses | Each line fully used, prefetcher happy |
for c { for r { m[r, c] } } |
Jumps 16 KiB each step | One int used per line fetched, prefetcher less effective, TLB misses |
For matrices bigger than the caches, the column-first loop is commonly 5–10× slower. Jagged arrays (int[][]) are arrays of separately allocated rows, which adds an indirection per row but keeps each row contiguous.
| Choice | Layout | Locality |
|---|---|---|
int[], Span<int>, List<int> |
Values contiguous | Excellent |
Point[] where Point is a struct |
Values contiguous | Excellent |
Customer[] where Customer is a class |
Contiguous references; objects anywhere on the heap | Each element access may miss cache |
LinkedList<T> |
Nodes scattered, each pointing to the next | Poor; pointer chasing |
Dictionary<TKey, TValue> |
Entries in arrays, plus buckets | Good for lookups, but each lookup touches a couple of lines |
Struct-of-arrays (separate Prices[], Quantities[]) |
Each field contiguous | Best when a loop needs only a few fields |
The GC helps a little: objects allocated together tend to be placed together and compaction keeps them close, but long-lived, mutated object graphs drift apart.
A pricing engine stored 2 million positions as List<Position> (a class with 20 fields) and revalued them by reading three fields each. Converting the hot fields into a struct array (PositionCore[] with just the three values) cut revaluation from 180 ms to 35 ms, because the loop read 24 bytes per position contiguously instead of chasing a reference to a 200-byte object.
Checks practical performance intuition about memory.
Green flags: explains cache lines, spatial and temporal locality, row-major order, reference arrays versus struct arrays, gives a realistic example and measures with BenchmarkDotNet at realistic sizes.
Red flags: thinks all memory access costs the same; can't explain why the loop order matters; recommends structs everywhere without caveats.
int[4, 4] m: row 0 row 1 row 2 row 3
address: [00 01 02 03] [04 05 06 07] [08 09 10 11] [12 13 14 15]
row-major walk: 00 01 02 03 04 05 ... (sequential)
column-major walk: 00 04 08 12 01 05 09 13 ... (stride = row length)
With 4,096 columns of int, the column walk strides 16 KiB per step: every access touches a different cache line and, every 4 KiB, a different page (so also TLB pressure).
| Level | Typical size | int values |
Position objects (~200 bytes) |
|---|---|---|---|
| L1d | 32–64 KB | 8–16 thousand | ~250 |
| L2 | 1–2 MB | 250–500 thousand | ~7,500 |
| L3 | 16–100+ MB (shared) | millions | ~100,000+ |
Once the working set exceeds a level, performance drops a step. Benchmarks over tiny arrays hide locality problems; test with production-sized data.
Customer[] (class): [ref][ref][ref][ref] -> objects scattered on the heap
| | | |
v v v v
obj obj obj obj (each may be a cache miss)
Point[] (struct): [x y][x y][x y][x y] (values inline, sequential)
Structs aren't free: large structs are expensive to copy and can't be shared by reference. Use ref returns, Span<T>, in parameters or ref locals (ref var p = ref points[i];) to avoid copies.
AoS: [price qty fee name ...][price qty fee name ...] ... loop reads price+qty, drags fee+name too
SoA: prices: [p p p p p p ...]
quantities: [q q q q q q ...] loop reads only what it needs, SIMD-friendly
SoA is what columnar databases and analytics engines do. In C# it's a deliberate optimisation for hot loops, not a default design.
foreach over List<T> of structs or primitives: great. Over objects: fine for small lists, costly for millions.Dictionary with string keys: each lookup hashes the string (reading it) and compares it with the entry's key (reading another object). FrozenDictionary (.NET 8+) reorganises read-only data for faster lookups.object, non-generic collections) turns contiguous values into scattered heap objects.[MemoryDiagnoser] and, where available, [HardwareCounters(HardwareCounter.CacheMisses)].perf stat -e cache-references,cache-misses,LLC-load-misses.int[,] at 256 × 256, 1,024 × 1,024 and 4,096 × 4,096, and plot the ratio as the matrix outgrows each cache level.decimal field over 1 million items stored as List<OrderClass>, OrderStruct[] and a separate decimal[].LinkedList<int> version and explain the result.namespace CacheLocality;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
public sealed class OrderClass
{
public decimal Total { get; init; }
public string Customer { get; init; } = "";
public DateTime Created { get; init; }
}
public readonly record struct OrderStruct(decimal Total, DateTime Created);
[MemoryDiagnoser]
public class LocalityBenchmarks
{
[Params(1024, 4096)]
public int Size;
private int[,] _matrix = new int[0, 0];
private List<OrderClass> _classes = [];
private OrderStruct[] _structs = [];
private decimal[] _totals = [];
[GlobalSetup]
public void Setup()
{
_matrix = new int[Size, Size];
var random = new Random(1);
int n = 1_000_000;
_classes = Enumerable.Range(0, n)
.Select(i => new OrderClass { Total = i, Customer = $"C{i}", Created = DateTime.UnixEpoch })
.OrderBy(_ => random.Next()) // shuffle so objects aren't in allocation order
.ToList();
_structs = _classes.Select(c => new OrderStruct(c.Total, c.Created)).ToArray();
_totals = _classes.Select(c => c.Total).ToArray();
}
[Benchmark(Baseline = true)]
public long RowMajor()
{
long sum = 0;
for (var r = 0; r < Size; r++)
for (var c = 0; c < Size; c++)
sum += _matrix[r, c];
return sum;
}
[Benchmark]
public long ColumnMajor()
{
long sum = 0;
for (var c = 0; c < Size; c++)
for (var r = 0; r < Size; r++)
sum += _matrix[r, c];
return sum;
}
[Benchmark] public decimal SumClasses() { decimal s = 0; foreach (var o in _classes) s += o.Total; return s; }
[Benchmark] public decimal SumStructs() { decimal s = 0; foreach (ref readonly var o in _structs.AsSpan()) s += o.Total; return s; }
[Benchmark] public decimal SumColumn() { decimal s = 0; foreach (var t in _totals) s += t; return s; }
}
public static class Program
{
public static void Main() => BenchmarkRunner.Run<LocalityBenchmarks>();
}
Mistake: iterating multidimensional arrays in the wrong order.
Making the first index the inner loop strides across rows, wasting cache lines and running several times slower on large data.
Instead: make the last index the innermost loop for T[,], and walk jagged arrays row by row.
Mistake: assuming List<MyClass> is contiguous data.
Only the references are contiguous; the objects can be spread across the heap, so each access may miss cache.
Instead: for large, hot collections, store the hot fields in arrays of small structs or separate arrays.
Mistake: turning everything into structs.
Large mutable structs are copied on assignment and when passed by value, causing bugs and hidden costs.
Instead: use small, ideally readonly, structs for hot data, and access them by reference (ref, in, Span<T>).
Mistake: benchmarking with tiny data sets.
Everything fits in L1 or L2, so the layout differences disappear and the conclusions don't hold in production.
Instead: benchmark with realistic sizes and use [Params] to see where performance steps down.
Mistake: choosing LinkedList<T> for performance.
Its O(1) insertion is cancelled out by pointer chasing on every traversal.
Instead: prefer List<T>, Queue<T> or arrays unless you genuinely need stable node references and frequent middle insertions.
Seniors know that for in-memory work, the memory access pattern often matters more than Big O at realistic sizes. A linear scan of a contiguous array can beat a "smarter" pointer-based structure up to surprisingly large sizes.
| Workload | Locality problem | Layout that helps |
|---|---|---|
| Pricing / risk loops | Reading 3 fields from 200-byte objects | Struct array of hot fields, or struct-of-arrays |
| In-memory cache or lookup tables | Scattered entries, string keys | FrozenDictionary/FrozenSet, smaller keys, intern or pre-hash |
| Analytics / reporting | Row objects, only a few columns used | Columnar (SoA) arrays, TensorPrimitives |
| Serialisation / parsing | Many small allocations | Span<byte>, pooled buffers, Utf8JsonReader |
| Parallel counters | False sharing on one cache line | Per-thread locals, padding, combine at the end |
| Real-time / game-style loops | Object graphs mutated over time | Pre-allocated arrays, entity-component layouts |
They also keep this in proportion: most business services are dominated by I/O, so data-oriented layouts go only into measured hot paths and ordinary domain models stay readable. Trade-offs: struct arrays need care with copying (ref locals, in parameters) and with keeping duplicated data in sync; SoA makes code less object-oriented. Document the decision (an ADR) and keep the benchmark in the repo so the next refactor does not undo it.
Cores keep their caches coherent: when one core writes to a cache line, copies of that whole 64-byte line in other cores are invalidated. If thread A updates counters[0] and thread B updates counters[1], they're logically independent but sit on the same line, so the line ping-pongs between cores on every write. That's false sharing: more threads, more invalidations, and the loop gets slower. Symptoms are high CPU with poor scaling and no locks in sight. The best fix is to accumulate in a local variable per thread and combine once at the end (Parallel.For with localInit/localFinally). Where per-thread state must live in shared memory, pad each slot to its own cache line (128 bytes is safe across x64 and Apple Arm64).
SIMD (single instruction, multiple data) lets one CPU instruction operate on several values at once, held in a vector register: a 128-bit register holds four ints, a 256-bit one holds eight. x64 offers SSE, AVX2 and AVX-512; Arm64 offers NEON. .NET exposes this through portable types (Vector128<T>, Vector256<T>, Vector512<T> and the size-agnostic Vector<T>), plus platform-specific intrinsics. First, use what's already vectorised: Span methods like IndexOf and SequenceEqual, and TensorPrimitives. Hand-write SIMD only for a measured hot loop over contiguous primitive data, with a scalar tail and a fallback when IsHardwareAccelerated is false.
How to tell it (STAR)
**Situation:** At [company], each price tick triggered a revaluation of [2 million] positions that took about [180 ms], delaying client-facing updates. **Task:** I was asked to bring it under [50 ms]. **Action:** The profile showed time in simple field reads with lots of cache misses, so I benchmarked different layouts. The loop only needed three fields, so I moved those into a contiguous array of small structs that stayed in sync with the domain objects. **Result:** Revaluation dropped to about [35 ms], and the ADR and benchmark kept the design from being undone later.
Last updated 23 Oct 2026.