Visual walkthrough — restrict keyword — aliasing hint

We will walk this loop the whole way:

for (int i = 0; i < n; i++)
    a[i] = b[i] + c[i];

Everything below is about what the compiler is allowed to do with these three pointers.

Step 1 — What a pointer actually is (a house address)

WHAT. A pointer is just a number: the address of a box in memory. a, b, c are each an address of the first box of a row of boxes; a[i] means "the box i steps after where a starts."

WHY start here. Every later argument is about whether two of these addresses can land on the same box. If you don't picture memory as a numbered street of boxes, "overlap" is a meaningless word.

PICTURE. Below, memory is a row of numbered cells. b and c point at two separate rows; a points at a third. The label under each arrow is the address it holds.

Step 2 — The compiler's fear: maybe the rows secretly touch

WHAT. Nothing in the function signature void add(int *a, int *b, int *c, int n) forbids the rows from overlapping. So the compiler must imagine the worst case: perhaps a is b shifted by one box.

WHY. A compiler is only allowed to change your code if the change is guaranteed to give the same answer for every legal input. If overlap is legal, it must survive overlap.

PICTURE. Here is the poisonous case the compiler dreads: a = b + 1. Now a[i] and b[i+1] are literally the same box (yellow). Writing a[i] silently rewrites the value b[i+1] that a later iteration will read.

Step 3 — Why fear forces a strict order (WHAT each memory op does)

WHAT. Because a store into a[i] might change some future b[?] or c[?], the compiler must run the three memory operations in exactly source order, every single iteration:

• $\text{load }b[i]$ — fetch the summand from row b.
• $\text{load }c[i]$ — fetch the summand from row c.
• $\text{store }a[i]$ — write the sum; this arrow is the threat — it might land on a box a future load needs.

WHY. If the compiler reordered — say loaded b[i+1] early into a register — but the store to a[i] overwrote that very box, the register would hold a stale value. So reordering is banned; caching across iterations is banned.

PICTURE. The three ops chained by hard dependency edges. The red edge is the store→future-load hazard that pins everything down.

Step 4 — The promise: restrict erases the shared box

WHAT. Now we add the qualifier:

void add(int * restrict a, const int * restrict b,
         const int * restrict c, int n);

WHY this tool and not const? const promises "I won't write through this pointer." That's a different promise — it says nothing about two pointers touching. We need a promise about addresses being disjoint, and restrict is the only C99 tool that says exactly that:

Each $\ne$ is you swearing no box is shared.

PICTURE. The same three rows, but the yellow shared box is gone — a bright wall separates them. The store arrow can no longer reach another row's boxes.

Step 5 — With no shared box, order collapses

WHAT. Since a store to a[i] can never hit a b or c box, the store→load hazard from Step 3 disappears. The dependency chain breaks into three independent streams.

WHY. Independence is the currency of optimization. Independent operations can be reordered, batched, and cached freely, because none can spoil another.

PICTURE. The chained diagram of Step 3, now with the red hazard edge cut. The three ops float free.

Step 6 — Freedom becomes SIMD (many boxes at once)

WHAT. Free of ordering, the compiler grabs a block of b and a block of c, adds them in one wide instruction, and stores a block of a. This is vectorization / SIMD — one instruction operating on several elements.

WHY. A CPU can add, say, 8 integers in the time it took to add 1. This is only legal because Step 5 proved the boxes are independent — no store can invalidate a value already loaded into a wide register.

PICTURE. Four boxes of b and four of c loaded together, summed by one wide "+", stored as one block into a.

Step 7 — The degenerate case: what if you LIE

WHAT. First, the function we are calling — note the parameter order, destination comes first, exactly like memcpy(dst, src, n):

// copy n ints from src into dst; PROMISES dst and src regions never overlap
void copy(int * restrict dst, const int * restrict src, int n) {
    for (int i = 0; i < n; i++) dst[i] = src[i];
}

So in copy(dst, src, n) the first argument is where we write, the second is where we read. Now we lie about the wall:

int arr[4] = {1,2,3,4};
copy(arr + 1, arr, 3);   // dst = arr+1 (write here), src = arr (read here) -> they OVERLAP

WHY show this. Every promise has a failure mode. Here the compiler believed Step 4's wall existed and did Step 6's batching — but the wall was a lie. It reads stale/fresh boxes in whatever order it chose. The result is undefined behaviour: maybe {1,1,2,3} (a byte-forward dst[i]=src[i] that keeps re-reading boxes it just wrote), maybe {1,1,1,1} (block/backward orders), maybe {1,2,3,4}-flavoured garbage. Two different answers from the same call ⇒ undefined.

PICTURE. The overlap of arr and arr+1, with two possible outputs branching from the same source — proof the answer isn't determined.

Step 8 — Edge case: the single scalar behind a pointer

WHAT. A subtler win — one pointer that isn't even an array:

void scale(float * restrict v, float * restrict factor, int n) {
    for (int i = 0; i < n; i++) v[i] *= *factor;
}

WHY. Without restrict, factor might point inside v. Then writing v[i] could change *factor, so the compiler must re-read *factor every iteration. With restrict factor, it proves factor is outside v and loads *factor once into a register.

PICTURE. Left: factor feared to live inside v, forcing a reload arrow each step. Right: factor walled off, loaded once (single arrow to a register).

The one-picture summary

The whole chain — fear → forced order → promise → freedom → speed — in one frame.

Active recall

Connections

• Yeh note Hinglish mein →
• Pointers in C
• Pointer aliasing
• const qualifier
• memcpy vs memmove
• Compiler optimization & vectorization (SIMD)
• Undefined behaviour in C
• C99 standard features

Derivation Map