restrict keyword — aliasing hint: Exercises — Hinglish deep dive

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

Shuru karne se pehle, ek picture vocabulary fix karne ke liye. Jab hum kehte hain ki do pointers alias karte hain, matlab unke memory regions touch karte hain ya overlap karte hain. Jab hum kehte hain disjoint, matlab regions ek bhi byte share nahi karte.

Figure — restrict keyword — aliasing hint

Level 1 — Recognition

Exercise 1.1

Inme se restrict kya hai: (a) ek statement, (b) ek function, (c) ek type qualifier, (d) ek preprocessor macro?

Recall Solution

(c) ek type qualifier. Jaise const ek pointer ke type mein baithta hai, restrict bhi ek pointer ke type mein baithta hai (T * restrict p). Yeh koi code nahi hai jo run ho; yeh ek label hai type pe jise compiler padhta hai. Sibling qualifier ke liye dekho const qualifier.

Exercise 1.2

Is declaration ko plain English mein zor se padho:

int * restrict p;

Recall Solution

"p ek pointer hai int ki taraf, aur jab tak p use mein hai, ==jo bhi object main p ke through reach karta hoon woh sirf p ke through hi reach hota hai== (ya un pointers ke through jo maine p se copy kiye)." Yeh ek no-aliasing ka promise hai, bas itna hi.

Exercise 1.3

Sach ya jhooth: compiler error emit karega agar mere do restrict pointers actually overlap karte hain.

Recall Solution

Jhooth. Compiler generally prove nahi kar sakta ki pointers overlap nahi karte (pointers runtime pe user input se aa sakte hain). Isliye woh simply trust karta hai tumhe. Toota hua promise undefined behaviour hai, jo aksar sirf -O2/-O3 pe dikhayi deta hai.

Level 2 — Application

Exercise 2.1

restrict (aur jahan sensible ho const) add karo taaki yeh vectorizable ho jaye, assuming teen arrays kabhi overlap nahi karte:

void axpy(float *y, float *x, float a, int n) {
    for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i];
}

Recall Solution

void axpy(float * restrict y, const float * restrict x, float a, int n) {
    for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i];
}

x sirf read hota hai, isliye ise const (modifiability promise) aur restrict (aliasing promise) mark karo.
y write aur read dono hota hai, isliye restrict lekin const nahi.
a ek plain value hai, pointer nahi — koi qualifier nahi.

Ab compiler jaanta hai ki y[i] pe store x[i+1] ko kabhi change nahi kar sakta, isliye woh x ka ek block load kar sakta hai, ek saath kayi lanes pe multiply-add kar sakta hai, aur y ka ek block store kar sakta hai. Dekho Compiler optimization & vectorization (SIMD).

Exercise 2.2

Is loop mein, factor ko restrict se mark karne se compiler read ko loop se bahar kyun hoist kar sakta hai?

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

Recall Solution

Promise ke bina, compiler ko darr rehta hai ki factor v ke andar point kar raha ho. Tab v[i] *= *factor kisi iteration pe *factor khud ko change kar sakta hai — isliye use ==har pass mein *factor re-read karna padta hai==. restrict factor ke saath, factor v ko alias nahi kar sakta, isliye *factor ek baar register mein load hota hai aur reuse hota hai. Kam memory loads → tez loop.

Exercise 2.3

Ise disjointness promise ke saath rewrite karo, phir ek sentence mein batao ki kya galat ho sakta hai agar caller us promise ko ignore kare:

void merge_sum(long *out, long *in1, long *in2, int n);

Recall Solution

void merge_sum(long * restrict out, const long * restrict in1,
               const long * restrict in2, int n);

Agar koi caller aisa out pass kare jo in1 ya in2 se overlap karta ho (jaise merge_sum(a, a, b, n)), toh code mein undefined behaviour hai: vectorized version stale ya already-overwritten values read kar sakta hai, galat sums dega — aur yeh sirf tab misbehave kar sakta hai jab optimizations on hon.

Level 3 — Analysis

Exercise 3.1

int arr[5] = {1,2,3,4,5}; aur yeh restrict copy di gayi hai:

void copy(int * restrict dst, const int * restrict src, int n) {
    for (int i = 0; i < n; i++) dst[i] = src[i];
}

Call copy(arr, arr + 2, 3) {3,4,5} se positions 0..2 mein copy karta hai. Kya dst aur src overlap karte hain? Kya promise honor hua? arr baad mein kya hoga agar compiler front-to-back copy kare?

