False sharing problem: Visual walkthrough — Hinglish deep dive

6.1.10 · D2 · Hardware › Parallelism & Multicore › False sharing problem

Yahan kuch bhi assume nahi kiya gaya. Agar tumne kabhi "cache line", "core", ya symbol $⌊ \cdot ⌋$ nahi dekha, toh use use karne se pehle introduce kiya jaayega.

Step 1 — Memory ek lamba ruler hai bytes ka

KYA HAI. Computer ki memory chhote numbered boxes ki ek badi row hai. Har box ek byte (8 bits, ek chhote number ya ek letter ke liye kaafi) rakhta hai. Box par likha number uska address hai. Hum addresses hexadecimal (base 16) mein 0x ke saath likhte hain — toh 0x1000, 0x1001, 0x1002, … teen boxes hain jo ek saath side by side baithe hain.

KYUN. False sharing ki har baat isi se aati hai ki kaun se boxes kis ke paas baithe hain. Isliye sabse pehle humein memory ko ek seedha ruler ki tarah dikhna chahiye jahan har byte ki ek jagah ho. Abhi koi triangles ya protocols nahi — bas ruler.

PICTURE. Neeche, ruler left se right chalta hai. Do variables counter[0] aur counter[1] 4-byte integers hain. Notice karo ki ye bilkul ek ke baad ek hain — counter[1] theek wahin se shuru hota hai jahan counter[0] khatam hota hai.

Step 2 — Hardware kabhi ek byte nahi move karta; poori line move karta hai

KYA HAI. CPU kabhi memory se apne fast local storage (cache) mein ek single byte fetch nahi karta. Wo hamesha ek fixed-size chunk uthata hai jise cache line kehte hain. Almost har modern machine par wo chunk $L = 64$ bytes ka hota hai.

KYUN. 64 bytes ek saath fetch karna per byte sasta hai bajaaye 64 alag trips ke (memory bulk moves pasand karti hai, aur paas ka data usually saath mein chahiye hota hai). Ye ek acchi bet hai — lekin ye exactly wahi bet hai jo false sharing mein ulti pad jaati hai. Transfer ki unit ka ek variable se bada hona is poore problem ka beej hai.

PICTURE. Ab hum ruler ko 64 bytes ke blocks mein group karte hain. Dono counters ek hi shaded block ke andar aate hain. Wo single shaded block woh cache line hai jise hardware ek indivisible unit ki tarah treat karta hai.

Dekho Cache line size and alignment ki 64 kahan se aata hai.

Step 3 — Koi address kis line mein hai? Floor function se milte hain

KYA HAI. Ye decide karne ke liye ki do variables ek hi cache line mein hain ya nahi, hum har address ke liye ek line number calculate karte hain. Address ko $L$ se divide karo aur fractional part fenko. Fractional part phenk dena wahi hai jo symbol $⌊ x ⌋$ (floor) matlab rakhta hai: nearest whole number ki taraf neeche round karo.

KYUN. Humein ek yes/no test chahiye — "same line hai ya nahi?" — aur jo cheez matter karti hai wo hai ki tum 64-byte ke kaunse block mein ho, andar kahan ho nahi. 64 se divide karke floor karna ek block ke har address ko same integer par collapse kar deta hai. Wo integer us block ki identity hai.

PICTURE. Addresses ki number line 64-unit ki bins mein split hai. Ek bin mein har address same line number par map hota hai. Dekho kaise dono counters line number 64 par collapse hote hain.

Worked check. counter[0] at 0x1000 = 4096. counter[1] at 0x1004 = 4100. $⌊ \frac{4096}{64} ⌋ = ⌊ 64.0 ⌋ = 64, ⌊ \frac{4100}{64} ⌋ = ⌊ 64.06 ⌋ = 64.$ Same line number ⇒ collision hai.

Step 4 — Sirf ek core own kar sakta hai dirty line (MESI rule)

KYA HAI. Jab kai cores ek hi cache line ki copies rakhte hain, ek protocol unhe honest rakhta hai. Common wala hai MESI, jo un chaar states ke naam par hai jismein ek line per core ho sakti hai: Modified, Exclusive, Shared, Invalid. Humein jo ek rule chahiye: ek line ek time par sirf ek core mein Modified state mein ho sakti hai.

KYUN. Agar do cores dono ek modified copy rakh sakein, toh unke edits disagree karenge aur memory corrupt ho jaayegi. Write karne ke liye, ek core ko pehle khud sole owner banana hoga — matlab har doosre core ko bolna "apni copy phenk do" (ise Invalid set karo). Wo announcement expensive part hai.

PICTURE. Do cores, ek shared line. Core 0 write karna chahta hai, toh wo Core 1 ko ek invalidate broadcast karta hai; Core 1 ki copy dark ho jaati hai (Invalid). Ab Core 0 akele Modified line hold karta hai.

Full state machine Cache coherence protocols mein hai.

Step 5 — Ping-pong: do owners hamesha ladte hain

KYA HAI. Step 3 aur 4 ko saath rakh lo. Core 0 counter[0] likhta hai; Core 1 counter[1] likhta hai; wo same line hain. Toh har write doosre core ko ownership chhodni pad ti hai. Ownership aise uchhalti rehti hai jaise ping-pong ball, even though dono cores alag bytes touch karte hain aur koi logical data share nahi karte.

KYUN. Hardware nahi dekh sakta ki byte 4096 aur byte 4100 unrelated hain. Use bas dikhta hai "kisi ne line 64 mein likha". Correctness (Step 4) har write par poora invalidation force karta hai. Alag variables, same line ⇒ har iteration par poora coherence cost.

