Memory and Locality¶

Two algorithms with the same asymptotic complexity can perform very differently because modern memory is hierarchical.

Locality¶

Temporal locality: recently accessed data is likely to be accessed again.
Spatial locality: data near a recent access is likely to be accessed soon.

Contiguous arrays usually make sequential traversal cache-friendly. A linked list may place nodes far apart, requiring pointer chasing even though both structures can be traversed in Θ(n) time.

Java representation costs¶

An int[] stores primitive values contiguously. An ArrayList<Integer> stores references to Integer objects and may require boxing, unboxing, and additional objects. Exact object sizes are JVM- and configuration-dependent, so do not turn this observation into a universal byte count.

Allocation and garbage collection¶

Allocation can be cheap, but allocated objects still affect memory pressure and garbage-collection work. An optimization that reuses one O(n) buffer may be preferable to allocating many temporary collections, even when both approaches have the same peak Big-O space bound.

Cache-aware reasoning¶

Matrix traversal illustrates spatial locality. For Java's array-of-arrays representation, walking each row sequentially is generally friendlier to memory than repeatedly jumping between rows.

static long sumRows(int[][] matrix) {
    long total = 0;
    for (int[] row : matrix) {
        for (int value : row) {
            total += value;
        }
    }
    return total;
}

Measure carefully¶

JIT compilation, dead-code elimination, garbage collection, CPU frequency, cache warm-up, and input choice can invalidate naive timings. Use a benchmarking harness such as JMH for Java and report methodology alongside results.

Exercises¶

Compare the locality of a binary heap and a pointer-based binary tree.
Explain why fewer allocations can help without changing asymptotic space.
List three reasons a single System.nanoTime() measurement is unreliable.