Tracing Garbage Collection — mark-sweep থেকে generational পর্যন্ত

আগে এটা বুঝি

গত লেসনে আমরা tracing GC-কে black box রেখেছিলাম: “collector চলল, unreachable মুছে গেল।” এই একটা বাক্যের ভেতরে লুকানো আছে দুইটা গভীর প্রশ্ন, আর আজকের পুরো লেসন সেই দুইটাই:

প্রশ্ন ১: Collector কীভাবে জানে কোন object dead?

সোজা উত্তরটা বিভ্রান্তিকরভাবে অসম্ভব। “কোন object আর কখনো ব্যবহার হবে না” — এটা ভবিষ্যৎ সম্পর্কে প্রশ্ন, আর ভবিষ্যৎ predict করা যায় না (halting problem-ঘেঁষা)। তাই প্রতিটা tracing collector একটা সুচতুর substitution করে: liveness-এর বদলে reachability মাপে। যে object-এ root থেকে reference chain দিয়ে পৌঁছানো যায় না, সে আর পৌঁছানোও যাবে না — মানে ব্যবহারও হবে না। Dead detection না, survivor detection।

প্রশ্ন ২: জরিপটা কখন, কীভাবে চালানো হয় — যাতে পুরো heap traverse করা সত্ত্বেও প্রোগ্রাম ধীর না লাগে?

এই প্রশ্নের উত্তরের ইতিহাসই ৬০ বছরের GC evolution: mark-sweep (1960) → copying (1970) → generational (1984) → concurrent/incremental (আজকের G1, ZGC, Shenandoah)। প্রতিটা ধাপ আগেরটার একটা নির্দিষ্ট ব্যথার জবাব।

আজকের শেষে আপনি theory শুধু পড়বেন না — নিজের C কোডে একটা কাজ করা mark-sweep collector লিখবেন, আর Go/Python-এ নিজের চোখে collection pause মাপবেন।

মূল ধারণা

Root set — জরিপের শুরুর ঠিকানাগুলো

Reachability মানে “root থেকে পৌঁছানো যায়”। তাহলে root কারা? Root হলো সেই সব reference যেগুলো heap-এর বাইরে থেকে heap-এর ভেতরে আঙুল দেখাচ্ছে:

Root	কোথায় থাকে	কে scan করে
Global variable	Data segment	Collector, শুরুতে
প্রতিটা thread-এর call stack	Stack segment	Stack walk — প্রতিটা frame-এর pointer slot
CPU register	Register file	JIT/compiler-generated maps (conservative বা exact)
Explicit handle table	Runtime metadata	JNI handle, JS handle scope

লক্ষ্য করুন এই তিনটা জায়গাই আপনার চেনা — process address space-এর text/data/stack/register layout, operating-systems/process-anatomy লেসনে দেখা। আর Register-এ বসে থাকা pointer-গুলো scan করা সবচেয়ে কঠিন: interpreter/JIT-কে compiler-কে বলে রাখতে হয় কোন register-এ কখন pointer আছে (exact rooting), নাহলে raw integer-ও pointer ভেবে conservative scan করতে হয়।

Roots (heap-এর বাইরে)          Heap (reference graph)
┌──────────────┐
│ globals      │──────────┐
├──────────────┤          ▼
│ thread stack │──────► [A] ──► [B] ──► [C]
├──────────────┤           │              ↑
│ registers    │───┐       └────► [D]      │
└──────────────┘   │               ↑       │
                   └──────────────►[E] ────┘
                                    (E→C cycle)

Live: A B C D E — সবাই কোনো না কোনো root থেকে reachable।

একটা object যদি শুধুমাত্র cycle-এর ভেতর থেকে reach করা যায়, কিন্তু কোনো root থেকে না — সে dead। E আর C একে অপরকে point করলেও, root-দের কেউ ওই cluster-এ ঢুকতে না পারলে দুটোই reclaimable। এটাই tracing-এর RC-র উপর মৌলিক জয় (লেসন ৮-এ ফিরে আসবে)।

Tri-color marking — traversal-এর abstract ভাষা

Marking phase-কে বর্ণনার universal ভাষা হলো tri-color model। প্রতিটা object তিন রঙের একটায়:

White: এখনো দেখা হয়নি। Mark phase শেষে যারা white, তারাই garbage।
Grey: নিজে live চিহ্নিত, কিন্তু তার children এখনো ঘাঁটা হয়নি — worklist-এ আছে।
Black: নিজে এবং সব direct children scan-complete।

Algorithm মাত্র দুইটা নিয়মে চলে:

১. প্রতিটা root-কে grey করো (worklist-এ push)
২. worklist খালি না হওয়া পর্যন্ত:
     একটা grey বেছে নাও, তার সব white child-কে grey করে
     নিজেকে black করো

শেষে: black = live, white = garbage, grey = কেউ না

Strong tri-color invariant — আজকের সবচেয়ে গুরুত্বপূর্ণ এক লাইন