Recall Solution

dst arr[0..2] ke bytes cover karta hai, src arr[2..4] cover karta hai. Woh arr[2] share karte hain — isliye woh overlap karte hain, promise toot gaya, aur behaviour undefined hai. Agar (guaranteed nahi!) compiler simple front-to-back copy kare:

i=0: arr[0]=arr[2]=3 → {3,2,3,4,5}
i=1: arr[1]=arr[3]=4 → {3,4,3,4,5}
i=2: arr[2]=arr[4]=5 → {3,4,5,4,5} Result {3,4,5,4,5} — lekin kyunki yeh UB hai, vectorized build mein kuch aur bhi aa sakta hai. Overlap ke liye memmove semantics use karo.

Exercise 3.2

Same copy, call copy(arr + 2, arr, 3) — {1,2,3} ko positions 2..4 mein copy karo. Overlap? Agar compiler vectorize kare (pehle saara src block read kare, phir write kare), toh kya milega, aur yeh naive loop se kyun alag hai?

Recall Solution

dst = arr[2..4], src = arr[0..2] → arr[2] share karte hain → overlap → UB.

Naive front-to-back: arr[2]=arr[0]=1, arr[3]=arr[1]=2, arr[4]=arr[2]=1(!) → {1,2,1,2,1} (arr[2] pe write ne baad ki read ko corrupt kar diya).
Vectorized (pehle block {1,2,3} read karo, phir store karo): {1,2,1,2,3}. Ek hi source line se do alag answers — yeh restrict pe rely karne ka visible symptom hai jab woh false ho. Isi liye memcpy overlap pe undefined hai jabki memmove safe hai.

Exercise 3.3

Ek student likhta hai:

void f(int * restrict p) {
    int *q = p;      // q derived from p
    *p = 1;
    *q = 2;          // (A)
    int *r = get_other_path();  // NOT derived from p
    *r = 3;          // (B) r happens to point at the same object as p
    printf("%d", *p);
}

Kaun sa access, (A) ya (B), restrict promise violate kar sakta hai?

Recall Solution

(B) violate karta hai; (A) theek hai. Promise allow karta hai access through p aur un pointers ke through jo p se derived hain — q = p derived hai, isliye *q legal hai. Lekin r us object tak alag, non-derived path se pahunchta hai; r ke through object ko touch karna guarantee tod deta hai ki "yeh object sirf p ke through reach hota hai." Dekho Pointer aliasing.

Level 4 — Synthesis

Exercise 4.1

Ek safe API design karo. Tumhe ek function likhna hai jo do vectors ko ek teesre mein add kare, lekin tum chahte ho ki yeh tab bhi usable ho jab caller result ko input ke upar likhta ho (c equal ho sakta hai a ke). Kya output pointer restrict hona chahiye? Signature do aur justify karo.

Recall Solution

void vadd(int *c, const int * restrict a, const int * restrict b, int n) {
    for (int i = 0; i < n; i++) c[i] = a[i] + b[i];
}

a aur b read-only hain aur (maano) jaane-maane disjoint hain → const ... restrict.
c restrict nahi hai, kyunki caller ko c == a pass karna allowed hai. Element-wise c[i]=a[i]+b[i] tab bhi safe hai jab c a ko alias kare, kyunki har c[i] apna a[i] read hone ke baad likha jaata hai aur koi doosra index touch nahi hota. c ko restrict mark karna us legal, useful call ko forbid kar deta. Qualifier ko sachchi contract se match karo, speed ki chahat se nahi.

Exercise 4.2

Parent note ke disjointness rule ka use karke explain karo ki memcpy(dst, src, n) (jo dono parameters ko restrict declare karta hai) overlapping ranges ke liye undefined kyun hai lekin memmove nahi — aur memcpy(dst, src, n) ke liye disjointness condition addresses pe inequality ke roop mein likho.

Recall Solution

memcpy ka prototype hai void *memcpy(void * restrict dst, const void * restrict src, size_t n);. Do restrict qualifiers assert karte hain ki dst aur src disjoint byte ranges name karte hain. Formally, addresses ko integers maanke, safe condition hai: $(dst + n \leq src) \lor (src + n \leq dst)$ matlab ek block doosre ke shuru hone se pehle khatam ho jaata hai. Agar dono mein se koi hold nahi karta, ranges overlap karte hain aur memcpy UB hai. memmove restrict chhod deta hai, isliye woh koi disjointness promise nahi karta; woh internally safe copy direction choose karta hai aur kisi bhi overlap ke liye defined hai. Dekho memcpy vs memmove.

