restrict keyword — aliasing hint: Visual walkthrough

5.1.32 · D2 · Coding › C Programming › restrict keyword — aliasing hint

Hum is loop ko poore raaste chalenge:

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

Neeche sab kuch isi baare mein hai ki compiler in teen pointers ke saath kya karne ki ijazat rakhta hai.

Step 1 — Pointer actually hota kya hai (ek ghar ka address)

KYA HAI. Ek pointer bas ek number hai: memory mein ek box ka address. a, b, c har ek boxes ki ek row ke pehle box ka address hai; a[i] ka matlab hai "woh box jo a shuru hoti hai wahan se i steps aage hai."

YE SHURU SE KYUN. Baad ke har argument ke baare mein yahi hai ki kya in do addresses mein se koi ek hi box pe land kar sakta hai. Agar tum memory ko numbered boxes ki ek gali ki tarah nahi dekhte, toh "overlap" ek bekar lafz hai.

TASVEER. Neeche, memory numbered cells ki ek row hai. b aur c do alag rows pe point karte hain; a teesri pe. Har arrow ke neeche label woh address hai jo usne hold kiya hua hai.

Figure — restrict keyword — aliasing hint

Step 2 — Compiler ka darr: shayad rows chhupchhup ke touch karti hain

KYA HAI. Function signature void add(int *a, int *b, int *c, int n) mein kuch bhi rows ko overlap karne se nahi rokta. Toh compiler ko worst case sochna padta hai: shayad a, b ek box se shift hai.

KYUN. Ek compiler ko apna code tabhi badalne ki ijazat hai jab change har legal input ke liye ek jaisa jawab guarantee kare. Agar overlap legal hai, toh use overlap ke saath bhi survive karna hoga.

TASVEER. Yeh woh zeherila case hai jis se compiler darta hai: a = b + 1. Ab a[i] aur b[i+1] literally ek hi box hain (yellow). a[i] mein likhna chupke se woh value b[i+1] overwrite kar deta hai jo ek baad wali iteration read karegi.

Step 3 — Darr kyun ek strict order force karta hai (har memory op KYON karta hai)

KYA HAI. Kyunki a[i] mein store karna kisi future b[?] ya c[?] ko change kar sakta hai, compiler ko teen memory operations ko bilkul source order mein chalana padta hai, har iteration mein:

purani value padho load b [i] \to purani value padho load c [i] \to likho, clobber ho sakta hai store a [i]

$load b [i]$ — row b se summand fetch karo.
$load c [i]$ — row c se summand fetch karo.
$store a [i]$ — sum likho; yeh arrow threat hai — yeh kisi aisi box pe land ho sakta hai jo future load ko chahiye.

KYUN. Agar compiler reorder karta — say b[i+1] pehle ek register mein load karta — lekin a[i] ka store usi box ko overwrite kar deta, toh register mein purana value hota. Isliye reordering banned hai; iterations ke paas caching banned hai.

TASVEER. Teen ops hard dependency edges se chain hain. Red edge woh store→future-load hazard hai jo sab kuch pin karta hai.

Step 4 — Promise: `restrict` shared box mita deta hai

KYA HAI. Ab hum qualifier add karte hain:

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

KYUN yeh tool aur const nahi? const promise karta hai "Main is pointer ke through nahi likhunga." Yeh ek alag promise hai — yeh do pointers ke touch karne ke baare mein kuch nahi kehta. Humein addresses ke disjoint hone ka ek promise chahiye, aur restrict ek maatra C99 tool hai jo bilkul yahi kehta hai:

\forall i, j : a ka koi bhi box & a [i] \neq = b ka koi bhi box & b [j] (aur same for a, c aur b, c)

Har $\neq =$ tumhari taraf se kasam khana hai ki koi box share nahi hai.

TASVEER. Wahi teen rows, lekin yellow shared box chali gayi — unke beech ek roshan diwar hai. Store arrow ab kisi doosri row ke boxes tak nahi pahunch sakta.

Step 5 — Koi shared box nahi, toh order collapse ho jaata hai