Black object-এর কোনো direct reference white object-কে point করবে না। Stop-the-world collector-এ এটা automatic — mutator (আপনার প্রোগ্রাম) তো চলছেই না। কিন্তু concurrent collector-এ mutator আর collector একসাথে চলে; এই invariant ভাঙলে (black → white edge তৈরি হলে) একটা genuinely live object white-ই থেকে যেতে পারে আর sweep-এ মুছে যেতে পারে — data loss। এই ভাঙন ঠেকাতেই দুইটা কৌশল: write barrier (mutator-এর প্রতিটা pointer-store-এ collector কাজ করে — যেমন white target-কে grey করে দেওয়া) আর read barrier। Generational collector-এর remembered set-ও একই write barrier-এর আত্মীয় — একটু পরে দেখব।

Mark-sweep — প্রথম প্রজন্ম

McCarthy-র Lisp (1960) থেকে সরাসরি আজও ব্যবহৃত। দুই phase:

Mark: root থেকে graph traverse, প্রতিটা visited object-এ bit সেট।
Sweep: পুরো heap linear scan — marked bit clear করে unmarked-দের free-list-এ ফেরত পাঠাও।

সুবিধা: object move হয় না (pointer identity অটুট), সব ভাষার সাথে খাপ খায়। দাম:

Fragmentation: free chunk-গুলো ছোট ছোট টুকরোয় ছড়িয়ে থাকে — মোট ফাঁকা জায়গা যথেষ্ট থেকেও বড় allocation fail করতে পারে। Build section-এ এটা চোখে দেখবেন।
Pause ∝ পুরো heap: mark-ও sweep-ও heap size-এর সরলরেখায়। Heap 10 GB মানে sweep মানে 10 GB walk — stop-the-world-এ।

Mark-copy — দ্বিতীয় প্রজন্ম

Cheney (1970): heap-কে দুই সমান semispace-এ ভাগ করো। একসময় মাত্র একটায় allocation হয়; GC-র সময় live object-গুলো অন্য semispace-এ copy করে পাশাপাশি compact করে সাজাও, তারপর দুই space-এর ভূমিকা flip।

Before GC:                        After GC:
From-space        To-space        From-space       To-space
[A][B][C][D][E]   (empty)         (garbage)        [A][C][E]↑compact
    ↑ live: A,C,E                                  (allocation resumes)
    D,B dead

Copy-র সময় প্রতিটা object-এ forwarding pointer বসে — পুরনো address পাওয়া গেলে নতুন address দেখিয়ে দেয়, তাই সব internal pointer fix হয়ে যায় (scan একবারই, Cheney-র breadth-first worklist: from-space-এ scan করতে করতে to-space-এ copy)।

দুইটা বিস্ময়কর সুবিধা, একটা দাম:

Allocation হয় bump pointer-এ — free-list নেই, সবচেয়ে দ্রুত possible allocation।
Live data compact হয়ে পাশাপাশি বসে — locality উন্নত, cache-line বন্ধনীতে আত্মীয়রা একসাথে।
দাম: অর্ধেক memory সবসময় খালি বসে থাকে, আর copy cost ∝ live data। Heap-এর ৯০% dead হলে দারুণ সস্তা; ৯০% live হলে বিপদ।

Generational collection — empirical বুদ্ধি

Lieberman-Hewitt (1983) আর Ungar (1984) দুইটা empirical observation-এ ভর করে জিজ্ঞেস করলেন: পুরো heap প্রতিবার কেন ঘাঁটব?

Weak generational hypothesis:

Infant mortality: বেশিরভাগ object খুব অল্প বয়সেই মরে। টাইপিক্যাল measurement-এ allocation-এর প্রায় ৯০% প্রথম collection-এই garbage হয় — temporary string, iterator, parse node।
Old references young হয় বিরল: পুরনো object-এ নতুন object-এর pointer store করা বিরল ঘটনা।

Design: heap দুই age-group-এ ভাগ —

┌────────────────────────────┬──────────────────────────────┐
│ Young/Nursery (eden+suv.)  │ Old/Tenured                  │
│ ছোট, প্রায়ই collect (minor)│ বড়, কালেভদ্রে collect (major) │
│ copying collector — দ্রুত  │ mark-sweep/compact           │
└────────────────────────────┴──────────────────────────────┘
        │ survivors N-বার বেঁচে থাকলে "promote" ↓

Minor collection nursery-কে copying-এ পরিষ্কার করে — খরচ ∝ nursery-এর live data, যা hypothesis অনুযায়ী খুবই ছোট। তাই minor GC মিলিসেকেন্ড-স্তরে, ঘন ঘন। Major collection old generation-এর, কালেভদ্রে।

কিন্তু একটা ফুঁ: old object যদি nursery-এর কোনো object-কে point করে? Nursery-only traversal-এ সেই child live ধরা হবে না! Solution দুইটা মিলে:

Remembered set: old→young প্রতিটা pointer-এর রেকর্ড, যাতে minor collection-এ সেই old object-গুলোকেও root-এর মতো scan করা যায়।
Write barrier: এই set maintain করতে compiler প্রতিটা pointer store-এ ছোট্ট check বসায়: “old-gen object-এ কি young-gen address লিখলে?” হ্যাঁ হলে entry log। Mutator সারাজীবন এই tax দেয় — সাধারণত কয়েক instruction, কিন্তু প্রতি store-এই।

Roots ──► Nursery objects ┐
                          ├─► minor GC scan এই দুই উৎস থেকেই
Old gen ──(old→young ptr)─┘
   │
   └─ write barrier ধরে রেকর্ড করেছে কোন old object-এ young
      pointer লেখা হয়েছে → সেগুলোই remembered set-এ

