Demonstrate Row-Major vs Column-Major Matrix Traversal

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.