KYA HAI. Kyunki a[i] ka store b ya c ke kisi box pe kabhi nahi lag sakta, Step 3 ka store→load hazard gayab ho jaata hai. Dependency chain teen independent streams mein toot jaati hai.

KYUN. Independence optimization ki currency hai. Independent operations ko freely reorder, batch, aur cache kiya ja sakta hai, kyunki koi kisi ko barbad nahi kar sakta.

TASVEER. Step 3 ka chained diagram, ab red hazard edge cut ke saath. Teen ops azaad float kar rahe hain.

Step 6 — Azaadi SIMD ban jaati hai (ek saath bahut saare boxes)

KYA HAI. Order se mukti milne ke baad, compiler b ka ek block aur c ka ek block uthata hai, unhe ek wide instruction mein add karta hai, aur a ka ek block store karta hai. Yeh vectorization / SIMD hai — ek instruction kai elements pe kaam karti hai.

KYUN. Ek CPU 1 integer add karne mein jitna time lagta tha utne mein 8 integers add kar sakta hai. Yeh tabhi legal hai kyunki Step 5 ne prove kar diya ki boxes independent hain — koi store ek wide register mein already load kiye gaye value ko invalid nahi kar sakta.

TASVEER. b ke chaar boxes aur c ke chaar ek saath load, ek wide "+" se sum, a mein ek block ke roop mein store.

Step 7 — Degenerate case: agar tum JHOOTH bolo

KYA HAI. Pehle, woh function jise hum call kar rahe hain — parameter order note karo, destination pehle aata hai, bilkul memcpy(dst, src, n) ki tarah:

// 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];
}

Toh copy(dst, src, n) mein pehla argument wahan hai jahan hum likhte hain, doosra wahan se padhte hain. Ab diwar ke baare mein jhooth bolte hain:

int arr[4] = {1,2,3,4};
copy(arr + 1, arr, 3);   // dst = arr+1 (yahan likho), src = arr (yahan padho) -> OVERLAP hai

YEH KYUN DIKHATE HAIN. Har promise ka ek failure mode hota hai. Yahan compiler ne maana ki Step 4 ki diwar thi aur Step 6 ki batching ki — lekin diwar jhooth thi. Woh jis bhi order mein chaaha stale/fresh boxes read karta hai. Result undefined behaviour hai: shayad {1,1,2,3} (ek byte-forward dst[i]=src[i] jo un boxes ko baar baar read karta hai jo usne abhi likhe), shayad {1,1,1,1} (block/backward orders), shayad {1,2,3,4}-flavoured garbage. Ek hi call se do alag answers ⇒ undefined.

TASVEER. arr aur arr+1 ka overlap, ek hi source se branching karte do possible outputs ke saath — proof ki answer determine nahi hota.

Step 8 — Edge case: ek pointer ke peeche akela scalar

KYA HAI. Ek aur subtle win — ek pointer jo array bhi nahi hai:

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

KYUN. restrict ke bina, factor v ke andar point kar sakta hai. Tab v[i] likhne se *factor change ho sakta hai, isliye compiler ko har iteration mein *factor re-read karna padta hai. restrict factor ke saath, woh prove karta hai ki factor v ke bahar hai aur *factor ko ek baar register mein load karta hai.

TASVEER. Left: factor v ke andar hone ka darr, har step pe ek reload arrow force karta hai. Right: factor walled off, ek baar load (single arrow ek register ki taraf).

Ek-tasveer summary

Poori chain — darr → forced order → promise → azaadi → speed — ek frame mein.

Recall Feynman: poori walkthrough apne lafzon mein dobara batao