Minor GC খরচ ≈ f(nursery-এর LIVE data + remembered set size)
             ≠ f(মোট heap) ← এটাই পুরো magic

Minor GC-এর traversal কোথা থেকে শুরু হয় — remembered set হলো old→young edges-এর 'ঋণের খাতা'।

Pause — কেন stop-the-world ব্যথা দেয়

Marking-এর সময় object graph বদলালে (mutator চললে) tri-color invariant ভাঙার ঝুঁকি — তাই সবচেয়ে সহজ সমাধান: সব thread থামাও (STW)। কিন্তু থামার সময়টাই সমস্যা:

Web service: 200 ms pause মানে SLA breach, timeout cascade।
Trading/HFT: এক ms-ও মাফ নেই।
UI/game: 16 ms frame budget — 50 ms pause মানে dropped frames।

Modern collectors-এর পুরো গল্প এই pause ছোট করা:

Collector (JVM)	Strategy	Typical pause
Parallel GC	STW multi-threaded	শত শত ms
G1	Region-based, incremental, concurrent marking	~10–200 ms (target-settable)
ZGC	Concurrent, colored pointers, read barrier	sub-ms
Shenandoah	Concurrent compaction, Brooks pointer	sub-ms
Go runtime	Concurrent mark-sweep, write barrier	sub-ms typical

গণিতটা মনে রাখুন: pause ∝ যে কাজ STW-তে হয়। Incremental/concurrent collector সেই কাজ ছোট ছোট slice-এ ভাগ করে mutator-এর মাঝে ফিট করায় — দাম হলো write/read barrier overhead আর মোট throughput সামান্য কমা।

একটা major GC-র ভেতর থেকে — mark-sweep-compact pipeline

Initial marker (STW)সব thread থামো, roots scan করে grey করো — milliseconds-এর কাজ, এটাই unavoidable pause-এর মূল অংশ।
Concurrent markingApplication চলতে চলতে grey worklist শেষ করো; write barrier mutator-এর নতুন pointer-গুলোর হিসাব রাখে invariant রক্ষায়।
Remark (STW)ছোট final pass — barrier-এর জমা পরিবর্তনগুলো reprocess করে চূড়ান্ত black/white সীমানা টানো।
Sweep / CompactWhite-দের free করো; compacting collector হলে live-দের এক প্রান্তে সরিয়ে fragmentation মুছে দাও (এটাই সবচেয়ে দামি ধাপ, প্রায়ই concurrent করা হয়)।

ভেতরে কী ঘটছে

Tri-color invariant — concurrent world-এ যেখানে সব ভাঙে

এতক্ষণ আমরা marking-টা single-threaded কল্পনা করেছি। কিন্তু বাস্তব server-এ pause কমাতে collector application thread-এর পাশাপাশি চলে — মানে marking চলাকালীনই mutator (আপনার program) object graph বদলাচ্ছে। এখানেই দুইটা ভয়ংকর race জন্মায়:

১. Lost object: mutator একটা black object-এর field বদলে সেটাকে white object-এ point করাল, আর ওই white-টার একমাত্র reference হারিয়ে গেল। Collector black-কে আর rescan করবে না → live object সাদা থেকে sweep হয়ে যাবে — memory corruption, crash নিশ্চিত।

২. Floating garbage: mutator black object-এর pointer মুছে ফেলল, কিন্তু collector সেই object already grey/black করে ফেলেছে — এই cycle-এ dead object survive করে। এটা correctness ভাঙে না, শুধু জায়গা নষ্ট করে — acceptable trade-off।

প্রথমটা ঠেকাতে collector-দের হয় মার্কিং-এর সময় mutator-কে সীমাবদ্ধ রাখতে হয়, নয়তো barrier বসাতে হয়:

Barrier	নিয়ম	ধর্ম
Dijkstra (incremental update)	নতুন pointer store হলে destination-কে grey করো	Strong invariant ধরে
Steele	Destination black হলে re-scan trigger করে source-ও grey করো	কম floating garbage
Yuasa (SATB)	Overwrite-এর পুরনো value-কে grey করো	Snapshot-at-the-beginning — mark শুরুর moment-এর reachable set

black A ──store──▶ white B     (B-এর পুরনো ref C-কে point করত)
Dijkstra/Yuasa barrier: B (নতুন) বা C (পুরনো) grey হয়ে যায় —
                         দুই-ই না করলে একটা path চিরতরে হারাতে পারে

Generational collector-এ আরেকটা barrier চলে: generational write barrier। Minor GC-তে roots = stacks+globals+old→new pointer। কিন্তু প্রতিটা store check করা দামি — তাই JVM card table ব্যবহার করে: heap-কে 512-byte card-এ ভাগ করে একটা byte array; old-space-এ pointer store হলে শুধু সেই card-কে dirty mark করে (একটা mov)। Minor GC শুধু dirty card গুলো scan করে — O(dirty cards), O(heap) না।

Cheney semispace copying — ভেতরে ঠিক কী ঘটে

Copying collector fragmentation-এর সমস্যাটাই মুছে দেয় কারণ সে allocate-ই করে না — সরায়। Semispace ডিজাইনে heap দুইভাগ: from-space (এখন বসবাস) আর to-space (খালি)।