Level 5 — Mastery

Exercise 5.1

Predict aur count karo. Consider karo:

void saxpy(float * restrict y, const float * restrict x, float a, int n) {
    for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i];
}

n = 4 ke liye, ek optimizing compiler ko memory se a ke kitne loads chahiye, aur kitne non-restrict, non-const version ke liye worst case mein jahan use darr ho ki y a ki storage ko alias kare? (a ek value hai jo register mein pass hoti hai, lekin ek naive model assume karo jo ise spill kare.) Focus karo x reloads pe: aliased worst case mein, already-computed y values ke kitne extra reloads loop mein forced hote hain? Dono versions ke liye y-writes aur x-reads ka count do.

Recall Solution

a dono versions mein ek scalar parameter hai jo register mein hai — yeh ek baar load hota hai regardless (0 reloads); yeh x/y ke through addressable nahi hai, isliye arrays ki aliasing ise touch nahi karti. Meaningful difference array accesses ka ordering aur vectorization hai, a count nahi. n = 4 ke liye array traffic count karna:

x-reads: dono versions mein 4 (har element ke liye ek — tumhe har x[i] chahiye hi).
y-writes: dono versions mein 4 (har element ke liye ek).
restrict version inhe 1 vector load of x aur 1 vector store of y (4 lanes each) mein batch kar sakta hai aur freely reorder kar sakta hai; non-restrict version ko strictly interleaved aur ordered rakhna padta hai (load x[i], load y[i], store y[i], next i) kyunki y[i] pe store ek not-yet-read x ko change kar sakta hai. Numeric summary: x-reads = 4, y-writes = 4 (dono versions); vector-instruction count restrict version mein 8 scalar ops se 2 vector ops pe aa jaata hai.

Exercise 5.2

Dono copy orders ke neeche full trace. Array int a[6] = {10,20,30,40,50,60};. Exercise 3.1 ke restrict copy ko copy(a, a+1, 5) (ek left shift) ke roop mein call karo. Kya regions overlap karte hain? Front-to-back aur back-to-front copy orders ke liye result do, aur batao ki ek correct memmove kaun sa pick karta.

Recall Solution

dst = a[0..4], src = a[1..5] → woh bahut zyada overlap karte hain → restrict promise jhooth hai → UB.

Front-to-back (i = 0..4): har a[i] = a[i+1] pehle hi hota hai jab a[i+1] overwrite nahi hua, isliye: {20,30,40,50,60,60} — correct left-shift! (front-to-back left shift ke liye safe hai).
Back-to-front (i = 4..0): a[4]=a[5]=60, a[3]=a[4]=60(!), a[2]=a[3]=60, a[1]=a[2]=60, a[0]=a[1]=60 → {60,60,60,60,60,60} — corrupt. Ek correct memmove detect karta hai dst < src aur front-to-back copy karta hai, deta hai {20,30,40,50,60,60}. Kyunki humara restrict copy legally koi bhi order pick kar sakta hai, hum iske upar rely nahi kar sakte — yahi poora lesson hai.

Exercise 5.3

Synthesis check. Ek paragraph mein, chaar ideas ko connect karo: (i) worst-case aliasing assumption, (ii) restrict ek promise ke roop mein, (iii) toote hua promise pe undefined behaviour, (iv) kyun const akela yahan compiler ki madad nahi karta.

Recall Solution

Ek compiler do ordinary pointers dekh ke worst case assume karta hai — woh alias kar sakte hain — isliye woh defensive reloads insert karta hai aur reorder karne se inkaar karta hai, vectorization khatam. restrict ek programmer ka promise hai ki ek given pointer uski memory ka akela path hai, jo us worst-case darr ko mita deta hai aur SIMD unlock karta hai. Lekin compiler promise kabhi check nahi karta, isliye agar regions truly overlap karte hain toh tumhe undefined behaviour milta hai — galat results jo sirf optimization ke waqt dikhte hain. const substitute nahi kar sakta: const promise karta hai "main yahan write nahi karunga," jo kuch nahi kehta ki koi aur pointer yahan write kare ya nahi; aliasing ki chinta doosre pointers ke baare mein hai jo data ko touch karte hain, jise sirf restrict (ya C99 ki restrict semantics) address karta hai.

Connections

Pointers in C
const qualifier
Pointer aliasing
memcpy vs memmove
Compiler optimization & vectorization (SIMD)
Undefined behaviour in C
C99 standard features