PICTURE. Ek timeline. Har core ka write line ka owner badal deta hai aur doosri taraf invalidate arrow bhejtaa hai. Pattern kabhi settle nahi hota.

Isliye "maine zyada cores add kiye aur wo slow ho gaya" hota hai — dekho Multicore scaling.

Step 6 — Fix: har variable ko apni line mein dhakel do (padding)

KYA HAI. Hum $L$ nahi badal sakte; hardware use 64 bytes par fix karta hai. Toh instead hum har core ke variable ko dead filler bytes add karke poori line khud fill kara dete hain — padding — uske baad. Tab Step 3 ka floor test do variables ke liye fail ho jaata hai, aur koi line kabhi share nahi hoti.

KYUN. Yaad karo collision purely $⌊ A_{0} /64 ⌋ = ⌊ A_{1} /64 ⌋$ se aayi thi. Agar hum addresses ko kam se kam 64 apart aur line-aligned force karein, toh dono floor values alag honge, aur ladne ke liye kuch nahi bachega. Hum wasted memory (padding) ka daam chukate hain cycles wapas paane ke liye.

PICTURE. Wahi do counters, lekin ab har ek apne 64-byte block ke shuru mein baitha hai aur uske peeche 60 bytes ka grey padding hai. Line numbers ab 64 aur 65 hain — alag bins, koi invalidations nahi.

Numeric check. Padded counters 0x1000 (=4096) aur 0x1040 (=4160) par: $⌊ \frac{4096}{64} ⌋ = 64, ⌊ \frac{4160}{64} ⌋ = 65 \Rightarrow alag lines. Fix ho gaya.$

C++17 mein compiler tumhe sahi pad size std::hardware_destructive_interference_size ke through alignas ke saath batata hai. Dekho Memory allocators ki kaise allocators tumhe under- ya over-align kar sakte hain.

Step 7 — Degenerate cases (taaki kuch surprise na kare)

KYA HAI & KYUN. Ek acchi derivation ko boundaries cover karni chahiye, sirf sundar middle nahi. Chaar edge cases:

Dono variables same byte range mein hain lekin sirf read hote hain (kabhi write nahi). Writes nahi ⇒ invalidations nahi ⇒ MESI line ko dono caches mein hamesha ke liye Shared chhod deta hai. Koi false sharing nahi. False sharing ek write problem hai.
Ek writer, bahut saare readers. Single writer baar baar ownership leta rehta hai, readers ko refetch karne par majboor karta hai. Isme cost hai — ye ek line ka "true-ish" sharing hai — lekin ye Step 5 ka symmetric ping-pong nahi hai.
Variables alag lines mein luck se land karte hain ( $⌊ A_{0} /64 ⌋ \neq = ⌊ A_{1} /64 ⌋$ already). Koi fix nahi chahiye. Padding sirf memory waste karega.
Ek single variable ek line boundary par straddle karta hai (uske bytes do lines mein faile hain). Tab wo dono neighbouring lines ke owners se collide karta hai. Alignment (alignas) ise rok deta hai ise cleanly start kara ke.

PICTURE. Charon cases side by side: do grey (read-only), ek asymmetric (ek writer), ek already-separated, aur ek straddling. Sirf symmetric two-writer, same-line case hi true false-sharing villain hai.

Atomics yahan tumhe nahi bachaate: Atomic operations correctness guarantee karte hain lekin tumhe padded aur atomic layout chahiye — aur Lock-free data structures exactly is padding par rely karte hain scale karne ke liye.

Ek-picture summary

Ek frame mein har idea: ruler → 64-byte line → floor test → ownership rule → ping-pong → padded fix.

Recall Feynman retelling — plain words mein wapas bolo

Memory numbered boxes ki ek lambi row hai. CPU aalsand hai aur kabhi ek box nahi uthata; wo ek saath 64 boxes ki tray uthata hai — woh tray hai ek cache line. Ye jaanne ke liye ki do variables ek hi tray par hain, har address ko 64 se divide karo aur neeche round karo; equal answers matlab same tray. Ab safety rule: sirf ek core ek tray par ek waqt likhta reh sakta hai, toh likhne se pehle ek core chillata hai "baaki sab, apni copy faad do!" — woh chillana slow hai. Agar do cores apne alag variables ek hi tray par rakhein aur dono likhte rahein, toh wo baar baar chillate rahenge aur ek doosre ki copies faadte rahenge, chahe wo alag boxes touch kar rahe hon. Wahi hai false sharing — aur ye code ko 50–100× slow kar sakta hai. Ilaaj: har core ke variable ko apni poori tray do, uske peeche 60 junk bytes thoos ke (padding), taaki unke divide-by-64 answers alag hon aur kisi ko kabhi chillana na pade. Bas yaad rakho: villain sirf tab aata hai jab cores write karte hain; read-only trays kabhi nahi ladtey.

Recall Test yourself

Kya 4096 aur 4100 addresses par do ints ek 64-byte line share karte hain? ::: Haan — floor(4096/64)=64 aur floor(4100/64)=64, same line number. False sharing hone ke liye kaunsa ek operation zaroori hai? ::: Concurrent write — reads akele line ko Shared chhod dete hain, koi invalidations nahi. Hardware "dekh" kyun nahi sakta ki variables independent hain? ::: Coherence line granularity par kaam karta hai; use sirf pata hai ki ek 64-byte block mein kuch likha gaya, kaunse byte mein nahi. Ek 4-byte int ko 64-byte line khud rakhne ke liye kitna filler chahiye? ::: 60 bytes of padding (4 + 60 = 64). Padding ke baad dono counters safe kyun hain? ::: Unke addresses ab ≥64 ke difference par hain aur line-aligned hain, toh unke floor-divided line numbers alag hain (64 vs 65).