Experiments and implementations · Intermediate

Compare row and column traversal order

Traverse the same contiguous matrix in two orders, verify equal results and work, and compare native timings without inventing cache counts.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Change order while preserving all visited elements
  2. Build with a visible loop-order contract
  3. Read the index progression in the source
  4. Inspect all samples and normalize by equal work
  5. Keep numeric and generated-order assumptions aligned
  6. Solve the changed-row-length exercise
  7. Ask Logeia about this articleCheck your understanding

Change order while preserving all visited elements

Allocate a 2048 by 2048 matrix of uint32_t in one contiguous row-major region. Sum every element once in row order and once in column order. Both cases perform the same additions over the same values; unlike the stride experiment, neither skips elements. Read the cache-placement guide first, then separate a predicted address pattern from measured native traversal time. A Python nested-loop substitute introduces interpreter costs and is not the same experiment.

Four-byte elements make the allocation 16 MiB. Adjacent row elements differ by four bytes, while adjacent column elements differ by 8,192 bytes. In a 64-byte-line teaching model, row order immediately uses sixteen elements of a line. Column order next touches another line, although later columns can revisit earlier lines. The model does not count actual transfers: retention, prefetching and other hierarchy behavior still matter. Record these address facts before looking at durations so the prediction is independent of whichever order happens to win a particular run.

Build with a visible loop-order contract

Save the complete code as row.c. On Linux with GCC, compile using gcc -O2 -std=c11 -fno-loop-interchange -fno-ipa-pure-const row.c -o row, then run ./row. Disabling interchange preserves the loop-order question; it is an experimental control, not general application tuning advice. With another compiler, verify its transformation behavior rather than assuming flags are interchangeable. Output is CSV containing order, repetition, nanoseconds and checksum.

Allocation, initialization, checking and printing are outside the measured interval. Values are i modulo seventeen and the accumulator is 64-bit, safely covering this input. Allocation failure aborts rather than continuing with an invalid pointer. Initial traversals compare both results, and each timed result is checked again. Those preparatory traversals also mean that the first saved timing is not a proof of an empty hierarchy. Describe it as the first recorded observation after preparation, preserving what actually happened before the timer began.

Read the index progression in the source

The expression a[i*SIDE+j] identifies row i and column j. Incrementing j walks contiguous elements, while incrementing i jumps by a row. Write the first four indices before running: column order visits zero, 2048, 4096 and 6144; row order visits zero, one, two and three. Multiply by four to obtain byte offsets. Replacing this allocation with separately allocated row pointers changes the contiguity assumption and should be recorded as a different experiment.

The r and k loops alternate which direction is timed first. That reduces one-sided exposure to gradual environmental changes compared with completing every row sample before starting columns. It does not eliminate ordering effects, because the previous traversal changes cache state. Each result is consumed through sink and a printed checksum. Do not rely on noinline alone as evidence that all intended work survives optimization; inspect the actual call and loop in disassembly as an additional check of the implementation being timed.

c
#define _POSIX_C_SOURCE 200809L
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static volatile uint64_t sink;
static uint64_t ns(void) { struct timespec t; assert(!clock_gettime(CLOCK_MONOTONIC,&t)); return (uint64_t)t.tv_sec*1000000000u+t.tv_nsec; }
enum { SIDE=2048 };
__attribute__((noinline)) static uint64_t walk(const uint32_t *a,int column) {
 uint64_t sum=0;
 if(column) { for(size_t j=0;j<SIDE;j++) for(size_t i=0;i<SIDE;i++) sum+=a[i*SIDE+j]; }
 else { for(size_t i=0;i<SIDE;i++) for(size_t j=0;j<SIDE;j++) sum+=a[i*SIDE+j]; }
 return sum;
}
int main(void) {
 size_t n=(size_t)SIDE*SIDE;
 uint32_t *a=malloc(n*sizeof(*a)); assert(a);
 for(size_t i=0;i<n;i++) a[i]=(uint32_t)(i%17);
 uint64_t expected=walk(a,0); assert(walk(a,1)==expected);
 for(int r=0;r<9;r++) for(int k=0;k<2;k++) {
  int column=(r+k)%2; uint64_t start=ns(),sum=walk(a,column),elapsed=ns()-start;
  assert(sum==expected); sink=sum;
  printf("%s,%d,%llu,%llu\n",column?"column":"row",r,(unsigned long long)elapsed,(unsigned long long)sum);
 }
 free(a);return 0;
}

Inspect all samples and normalize by equal work

A passing run prints nine rows per direction with identical checksums. It does not assert a timing ranking, because differences and variation depend on the environment. Preserve all samples and calculate a median and quantiles for each order. Divide nanoseconds by 4,194,304 for time per element. Total durations are already comparable because work is equal, but normalized values remain interpretable when dimensions change. Selecting only one fastest row hides scheduling and other variation.

The recorded execution uses GCC 13.3 on a virtualized CPU exposing an AMD EPYC model. It verifies successful execution, checksums and generated code, but does not acquire PMU counts. A slower column traversal cannot be converted into a count of cache misses. Translation, prefetching, shared resources and operating-system scheduling can contribute. Reproduce with CPU, OS, compiler, flags and repetition count recorded together. If hardware counters become available, save their interval and interpretation as separate evidence rather than treating duration as their substitute.

Keep numeric and generated-order assumptions aligned

The small nonnegative integer input permits exact comparison of both complete traversal orders with a 64-bit accumulator. Changing to float introduces accumulation-order rounding and can invalidate a bitwise-equality oracle. Define error tolerance and reference before changing type. Likewise, a build permitting loop interchange may transform column-order source into another generated order. Inspect the inner address increment in the called implementation. Matching output alone proves neither retained source order nor the intended performance comparison. These two checks serve different purposes: result validation protects the computation, while instruction inspection protects the experimental variable. Retain both when adding dimensions or another compiler configuration.

Solve the changed-row-length exercise

Change SIDE to 2049. The column step becomes 8,196 bytes. The element count and checksum also change, so do not reuse the old expected total or raw duration as though work were identical. Verify that both traversals cover the new equal element set and recompute time per element. Set conflicts can change, but a faster result is not guaranteed. Keep this size's observations separate from the original samples.

If the task instead becomes reading only one column, it no longer does equal work to a full row-major scan. That is a different access question, requiring its own normalization rather than a raw total-time ranking. Explain layout, visited indices, visit count and result together. At completion retain or remove the binary, source and CSV; there is no background server or external service to stop. The stride experiment next varies spacing while explicitly tracking unequal visit counts, so the equal-work assumption used here is not carried over accidentally.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 8

Prepare for AI systems · STEP 5

Choose a learning path