from-space                    to-space
┌──────────────┐             ┌──────────────┐
│A B C D E F   │   roots ──▶ │A B ▼         │  ◀ free ptr
│  ↑    ↑      │  ═══copy══▶ ││ │           │  ◀ scan ptr
│  └────C       │             └──────────────┘
│ (D,E,F dead?)│              scan==free হলে মার্কিং শেষ
└──────────────┘

Algorithm-টা BFS, কিন্তু queue-টা to-space নিজেই:

Root-এর সব object to-space-এ copy করো, from-space-এর জায়গায় forwarding pointer বসাও (“আমি এখন to-space-এর X-এ”)।
scan pointer থেকে free pointer পর্যন্ত object-গুলো একে একে process করো — প্রতিটা field-এর জন্য target copy হয়ে গেলে forwarding pointer থেকে নতুন address বসাও, না হলে এখনই copy।
scan == free হলে সব reachable object copied — from-space পুরোটা একসাথে recycle। Allocation এরপর bump-pointer: free += size।

লক্ষ্য করুন sweep নামে কোনো phase-ই নেই — dead object গুলোকে কিছুই করা হয় না, পুরো space ফেলে দেওয়া হয়। Cost: মেমরির অর্ধেক সবসময় খালি থাকে (space overhead 2×), বিনিময়ে allocation হয় free += size মাত্র — এর চেয়ে দ্রুত general-purpose allocation প্রায় অসম্ভব, আর surviving object গুলো compact হয়ে cache locality ও বুস্ট করে (computer-architecture/cache-organization লেসনের সেই spatial locality কথাটা মনে আছে?)।

উদাহরণ

একটা ছোট graph-এর পূর্ণ mark-sweep trace

Heap-এ ছয়টা object, root দুইটা (g global আর stack-এ p):

roots: g ──► A ──► B ──► C
       p ──► D          │
                        ▼
                        E ──► F        (F-এর দিকে আর কেউ না)

Initial:  A B C D E F সব white

Phase 1 — mark: g আর p grey হয়, তারপর wavefront propagate:

step 0: grey={g,p}                    white={A..F}
step 1: g→A grey, p→D grey            grey={A,D}   g,p→black
step 2: A→B grey                      grey={B,D}   A→black
step 3: B→C,E grey                    grey={C,D,E} B→black
step 4: C→F grey                      grey={D,E,F} C→black
step 5: D-র children নেই              grey={E,F}   D→black
step 6: E-র children নেই (F already grey)
step 7: F→black                       grey={} — মার্কিং শেষ

Phase 2 — sweep: পুরো heap linear scan। এই উদাহরণে সবাই live — কিন্তু যদি p stack থেকে pop হয়ে যেত (return), D orphan হতো, আর sweep তাকে free-list-এ ফেরত দিত:

p নেইলে:  white={D}, sweep frees D
heap:     [A][B][C][E][F][ . D . ]   ← মাঝখানে ফাঁক = fragmentation শুরু

এখন malloc(2×sizeof(D)) জাতীয় contiguous request D-র ফাঁকে ঢুকতে পারবে না — মোট ফাঁকা যথেষ্ট থেকেও। এটাই non-moving collector-এর জন্মগত রোগ, এবং compacting/copying design-এর মূল প্রেরণা।

ছবিতে

Semispace flip আর generational lifecycle — দুইটা মানচিত্র

Cheney semispace — এক collection-এর পুরো জীবন্ত চিত্র:

                FROM-SPACE                     TO-SPACE
alloc ptr ──►  ┌─────────────────┐           ┌─────────────────┐
               │ A B C D E F ... │  ─copy──► │ A C E | scanptr │
               └─────────────────┘           └────────▲────────┘
                 live: A C E                          │
                 dead: B D F (কখনোই ছোঁয়া হয় না!)      │
                                                      │
Cheney loop: scanptr থেকে একে একে object পড়ো, তার children-
pointer-গুলো forward করো (প্রথম visit-এ copy, পরে forwarding ptr),
scanptr বাড়াও। scan == copy শেষ হলে flip:

               FROM(old garbage)  ⇄  TO(new home, bump-ptr ready)

Generational journey — একটা object-এর সম্ভাব্য জীবন:

eden ──minor GC 1──► survivor ──minor GC N──► tenured (old gen)
  │                     │                        │
  90% এখানেই মরে        কিছু মরে                  কালেভদ্রে major GC
                        (age counter বাড়ে প্রতি survive-এ)
                                                 │
old→young pointer হলে ◄── write barrier ────────┘
remembered set-এ entry

নিজে চালিয়ে দেখুন

EXPERIMENT

নিজের চোখে GC — Go-তে pause, Python-এ generation counts

Linux/macOS, Go ≥1.18 ও Python 3 ইনস্টল থাকলে দুটোই; একটা হলেও চলবে· ১৫ মিনিট

ধাপ ১ — Go-তে churn (সব short-lived):

// churn.go — ২০০ MB garbage, দ্রুত জন্মে দ্রুত মরে
package main

import "fmt"

func main() {
    var sink byte
    for i := 0; i \< 50; i++ {
        buf := make([]byte, 4*1024*1024) // 4 MB, iteration শেষেই dead
        buf[0] = byte(i)
        sink = buf[0]
    }
    fmt.Println(sink)
}

