Demonstrate Row-Major vs Column-Major Matrix Traversal

Topic Overview

Loop Order Must Match Layout

C stores two-dimensional arrays in row-major order: row 0's elements sit contiguously, then row 1, and so on. Ulrich Drepper's memory guide opens with loop interchange because traversing columns in the outer loop jumps by N * sizeof(int) bytes, blowing cache lines on every step.

Spatial Locality on Cache Lines

CPUs fetch 64-byte cache lines. Sequential row access touches each line once per 16 ints (typical). Column-first access on a 1000x1000 matrix causes a miss almost every load.

cCopy
Loading…

• Fortran and MATLAB default to column-major; C interop needs care
• Measure with perf stat -e cache-misses to see the gap
• Same arithmetic, different order: expect 10x/100x slowdown on large N
• Tiling (blocking) helps when you cannot change storage order

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will benchmark row-major vs column-major traversal on a large matrix and print both timings. This exercise asks you to explain the ratio using cache lines and stride.

Your Task

Why is summing a matrix row by row so much faster than column by column? Wall-clock timings are noisy, so this task measures the cause directly. Simulate a set-associative cache with LRU replacement, and count the misses that each traversal order produces on a row-major C array.

Input

cCopy
Loading…

Rules

• Element (r, c) lives at byte address (r * COLS + c) * ELEM, starting at 0.
• The cache has SIZE / (LINE * WAYS) sets. An address maps to block addr / LINE, which goes to set block % sets with tag block / sets. On a miss, fill an empty way, or else evict the least recently used way. Hits and fills both count as a use.
• The geometry is valid only if LINE is a power of two, WAYS >= 1, and SIZE divides into a power-of-two number of sets. Otherwise print cache SIZE LINE WAYS: invalid geometry and keep the old cache.
• A matrix is valid if ROWS, COLS and ELEM are nonzero and ROWS * COLS <= 4000000 (otherwise matrix: invalid size).
• Every traversal starts from an empty cache and touches each element once. row runs the column index in the inner loop, and col runs the row index in the inner loop.
• compare runs row, then col, prints both, and prints the ratio of misses.

Output

cCopy
Loading…

The miss rate and the ratio are rounded half up to 2 decimals using integer arithmetic. Bytes fetched = misses * LINE.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Model tags and LRU order per set. A fully associative or "count distinct lines" shortcut gives wrong answers when accesses conflict in a set.
2. Generate the address stream from the loop nest itself, exactly as the C code would access memory.

Hidden tests cover a matrix small enough to fit (both orders equal), a direct-mapped cache where a power-of-two row length makes every column access conflict, a padded row that removes the conflicts, 8-byte elements, a single traversal, and invalid geometry.