Experiments and implementations · Intermediate

Compare stride, visit count and traversal time

Measure two allocation sizes and four strides in C, normalize unequal work, and keep useful bytes distinct from cache and translation traffic.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Count visits before comparing durations
  2. Convert element spacing into byte spacing
  3. Run two explicitly sized allocations
  4. Normalize work and identify tiny intervals
  5. Separate observation from causal candidates
  6. Validate the final visit independently
  7. Solve the non-divisible-length exercise
  8. Ask Logeia about this articleCheck your understanding

Count visits before comparing durations

Traverse a uint32_t array using strides of one, sixteen, 64 and 1024 elements. Every value is one. A larger stride visits fewer elements of the same allocation, so this differs from the equal-work row-versus-column experiment. Calculate the number of visits first and verify that the sum equals it. After reading the cache-placement guide, use this lab to avoid interpreting less work as a better cache implementation.

For length n and stride s, indices are zero, s, twice s and so on while below n. The visit count is ceil(n/s), calculated here as integer division of n+s-1 by s. With n=8192, stride sixteen makes 512 visits and stride 1024 only eight. A smaller total duration can therefore be entirely consistent with greater cost per visited element. The application's required data still determines the useful comparison: skipping values is not a legal optimization if the original task needed their sum.

Convert element spacing into byte spacing

Stride is an element count, not a byte count. Four-byte elements turn strides sixteen, 64 and 1024 into byte steps of 64, 256 and 4096 respectively. In a 64-byte-line model, stride one can use multiple values from each fetched line, while stride sixteen uses one. Useful bytes are four times the visit count; actual bytes transferred across a hierarchy boundary can differ because of line transfers, prefetching and retention.

A 4096-byte step reaches the same offset of successive pages if the actual page size is 4096 bytes. Translation behavior and prefetch opportunities can change alongside line placement. Elapsed time alone cannot label a difference as a TLB miss or an L1 miss. If a future experiment changes page size, verify the allocation actually received that mapping. Allocation success does not prove huge-page use. Keep line, page and element units separate when predicting which mechanisms might matter.

Run two explicitly sized allocations

Save the code as stride.c. Build with gcc -O2 -std=c11 -fno-loop-interchange -fno-ipa-pure-const stride.c -o stride and run ./stride. The two lengths allocate 32 KiB and 64 MiB. These are allocation sizes, not universal assertions that one resides in private cache and the other exceeds every cache. Record processor configuration and sharing, and retain separate results for each size. Initialization stays outside timing, and allocation failure stops the program.

Each size and stride receives nine observations. CSV records length, stride, visits, repetition and nanoseconds. The order of strides rotates across repetitions. Assertions require the sum to equal the visit count, separating successful termination from correct traversal. Only one walk call is timed; printing and filling the input with ones are excluded. Save compiler version and complete settings alongside output, rather than combining observations from different binaries into a single unlabeled series.

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; }
__attribute__((noinline)) static uint64_t walk(const uint32_t *a,size_t n,size_t stride) {
 uint64_t sum=0; for(size_t i=0;i<n;i+=stride) sum+=a[i]; return sum;
}
int main(void) {
 size_t sizes[]={8192,16777216},strides[]={1,16,64,1024};
 for(int z=0;z<2;z++) {
  size_t n=sizes[z]; uint32_t *a=malloc(n*sizeof(*a)); assert(a);
  for(size_t i=0;i<n;i++) a[i]=1;
  for(int r=0;r<9;r++) for(int k=0;k<4;k++) {
   size_t stride=strides[(k+r)%4],visits=(n+stride-1)/stride;
   uint64_t start=ns(),sum=walk(a,n,stride),elapsed=ns()-start;assert(sum==visits);sink=sum;
   printf("%zu,%zu,%zu,%d,%llu\n",n,stride,visits,r,(unsigned long long)elapsed);
  }
  free(a);
 }
 return 0;
}

Normalize work and identify tiny intervals

Divide nanoseconds by visits for time per visited element. Multiplying visits by four gives useful bytes and can produce a useful-byte throughput, but do not label it DRAM bandwidth. It does not measure full-line transfers or cache filtering. A comparison table should retain allocation size, stride, visits, total duration and normalized duration together. Explain any ranking change after normalization using the changed amount of work.

The small allocation at stride 1024 performs only eight reads. Timer overhead can then occupy a substantial fraction of the interval. More printed decimal places do not create precision. Compare with an empty timing interval before interpreting tiny differences. Repeating multiple traversals inside one interval can reduce relative timer overhead but also changes reuse conditions, which must be reported. Preserve all observations and summarize medians and quantiles instead of selecting one favorable minimum. Scheduling variation and intervals containing too little work are distinct measurement limitations.

Separate observation from causal candidates

The recorded run uses GCC 13.3 and a virtualized CPU, validating sums for both sizes and all four strides. No PMU counts are acquired, so cache and translation misses remain unmeasured. Timing curves can motivate hypotheses, but a bend alone does not identify cache capacity or indexing. Several mechanisms may change over similar ranges. A counter-based follow-up must save processor-specific event definitions, scope and multiplexing.

This is a single-thread read-only experiment. It does not generate false sharing by having another core write the same line. A write experiment introduces ownership and writeback questions as additional conditions. Before interpreting a graph, verify that the operation required by the proposed explanation actually appears in the code. Narrow a broad claim about slow memory into a question about a particular boundary and observation. The data-layout article then helps investigate why unused values might be transferred along with useful ones.

Validate the final visit independently

For n=17 and stride sixteen, indices zero and sixteen are both valid, giving two visits. A faster loop that drops the last visit has changed work. Check that the final valid index is below n and the next would be outside. Keep this independent oracle when modifying loop bounds or normalizing durations. It complements the large power-of-two examples, where exact divisibility can conceal an off-by-one error. A useful benchmark must preserve the required visited set before its timing can inform a placement hypothesis.

Solve the non-divisible-length exercise

For n=10 and s=4, the visited indices are zero, four and eight. There are three visits and a sum of three when every value is one. Plain integer division 10/4 yields two and misses the last visit; the implemented ceiling calculation includes it. For positive n, even a stride larger than n visits index zero once. An extension allowing an empty allocation needs an explicit allocation and result contract.

Can sums ten and three from strides one and four be called equal-result implementations? No: they read different required data. If an application needs only a spaced subset, state that requirement before comparing implementations. Estimate memory before enlarging allocations, rather than starting many large cases simultaneously. The code frees each allocation after its observations. Retain or delete CSV and binaries as appropriate; there is no external service or persistent database to clean up.

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