GODEBUG=gctrace=1 go run churn.go

Typical output (সংখ্যা machine-ভেদে বদলাবে):

gc 1 @0.052s 2%: 0.42+2.1+0.021 ms clock, ...
gc 2 @0.089s 2%: 0.51+3.3+0.024 ms clock, ...
gc 3 @0.128s 2%: 0.48+3.9+0.022 ms clock, ...
done

প্রতিটা লাইন একটা GC: gc N @T X%: — X হলো GC-তে খরচ করা মোট CPU-র শতকরা অংশ, আর +...+... ms এর প্রথম/শেষ সংখ্যা দিয়ে wall-clock pause অনুমান করা যায় (sub-ms থেকে কয়েক ms — concurrent collector-এর হাতছোঁয়া)।

ধাপ ২ — একই মোট memory, কিন্তু সব long-lived:

// longlived.go — একবার allocate, বারবার touch
package main

import "fmt"

func main() {
    keep := make([]byte, 0, 200*1024*1024)
    for i := 0; i \< 50; i++ {
        keep = append(keep, make([]byte, 4*1024*1024)...)
        _ = keep[len(keep)-1]
    }
    fmt.Println(len(keep))
}

GODEBUG=gctrace=1 go run longlived.go

এবার GC লাইন অনেক কম — live set বাড়ছে বলে collector বেশি জায়গা পাওয়া পর্যন্ত অপেক্ষা করে, আর যে collection হয় তার খরচও বেশি (mark করতে হয় বড় live graph)। দুই run-এর GC count পাশাপাশি রাখুন — এটাই প্রথম প্রমাণ।

ধাপ ৩ — Python-এ generational counts সরাসরি:

# gens.py
import gc, sys

class Node:
    def __init__(self, n):
        self.data = bytearray(1024)
        self.next = n

gc.collect()                                   # clean slate
before = [g["collections"] for g in gc.get_stats()]
for i in range(20_000):                        # churn: gen0-এ জন্মে জন্মেই মরে
    n = Node(None)

after_churn = [g["collections"] for g in gc.get_stats()]
print("churn delta:", [a-b for a,b in zip(after_churn, before)])

old = []                                       # এখন long-lived population
for i in range(20_000):
    old.append(Node(None))
gc.collect()                                   # সবাইকে বয়স্ক gen-এ promote করাই
mid = [g["collections"] for g in gc.get_stats()]

del old                                        # এবার churn আবার
for i in range(20_000):
    n = Node(None)
end = [g["collections"] for g in gc.get_stats()]
print("final delta:", [a-b for a,b in zip(end, mid)])

python3 gens.py

churn delta: [12, 1, 0]     # gen0 বারবার, gen1 মাঝে মাঝে, gen2 প্রায় কখনো না
final delta: [13, 1, 0]

Gen0 বারবার collect হচ্ছে (nursery!), gen2 প্রায় না — CPython-এর ভেতরে আপনি generational collector-এর pulse সরাসরি দেখলেন। gc.set_debug(gc.DEBUG_STATS) দিয়ে আরও detail, gc.get_threshold() দিয়ে promotion threshold দেখুন।

এটা কী প্রমাণ করে

Allocation-heavy workload-এ collector বারবার চলে (pause মিলিসেকেন্ড-স্তরে, ঘন ঘন), আর long-lived-data workload-এ প্রায় চলেই না — অর্থাৎ GC activity আসলেই allocation pattern আর object lifetime দিয়ে নিয়ন্ত্রিত, আর Python-এর gen counts সরাসরি generational hypothesis-এর প্রমাণ।

নিজে বানান

BUILD IT

পূর্ণ mark-sweep collector — C-তে, shadow-stack root সহ

C · ●●●○○

Object struct: marked bit + fixed-size field array (reference graph)
VM struct: roots array (shadow stack) + all-objects registry
mark(): recursive grey-to-black traversal
sweep(): registry scan — unmarked free করো, marked-এর bit clear করে compact registry
Demo: graph বানাও, root drop করো, gc() চালাও — কে মরল দেখাও
Fragmentation মাপো: প্রতিটা object-এর synthetic address দিয়ে heap-map print করো

Interpreter-এর বাস্তব জগতে root থাকে native stack-এ — যা portable C-তে walk করা যায় না। তাই আমাদের mini-VM-এ shadow stack: interpreter যখনই value hold করবে, explicit root push/pop করবে। Lua-র পুরনো API-টা ঠিক এভাবেই কাজ করে।

/* gc.c — ~120 lines: object graph + mark-sweep + fragmentation map */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define MAX_FIELDS 2
#define MAX_ROOTS  32
#define MAX_OBJS   256

typedef struct Obj {
    uint8_t marked;
    int field_count;
    struct Obj *fields[MAX_FIELDS];
    size_t size;                 /* synthetic footprint — fragmentation map-এর জন্য */
    uintptr_t addr;              /* allocation-time synthetic address */
} Obj;

typedef struct {
    Obj *roots[MAX_ROOTS]; int rc;
    Obj *all[MAX_OBJS];    int ac;
    uintptr_t next_addr;
} VM;

static VM vm;