Memory numbered boxes ki ek lambi gali hai, aur a, b, c teen rows pe point karne wale arrows hain. Compiler is baat se darta hai ki shayad do rows ek box share karti hain (Step 2), kyunki agar a mein likhna b ko chheen sakta, toh sab kuch dheere aur order mein karna padta, har write ke baad re-read karna padta (Step 3). C ka built-in type rule sirf alag types ki rows ko alag karta hai; hamare same-type int* rows ke liye woh kuch nahi kehta, isliye tum compiler ko restrict se shaant karte ho: "Main kasam khata hun ki yeh rows kabhi nahi milti" (Step 4) — ek promise jo sirf a, b, c se descended pointers ko cover karta hai, kisi wild third pointer ko nahi ya arithmetic jo end se bahar jaaye. Ab koi write future read ko barbad nahi kar sakti, isliye operations azaad float karti hain (Step 5), aur CPU ek shot mein numbers ka pura block add kar sakta hai (Step 6) — bacha hua n mod W leftovers ke liye ek chhota scalar cleanup ke saath. Lekin agar tum jhooth bolte ho — overlapping rows dete ho jabki swear karte ho ki alag hain — woh phir bhi batch karta hai aur aisa garbage produce karta hai jise koi predict nahi kar sakta (Step 7). Yehi trick ek akele *factor ko bhi har loop ki jagah ek baar read karne deti hai (Step 8). Addresses ke baare mein ek promise tumhe saari speed dilata hai.

Active recall

Recall Apni tasveer check karo

Step 2 mein, kaunsa ek fact compiler ko pessimistic banata hai? (ek shared box possible hai)
restrict C ke built-in strict (type-based) aliasing se kaise alag hai? (type rule different types ko free mein alag karta hai; restrict same-type pointers ke liye promise supply karta hai)
Step 3 mein, kaunsa arrow woh hazard hai jo order ko pin karta hai? (store a[i] → future load)
const restrict ka kaam kyun nahi kar sakta? (const = nahi-likhunga; restrict = overlap-nahi-hoga)
restrict promise actually kisko cover karta hai? (pointer ko aur us se derived pointers ko — unrelated pointers ko nahi)
Step 6 mein, "tail" kya hai aur use kaise handle kiya jaata hai? (n mod W leftover elements; ek scalar cleanup loop)
copy(dst, src, n) mein, kaunsa argument likha jaata hai? (pehla, dst)
Step 7 mein, do outputs dono ko "correct" kya banata hai? (overlap + jhooth ⇒ undefined behaviour)

What single possibility makes the compiler refuse to reorder the loop?

Ki do rows ek box share kar sakti hain (aliasing) — ek overlapping address kaafi hai.

How does restrict differ from C's built-in strict (type-based) aliasing?

Strict aliasing compiler ko different-type pointers ke non-overlap assume karne deta hai free mein; restrict woh promise same-type pointers ke liye supply karta hai, jahan type rule khamosh hai.

Which memory operation is the reordering hazard in the add loop?

a[i] ka store, kyunki woh ek aisi box overwrite kar sakta hai jis ki ek later load ko zaroorat ho.

Why is restrict the right tool and not const here?

const pointer ke through koi write na hone ka promise karta hai; restrict promise karta hai ki pointer ke boxes kisi aur ke saath overlap nahi karte — sirf doosra reordering unlock karta hai.

Whom exactly does the restrict promise cover?

Restrict-qualified pointer aur us se derived pointers; unrelated pointers phir bhi alias kar sakte hain, aur out-of-bounds arithmetic apne aap undefined behaviour hai.

After the restrict promise, why can the loop vectorize?

Koi shared box nahi hone se, koi store loaded value ko invalid nahi kar sakta, isliye operations independent hain aur wide blocks mein chal sakti hain.

In copy(dst, src, n), which parameter is the destination?

Pehla wala, dst (write target); src doosra hai (read source), memcpy order se milta-julta.

What is the SIMD "tail" and how is it processed?

n mod W leftover elements jab n lane width W ka multiple nahi hota; compiler unke liye ek scalar cleanup loop (ya masked op) emit karta hai.

If restrict-marked pointers actually overlap, what is the result?

Undefined behaviour — output determine nahi hota, aksar sirf -O2/-O3 pe galat hota hai.

In v[i] *= *factor; why mark factor restrict?

Yeh prove karta hai ki factor v ke andar nahi hai, isliye *factor ek baar register mein load hota hai har iteration mein re-read karne ki jagah.

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

Visual walkthrough — restrict keyword — aliasing hint