static Obj *new_obj(size_t sz, int nf) {
    Obj *o = calloc(1, sizeof(Obj));
    o->size = sz; o->field_count = nf;
    o->addr = vm.next_addr; vm.next_addr += sz;   /* bump-style synthetic addr */
    vm.all[vm.ac++] = o;
    return o;
}
static void root(Obj *o)   { vm.roots[vm.rc++] = o; }
static void unroot(void)   { vm.rc--; }          /* LIFO — scope exit */
static void mark(Obj *o) {
    if (o->marked) return;                        /* black — cycle-safe */
    o->marked = 1;                                /* grey→(traverse)→black */
    for (int i = 0; i \< o->field_count; i++)
        if (o->fields[i]) mark(o->fields[i]);
}

static void gc(void) {
    int before = vm.ac;
    for (int i = 0; i \< vm.rc; i++) mark(vm.roots[i]);
    int w = 0;
    for (int r = 0; r \< vm.ac; r++) {             /* sweep + registry compact */
        if (!vm.all[r]->marked) { free(vm.all[r]); continue; }
        vm.all[r]->marked = 0;                    /* পরের cycle-এর জন্য white */
        vm.all[w++] = vm.all[r];
    }
    printf("gc: %d/%d objects survived\n", w, before);
    vm.ac = w;
}

/* fragmentation map: '#' live block, '.' swept hole */
static void heapmap(uintptr_t end) {
    for (uintptr_t a = 0; a \< end; ) {
        Obj *hit = NULL;
        for (int i = 0; i \< vm.ac && !hit; i++)
            if (vm.all[i]->addr == a) hit = vm.all[i];
        if (hit) { printf("#"); a += hit->size; }
        else     { printf("."); a += 16; }
    }
    printf("\n");
}
int main(void) {   /* গ্রাফ: root A→B→C, A→D ; G↔H cycle rooted */
    Obj *A = new_obj(48, 2), *B = new_obj(32, 1), *C = new_obj(16, 0);
    Obj *D = new_obj(16, 0), *E = new_obj(16, 0);
    Obj *G = new_obj(16, 1), *H = new_obj(16, 1);
    A->fields[0]=B; A->fields[1]=D; B->fields[0]=C;
    G->fields[0]=H; H->fields[0]=G;               /* cycle — tracing-এ সমস্যা না */
    E->fields[0]=NULL;
    root(A); root(G);
    heapmap(vm.next_addr);
    puts("-- unroot A subtree, run gc --");
    vm.roots[0] = G; vm.roots[1] = NULL; vm.rc = 1;   /* A-র root সরলাম */
    gc();                                             /* A,B,C,D মরবে; G,H বাঁচবে */
    heapmap(vm.next_addr);

    puts("-- unroot everything, run gc --");
    vm.rc = 0; gc();                                  /* cycle G↔H-ও মরবে! */
    heapmap(vm.next_addr);
    return 0;
}

gcc -O2 -o gc gc.c && ./gc

####..######..######--....----####----
gc: 2/7 objects survived
###...............####....................
gc: 0/2 objects survived
..........................................

Map-এর ব্যাখ্যা: প্রথম লাইনে সব live (সরলীকৃত rendering)। GC-র পরে মাঝে . gap — A,B,C,D-র জায়গা ফাঁক হয়ে রইল, সরেনি। পরের বড় allocation এই গর্তে ঢুকতে পারবে না যদি তার size গর্তের চেয়ে বড় হয়। এটাই mark-sweep fragmentation — এখন আর bookish definition না, আপনার প্রিন্ট করা ছবি। (শেষ দুই line-এর প্যাটার্ন আপনার বানানো গ্রাফ অনুযায়ী সামান্য আলাদা হবে — গঠনটা দেখুন, অক্ষরে-অক্ষরে মেলানোর দরকার নেই।)

নিজে বাড়ান:

Compact করুন: sweep-এর পরে live object-দের addr পুনর্বণ্টন করে গর্ত ভরাট করুন (synthetic move) — heap-map এবার কোনো . ছাড়া ছাপবে। এটাই mark-compact।
Iterative mark: recursion deep graph-এ stack overflow দেয় — mark-কে explicit worklist (grey stack) দিয়ে লিখুন; এটাই Cheney-style queue-র সরাসরি পূর্বসূরি।
Cycle প্রমাণ: G→H→G root-less রেখে আগের লেসনের refcount mental model-এ চিন্তা করুন — কেন counting এখানে ব্যর্থ কিন্তু আপনার collector সফল, এক লাইনে লিখুন।

বাস্তব সিস্টেমে

Production collector-দের মাঠ

JVM-এর জীবাশ্ম-থেকে-আধুনিক spectrum। Serial/Parallel GC (STW, পুরনো কিন্তু batch job-এ এখনো ভালো), CMS (মৃত — concurrent marking-এর পথিকৃৎ), G1 (region-based, default), ZGC/Shenandoah (sub-ms concurrent)। একই hypothesis, পাঁচ রকম engineering compromise।

Go। সরলতার পক্ষে: কোনো user-tunable generation নেই, একটাই concurrent mark-sweep, pacer নিজে target ঠিক করে (GOGC percent)। Server workload-এ predictable sub-ms pause-এর জন্য Go-র reputation-এর বড় অংশ এই collector।

CPython। Hybrid মজা: primary mechanism refcounting, কিন্তু cycle-ধরার জন্য generational tracing fallback (আপনি experiment-এ যে gen0/1/2 counts দেখলেন)। লেসন ৮-এ এই hybrid-এর পুরো গল্প।

V8 (JavaScript)। Generational: নতুন object “new space”-এ semi-space scavenge, বেঁচে থাকলে old space-এ promote; old space-এ incremental mark-sweep-compact, marking মূল thread-কে ছোট ছোট slice-এ ভাগ করে (Orinoco project-এর পর বেশিরভাগ কাজ concurrent)।

Lua আর game scripting। Incremental mark-sweep — frame budget-এর ভেতরে step-by-step চলে, কারণ 60 fps-এ 16 ms-এর বেশি কোনো single pause মারাত্মক।

History anchor: McCarthy-র mark-sweep (Lisp, 1960), Collins-এর refcounting (1960, পরের লেসনে), Cheney-র copying (1970), Lieberman-Hewitt/Ungar-এর generational (1983–84)। আপনি যে collector production-এ দেখছেন, সব এই চার মৌল থেকে বংশবিস্তার।

যে ভুলগুলো সবাই করে

“GC dead object খুঁজে বের করে।”

উল্টো — খোঁজা অসম্ভব (“আর কখনো লাগবে না” ভবিষ্যতের প্রশ্ন)। Collector live/reachable object-দের চিহ্নিত করে, বাকি সবকে মুছে দেয়। এই inversion-এর সরাসরি ফল দুইটা: (১) cycle-এ আটকে থাকা object-ও মরে যায়, (২) “reachable কিন্তু useless” object কখনোই মরে না — GC-যুগের leak-এর রূপ।

“Modern collector-দের pause এখন সমস্যাই না।”

ZGC/Shenandoah sub-ms pause দেয়, ঠিক — কিন্তু দাম: read/write barrier-এর constant throughput tax, আর larger heap headroom। সব workload-এ সব collector না; বড় live-set + tight memory-তে parallel-STW এখনো জেতে। “Pause নেই” না — “pause-কে throughput দিয়ে কিনে নেওয়া হলো”।

“Generational hypothesis একটা সর্বজনীন সত্য।”

এটা empirical tendency, physical law না। Long-lived-heavy workload (in-memory cache, big array processing) nursery-র সুবিধা খেয়ে ফেলে — promotion flood, major GC pressure। এজন্যই Azul-এর C4-এর মতো collector generation-ই বাদ দিয়েছে, আর Go-ও করেছে। Workload মাপুন, hypothesis assume করবেন না।

“Reference counting-ও এক ধরনের tracing GC।”

পরিবারই আলাদা। Tracing periodic graph traversal করে (roots থেকে), RC প্রতিটা pointer-operation-এ incremental accounting করে (কোনো root, কোনো traversal নেই)। Cycle-এ tracing জেতে, latency-distribution-এ RC ভিন্ন সুবিধায়। পরের লেসন পুরোটাই এই তুলনা।

বুঝেছেন কি না দেখুন

Tri-color model-এ grey object মানে কী? Strong tri-color invariant-টা এক বাক্যে বলুন এবং বলুন কোন situation-এ এটা ভাঙার প্রকৃত বিপদ থাকে।

স্মরণ

Grey = নিজে live চিহ্নিত কিন্তু children এখনো scan বাকি (worklist-এ বসে আছে)।

Invariant: black object সরাসরি white object-কে point করবে না। বিপদ concurrent collector-এ — mutator চলতে চলতে black-এ white-pointer বসালে সেই white subtree marking-এ আর ধরা পড়বে না, sweep মুছে ফেলবে — live data loss। STW collector-এ mutator থামানো বলে বিপদ নেই।

Mark-sweep-এর খরচ মোট heap size-এ proportional, copying-এর খরচ live data-তে proportional। Mostly-dead heap-এ কোনটা জেতে এবং কেন এই fact generational design-এর দরজা খুলল?

যুক্তি

Mostly-dead heap-এ copying জেতে — dead object ছোঁয়ই না, শুধু live copy করে; mark-sweep অন্তত sweep-phase-এ পুরো heap walk করে।

দরজা: যদি বেশিরভাগ object তরুণ বয়সেই মরে (infant mortality), তাহলে ছোট একটা region-কে copying দিয়ে ঘন ঘন collect করা পুরো heap ঘাঁটার চেয়ে কয়েক গুণ সস্তা — nursery/minor GC-র মূল যুক্তি। পুরনো, বেঁচে থাকা population-কে আলাদা কম-frequency region-এ রাখা হয়।

Nursery-only minor GC চলছে। Old generation-এর একটা object X nursery-এর Y-কে point করছে, আর বাইরে কেউ Y-কে point করছে না। Minor GC-র traversal Y-কে live ধরবে কীভাবে? Write barrier ছাড়া কী হতো?

প্রয়োগ

Minor GC-র roots = ক্লাসিক roots + remembered set। Write barrier আগেই X-কে set-এ রেখেছে (old→young store ধরা পড়েছিল), তাই X root-এর মতো scan হয়, X→Y edge পেয়ে Y grey হয় — survive।

Barrier না থাকলে X→Y edge-টা অদৃশ্য থাকত; Y white-ই থেকে nursery sweep-এ মুছে যেত, আর X-এর ভেতরে dangling pointer বসে যেত — old gen-এ পুরনো dangling-pointer সমস্যার GC-সংস্করণ!

আপনার team-এর trading system-এ 99.99th percentile latency 1 ms-এর নিচে রাখতে হবে; heap 8 GB, live set steady-state-এ ~6 GB। Parallel GC, G1, ZGC — কোনটা বেছে নেবেন, কোন সংখ্যাগুলো দেখে?

ডিজাইন

STW parallel GC বাদই — বড় heap-এ শত-ms pause percentile পুড়িয়ে দেবে।

G1 বনাম ZGC: G1-এর pause target settable (~10 ms রাখা যায়) কিন্তু 6 GB live-set-এ mixed collections-এ tail উঁচু হয়; ZGC-র concurrent design pause sub-ms — percentile goal-এর জন্য মানানসই। দাম দেখতে হবে: ZGC-র read-barrier overhead (~৫–১৫% throughput পরিসরে, workload-ভেদে) কি মানানসই, আর headroom (ZGC concurrent compact করতে extra memory চায়) আছে কি না। সিদ্ধান্তের metric: p99.99 measured under realistic load — spec sheet না।

আপনার build-এ লেখা collector recursive mark() ব্যবহার করে। কোন ধরনের input graph-এ এটা crash করবে এবং কেন production collector-রা (Cheney-সহ) iterative/worklist approach নেয়?

যুক্তি

Deep chain — যেমন ১০ লাখ-node linked list (A→B→C→…) — recursion depth ১০ লাখ; C stack overflow, segfault। ব্যবহারকারীর data shape-এ collector মারা মানে collector-এর fundamental bug।

Production collector-রা explicit worklist ব্যবহার করে: grey queue heap-এর বাইরে বা to-space-এ থাকে, memory bound আর predictable। Cheney-তে তো worklist-টা to-space নিজেই — scan pointer-এর পেছনের সব কিছু grey; আলাদা structure-ই লাগে না। Trade-off: worklist-ও জায়গা নেয় (worst-case O(live objects)), তাই overflow strategy (fallback rescan) লাগে।

এরপর কী

আজকের collector periodic জরিপে চলে — কিন্তু একটা ভিন্ন পরিবার আছে যেটা কোনো জরিপই চালায় না: reference counting। প্রতিটা object নিজের উপর কয়টা reference আছে সেটা গুনে রাখে; assignment-এ গুন বাড়ে, variable মরলে কমে, শূন্যে পৌঁছালেই সাথে সাথে মৃত্যু — deterministic destruction, GC-র সেই deferred latency-র সরাসরি উত্তর। কিন্তু এই পরিবারের একটা মারাত্মক দুর্বলতা আছে — cycle (আপনার build-এর G↔H-কে counting কখনোই মুছতে পারে না), প্রতিটা assignment-এ hidden tax, আর multithreading-এ atomic counter-এর দাম। Python/Swift-এর বাস্তব ARC story, weak reference-এর রসধন, আর নিজের হাতে C-তে refcounted node + deliberate cycle leak — সবই পরের লেসনে।

পরের লেসন: Reference Counting — গোনা রাখা, cycle-এর ফাঁদ, আর weak reference।

Tracing Garbage Collection — mark-sweep থেকে generational পর্যন্ত

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

Root set — জরিপের শুরুর ঠিকানাগুলো

Tri-color marking — traversal-এর abstract ভাষা

Mark-sweep — প্রথম প্রজন্ম

Mark-copy — দ্বিতীয় প্রজন্ম

Generational collection — empirical বুদ্ধি

Pause — কেন stop-the-world ব্যথা দেয়

ভেতরে কী ঘটছে

Tri-color invariant — concurrent world-এ যেখানে সব ভাঙে

Cheney semispace copying — ভেতরে ঠিক কী ঘটে

উদাহরণ

একটা ছোট graph-এর পূর্ণ mark-sweep trace

ছবিতে

Semispace flip আর generational lifecycle — দুইটা মানচিত্র

নিজে চালিয়ে দেখুন

নিজের চোখে GC — Go-তে pause, Python-এ generation counts

নিজে বানান

পূর্ণ mark-sweep collector — C-তে, shadow-stack root সহ

বাস্তব সিস্টেমে

Production collector-দের মাঠ

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Root set — জরিপের শুরুর ঠিকানাগুলো

Tri-color marking — traversal-এর abstract ভাষা

Mark-sweep — প্রথম প্রজন্ম

Mark-copy — দ্বিতীয় প্রজন্ম

Generational collection — empirical বুদ্ধি

Pause — কেন stop-the-world ব্যথা দেয়

⚙ভেতরে কী ঘটছেUnder the hood

Tri-color invariant — concurrent world-এ যেখানে সব ভাঙে

Cheney semispace copying — ভেতরে ঠিক কী ঘটে

▶উদাহরণExample

একটা ছোট graph-এর পূর্ণ mark-sweep trace

◫ছবিতেDiagram

Semispace flip আর generational lifecycle — দুইটা মানচিত্র

⌘নিজে চালিয়ে দেখুনExperiment

নিজের চোখে GC — Go-তে pause, Python-এ generation counts

⚒নিজে বানানBuild it yourself

পূর্ণ mark-sweep collector — C-তে, shadow-stack root সহ

◉বাস্তব সিস্টেমেReal-world usage

Production collector-দের মাঠ

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

এরপর কী

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

ছবিতে

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী