সরাসরি পর্বে যান
পর্ব ৭৫ · ৮৬-এর মধ্যে · মডিউল ১২

Garbage collection — reference counting, mark-sweep, copying আর generational

Garbage Collection — Roots and Reachability, Reference Counting and Cycles, Mark-Sweep, Cheney Copying, Mark-Compact, Generations and Write Barriers, Tri-Colour Marking

Taught in Bangla, this lesson defines garbage as objects unreachable from the roots of Haat's VM and runs collectors on a small Haat heap. It shows reference counting missing a cycle, then mark-sweep, Cheney copying and mark-compact, CPython's reference counting with a cycle collector, generational GC with a write barrier, tri-colour incremental marking, precise versus conservative scanning, finalizers and weak references. Real logs from Java's G1 and Node's V8 show pauses, and it ends with a GC choice for Haat.

এই পর্বে যা শিখবেন

  • Root আর reachability দিয়ে “garbage” শব্দের সঠিক সংজ্ঞা, আর Haat VM সত্যিই heap-এ কী রাখে তা গুনে দেখা
  • Reference counting হাতে বানানো, আর reference cycle-এ কেন সে হার মানে তা Haat-এর নিজের একটি cycle দিয়ে দেখা
  • Mark-sweep, Cheney-র copying collector আর mark-compact একই object graph-এ চালিয়ে খরচ মেলানো
  • Generational GC, write barrier আর tri-colour marking: কেন লাগে, আর Haat-এর কোন opcode-এ বসাতে হয়
  • CPython, V8 আর JVM-এর collector-এর সত্যিকারের আউটপুট পড়া, আর AI-এর GC-বিষয়ক দাবি যাচাই করা

১ · Garbage মানে কী — root, reachability আর Haat-এর heap

পর্ব ১৬-এ (Lifetime আর storage) দেখেছেন, heap-এর ঘর কখন ফেরত যাবে তার তিনটি উত্তর আছে: প্রোগ্রামার নিজে (free), ভাষার নিয়ম (Rust-এর ownership, পর্ব ৭৬), অথবা runtime নিজে খুঁজে বের করে। শেষ পথটির নাম garbage collection (GC). এই পর্বে সেই খোঁজার যন্ত্রটি আমরা নিজেরা বানাব, Haat-এর নিজের object দিয়ে।

বাজারঘরের গুদামে হাজারো বাক্স। ম্যানেজার কাউন্টারের খাতা (root) থেকে শুরু করেন: খাতায় যে বাক্সের নম্বর আছে সেটি দরকারি, আর সেই বাক্সের গায়ের চিরকুটে যে বাক্সের নম্বর, সেটিও। চিরকুট ধরে ধরে যত বাক্সে পৌঁছানো যায়, সব রাখা হয়; বাকিগুলো কেউ আর খুঁজে পাবে না, তাই ফেলে দেওয়া নিরাপদ। প্রতিটি বাক্সে “কতজন আমাকে দেখাচ্ছে” গুনে রাখা আরেক পদ্ধতি; তার দুর্বলতাও দেখব।

সংজ্ঞা ৭৫.১ — root, reachable আর garbage

চলার যেকোনো মুহূর্তে root set R হলো সেই জায়গাগুলো যেখান থেকে program সরাসরি একটি মান পড়তে পারে: global variable, প্রতিটি চলমান frame-এর slot আর register, আর VM-এর operand stack. Heap-কে একটি directed graph ভাবুন: object হলো node, আর object-এর ভেতরের প্রতিটি pointer একটি edge (o → p). তাহলে reachable object-এর সেট হলো সবচেয়ে ছোট সেট L, যাতে R থেকে সরাসরি দেখানো সব object আছে, আর o ∈ L ও o → p হলে p ∈ L. যে object L-এ নেই, সেটি garbage: program আর কোনো পথে তার কাছে পৌঁছাতে পারবে না, তাই তার জায়গা ফেরত নেওয়া নিরাপদ।

একটি সূক্ষ্ম কথা। Program-এর আসল প্রশ্ন “এই object কি ভবিষ্যতে আর ব্যবহার হবে?” (liveness), কিন্তু সাধারণ ক্ষেত্রে এটি গণনাযোগ্যভাবে জানা অসম্ভব (গণনার তত্ত্বের পর্ব ৫৩, Rice-এর উপপাদ্য). Reachability তার একটি নিরাপদ অনুমান: যা পৌঁছানো যায় না, তা নিশ্চয়ই আর ব্যবহার হবে না; উল্টোটি সবসময় সত্য নয়। তাই GC কখনো ব্যবহৃত জিনিস মোছে না, তবে অব্যবহৃত জিনিস বাঁচিয়ে রাখতে পারে; পর্ব ৫৭-এর (Environment আর closure-এর বাস্তবায়ন) safe for space নকশা এই ফাঁক কমায়।

Haat VM heap-এ আসলে কী রাখে

পর্ব ৫৯-এর (Stack-based virtual machine) VM-এ তিন রকম মান heap-এ যায়: MAKE_CLOSURE-এর closure (code + ধরা cell-এর তালিকা), MAKE_CELL-এর cell (ধরা variable-এর এক-ঘরের বাক্স), আর + দিয়ে জোড়া লাগানো নতুন string. Int আর Bool আমাদের মডেলে সরাসরি মান, heap-এ নয়; string literal থাকে code object-এর constant pool-এ। লেখকের ল্যাবে reference-এর vm.py-র একটি কপিতে প্রতিটি allocation গোনা হয়েছে (সত্যিকারের run, CPython 3.14.4):

Programclosurecellstringমন্তব্য
bazar.haat300তিনটিই সারা জীবন বাঁচে
counter.haat640দুটি counter-এর count আর step
nested.haat1390loop-এর প্রতি round-এ নতুন cell, আর go-র cycle
strings.haat103তিনটি +, তিনটি নতুন string
heap_demo.haat651এই পর্বের উদাহরণ (নিচে)

সংখ্যাগুলোয় <main>-এর closure-ও আছে। bazar.haat-এ GC-র কোনো কাজ নেই; প্রশ্ন ওঠে closure আর string নিয়ে খেলা program-এ। এই পর্ব চলবে নিচের program নিয়ে:

// বাজারঘর: heap-এ কী জমে, কী ফেলে দেওয়া যায়
fn make_counter(step: Int) -> () -> Int {
    var count = 0;
    let next = fn() -> Int { count = count + step; return count; };
    return next;
}
fn countdown(n: Int) {
    fn go(i: Int) { if i > 0 { go(i - 1); } }
    go(n);
}
let a = make_counter(1);
var b = make_counter(10);
var note = "অর্ডার " + "চাল";
countdown(2);
b = a;
note = "শেষ";
print(a() + b());
print(note);

Reference বাস্তবায়নের python -B haat.py run আর vm দুটিই ছাপে 3 আর শেষ (b = a;-এর পর দুটি নামই একই counter, তাই 1 + 2). এখন প্রথম print-এর ঠিক আগের মুহূর্তে heap-এর ছবি। এখানে নামগুলো ছোট করা: M = make_counter-এর closure, D = countdown-এর, A আর B দুটি counter closure (A.count, A.step তাদের cell), S = জোড়া লাগানো string, আর cG ও G হলো countdown-এর ভেতরের go-র cell আর closure. Reference-এর dis দেখায় কেন go একটি cell পায়: সে নিজেকে ডাকে, তাই নিজের নামটি ধরে (CONST (); MAKE_CELL 1; MAKE_CLOSURE 1 ; captures go; STORE_CELL 1).

ছবি ৭৫.১ — note = "শেষ";-এর পরের heap: ১১টি object, ৫টি জীবিত

লেখকের ল্যাবের reference VM-এর কপি থেকে নেওয়া snapshot; <main>-এর closure বাদ।

Heap of heap_demo.haat after note = "শেষ": five live objects reachable from roots, six garbage including the cG-G cycle root · global mk_ctr cntdwn a b note "শেষ" const M D A A.count A.step garbage · root থেকে পথ নেই B B.count B.step S "অর্ডার চাল" cG G cycle cG ↔ G: কারও গণনা শূন্য নয়, তবু garbage সবুজ = জীবিত ৫টি ধূসর আর হলুদ = garbage ৬টি
ছবি ৭৫.১ — a আর b দুটি root একই A-কে দেখায়; A তার দুটি cell-কে। note এখন একটি string literal দেখায়, যা constant pool-এ থাকে, heap-এ নয়। B আর তার দুটি cell, পুরোনো string S, আর countdown-এর রেখে যাওয়া cG ↔ G-এ কোনো root থেকে পথ নেই। ল্যাবের snapshot ঠিক এই ৫টিকে LIVE আর ৬টিকে dead দেখিয়েছে।

Garbage দুই রকমের: B-দল আর S acyclic, শেষ pointer সরলেই একা; cG ↔ G cyclic, একে অপরকে ধরে রাখে কিন্তু বাইরে থেকে কেউ নয়।

২ · Reference counting — সঙ্গে সঙ্গে ফেরত, কিন্তু cycle-এ অন্ধ

সবচেয়ে সরল ধারণা: প্রতিটি object-এর গায়ে একটি সংখ্যা, “কতগুলো pointer আমাকে দেখাচ্ছে”। একটি pointer লেখার সময় নতুন লক্ষ্যের গণনা এক বাড়ে, পুরোনো লক্ষ্যের এক কমে। কারও গণনা শূন্য হলে সে সঙ্গে সঙ্গে মুক্ত, আর তার ভেতরের প্রতিটি pointer-এর লক্ষ্যের গণনাও এক কমে, যা একটি শিকল-প্রতিক্রিয়া তৈরি করতে পারে। ধারণাটি George Collins-এর ১৯৬০ সালের প্রবন্ধে প্রকাশিত বলে ধরা হয়; আজ CPython, Swift (ARC), Objective-C, C++-এর std::shared_ptr আর Rust-এর Rc এর ওপর চলে।

নিয়ম ৭৫.১ — একটি pointer-লেখা x.f = v

(১) v যদি object হয়, rc(v) ← rc(v) + 1. (২) পুরোনো মান u = x.f যদি object হয়, rc(u) ← rc(u) − 1, আর rc(u) = 0 হলে u-কে মুক্ত করুন: তার প্রতিটি pointer-এর জন্য এই ধাপ (২) আবার। (৩) x.f ← v. ক্রমটি জরুরি: আগে বাড়ানো, পরে কমানো। নইলে x.f = x.f-এর মতো নিজের ওপর লেখায় গণনা এক মুহূর্তের জন্য শূন্য হয়ে object অকালে মুছে যেত।

Haat VM-এ “pointer-লেখা” মানে slot, global আর cell-এ লেখা, frame মুছে যাওয়া আর operand stack-এর ওঠা-নামা। নিচের ব্লক heap_demo.haat-এর ঘটনাগুলো reference VM-এর ক্রমেই (cell আগে, closure পরে) চালায়; সরলতার জন্য operand stack-এর ক্ষণিকের গণনা বাদ।

# heap_demo.haat-এর heap: প্রতিটি object = [kind, refs]; Int সরাসরি মান, heap-এ নয়
heap, rc, freed, allobjs, roots = {}, {}, [], {}, {}
def new(name, kind, *refs):
    heap[name] = allobjs[name] = [kind, list(refs)]; rc[name] = 0
    for r in refs: inc(r)
    return name
def inc(o):
    if o: rc[o] += 1
def dec(o):
    if not o: return
    rc[o] -= 1
    if rc[o] == 0:                       # গণনা শূন্য: সঙ্গে সঙ্গে মুক্ত, ভেতরের ref-ও কমে
        kind, refs = heap.pop(o)
        freed.append(o)
        for r in refs: dec(r)
def set_root(slot, o):                   # global বা frame-এর slot-এ লেখা
    inc(o); dec(roots.get(slot)); roots[slot] = o
def set_field(o, i, v):                  # STORE_CELL / STORE_FREE
    inc(v); dec(heap[o][1][i]); heap[o][1][i] = v
def make_counter(tag, glob):             # MAKE_CELL step, MAKE_CELL count, MAKE_CLOSURE
    set_root("step", new(tag + ".step", "cell"))
    set_root("count", new(tag + ".count", "cell"))
    set_root("next", new(tag, "closure", tag + ".count", tag + ".step"))
    set_root(glob, tag)
    for s in ("step", "count", "next"): set_root(s, None)   # frame শেষ
set_root("make_counter", new("M", "closure")); set_root("countdown", new("D", "closure"))
make_counter("A", "a"); make_counter("B", "b")
set_root("note", new("S", "string"))                       # "অর্ডার " + "চাল"
set_root("go", new("cG", "cell", None))                    # countdown: MAKE_CELL go
set_field("cG", 0, new("G", "closure", "cG"))              # MAKE_CLOSURE; STORE_CELL
set_root("go", None)                                       # countdown ফিরে গেল
print("countdown-এর পর rc:", {k: rc[k] for k in ("cG", "G")}, "মুক্ত:", freed)
set_root("b", "A"); set_root("note", None)                 # b = a;  note = "শেষ";
print("মুক্ত হলো:", freed)
print("heap-এ রয়ে গেল:", sorted(heap), "∣ cycle-এর rc:", {k: rc[k] for k in ("cG", "G")})

আউটপুট (CPython 3.14.4-এ ল্যাবে, আর Pyodide-এ একই):

countdown-এর পর rc: {'cG': 1, 'G': 1} মুক্ত: []
মুক্ত হলো: ['B', 'B.count', 'B.step', 'S']
heap-এ রয়ে গেল: ['A', 'A.count', 'A.step', 'D', 'G', 'M', 'cG'] ∣ cycle-এর rc: {'cG': 1, 'G': 1}

b = a;-এর মুহূর্তেই B-এর গণনা ১ থেকে ০, B মুক্ত, আর তার দুটি cell-এর গণনাও ০: তিনটি object এক শিকলে চলে গেল। note = "শেষ"; S-কে মুক্ত করল। কিন্তু countdown ফেরার পর cG আর G-এর গণনা ১ আর ১: প্রত্যেকে অন্যজনের একমাত্র ধারক। কোনো ঘটনা আর এদের গণনা কমাবে না, তাই ১১টির মধ্যে ৪টি মুক্ত, ৫টি জীবিত, আর ২টি চিরকালের memory leak.

11let a = make_counter(1);12var b = make_counter(10);13var note = "অর্ডার " + "চাল";14countdown(2);15b = a;16note = "শেষ";
Reference count
A, A.count, A.step
B, B.count, B.step
S
cG, G
  1. make_counter(1)-এর ভেতরে, return-এর আগে। দুটি cell, প্রত্যেকের ধারক একটি slot আর closure A, তাই গণনা ২; A-কে ধরে slot next, তাই ১.
  2. let a ফিরল। A global a-তে (+১), আর frame মুছে তিনটি slot-এর গণনা −১: A = ১, দুটি cell = ১. A বাইরে পালিয়েছে, তাই কিছু মুক্ত হয়নি।
  3. var b = make_counter(10). একই ঘটনা: B, B.count, B.step সবার গণনা ১.
  4. String জোড়া। নতুন string S, ধারক শুধু global note; দুটি literal constant pool-এর, তাদের গণনা লাগে না।
  5. countdown(2) চলছে। MAKE_CELL cG বানায় (slot: ১), MAKE_CLOSURE G বানায় যে cG ধরে (cG: ২), STORE_CELL G-কে cG-তে রাখে (G: ১).
  6. countdown ফিরল। Slot মুছল, cG ২ থেকে ১. এখন cG-কে ধরে শুধু G, G-কে শুধু cG. কেউ শূন্য নয়: leak শুরু।
  7. b = a. আগে A বাড়ে (২), তারপর B কমে (০)। B মুক্ত হয়ে ভেতরের দুটি pointer কমায়, B.count আর B.step-ও ০: এক শিকলে তিনটি।
  8. note = "শেষ"। নতুন মান literal, তাই S-এর গণনা ০, S মুক্ত। মোট ৪টি মুক্ত, ৫টি জীবিত, আর cG ও G চিরকাল ১ আর ১ নিয়ে পড়ে থাকবে।

Haat-এ cycle কোথা থেকে আসে — একটি ছোট প্রমাণ

Cycle কি Haat-এ দুর্লভ? পরের প্রস্তাব দেখায় cycle আসে ঠিক কোথা থেকে।

প্রস্তাব ৭৫.১ — Haat-এর heap-এ cycle শুধু cell-এ লেখা থেকে

Haat VM-এর heap-এ (closure, cell, string) যেকোনো cycle-এ অন্তত একটি cell আর একটি closure আছে, আর এমন cycle তৈরি হতে পারে শুধু STORE_CELL বা STORE_FREE চললে, অর্থাৎ ধরা var-এ নতুন মান লেখা বা একটি nested function-কে তার নিজের cell-এ রাখা।

প্রমাণ।

  1. String-এর ভেতরে কোনো pointer নেই; closure-এর pointer শুধু cell-এ (তার cells তালিকা; code static); cell-এর pointer তার এক মানে, যা যেকোনো কিছু হতে পারে। তাই closure থেকে বেরোনো প্রতিটি edge একটি cell-এ যায়, আর string থেকে কোনো edge বেরোয় না।
  2. একটি cycle-এ string থাকতে পারে না (তার বাইরে যাওয়ার edge নেই)। শুধু cell দিয়ে cycle হতে হলে একটি cell-কে আরেকটি cell দেখাতে হবে, কিন্তু Haat-এ cell কোনো মান নয় (cell-এর মান হয় Int, Bool, Str বা closure), তাই তা অসম্ভব। ফলে cycle-এ একটি closure আর তার পরের node হিসেবে একটি cell আছে।
  3. এবার তৈরির দিক। MAKE_CLOSURE নতুন closure বানায় যা আগে থেকে থাকা cell-কে দেখায়; MAKE_CELL নতুন cell বানায় যা stack-এর একটি আগে থেকে থাকা মান দেখায়; string জোড়া নতুন pointer-হীন object. তাই শুধু এই তিন রকম ঘটনায় প্রতিটি edge নতুন object থেকে পুরোনো object-এর দিকে যায় (জন্মক্রমে)। জন্মক্রম একটি পূর্ণ ক্রম, তাই এমন edge-গুলো দিয়ে কোনো cycle হয় না।
  4. একটি পুরোনো object-এর ভেতরের pointer পরে বদলায় শুধু STORE_CELL আর STORE_FREE-এ (globals আর slot root, heap-object নয়)। তাই যেকোনো cycle-এর অন্তত একটি edge এই দুই opcode-এর একটি তৈরি করেছে। ∎

countdown-এর cycle এই পথেই এসেছে: STORE_CELL 1 নতুন G-কে পুরোনো cG-তে রাখল। ধাপ ৩ অংশ ৬-এ আবার কাজে লাগবে।

৩ · Mark-sweep — root থেকে চিহ্ন, তারপর ঝাড়ু

Tracing collector গণনা রাখে না; মাঝে মাঝে program থামিয়ে সংজ্ঞা ৭৫.১-কে সরাসরি গণনা করে। McCarthy-র ১৯৬০ সালের LISP প্রবন্ধের পদ্ধতিকেই সাধারণত প্রথম garbage collector ধরা হয়। দুই ধাপ:

  • Mark: প্রতিটি root-এর লক্ষ্য একটি worklist-এ রাখুন। Worklist থেকে একটি object তুলুন; আগে চিহ্ন না পেয়ে থাকলে চিহ্ন দিন (mark bit), আর তার ভেতরের প্রতিটি pointer worklist-এ যোগ করুন। Worklist খালি হলে থামুন।
  • Sweep: পুরো heap-এর প্রতিটি ঘর ক্রমে দেখুন। চিহ্ন নেই? জায়গাটি free list-এ ফেরত। চিহ্ন আছে? পরের বারের জন্য চিহ্ন মুছে দিন।

এই হাঁটার একটি প্রচলিত ভাষা আছে, যা অংশ ৭-এ জরুরি হবে: tri-colour. সাদা = এখনো দেখা হয়নি (শেষে সাদা থাকলে garbage); ধূসর = চিহ্ন পাওয়ার যোগ্য বলে জানা, কিন্তু ভেতরের pointer এখনো দেখা হয়নি (worklist-এ আছে); কালো = চিহ্নিত, ভেতরও দেখা শেষ। নিচের ব্লক আগের ব্লকের একই ১১টি object (allobjs, যেখানে মুক্ত object-ও আছে, কারণ এবার reference counting ছাড়া শুরু থেকে ভাবছি) আর একই root নেয়।

# একই ১১টি object (allobjs), একই root; এবার tracing: mark-sweep আর Cheney copying
root_objs = [o for o in roots.values() if o]
print("root:", root_objs)
def mark_sweep():
    marked, grey, order = set(), list(root_objs), []
    while grey:                                  # grey = দেখা হয়েছে, ভেতর এখনো দেখা হয়নি
        o = grey.pop()
        if o in marked: continue
        marked.add(o); order.append(o)           # black
        grey += [r for r in allobjs[o][1] if r]
    swept = [o for o in allobjs if o not in marked]   # sweep: পুরো heap ঘুরে দেখা
    return order, swept
order, swept = mark_sweep()
print("mark-এর ক্রম:", order)
print("sweep মুছল:", swept, f"(heap-এর {len(allobjs)}টি ঘরই দেখতে হলো)")
def cheney():
    to, fwd = [], {}                             # to-space আর forwarding ঠিকানা
    def copy(o):
        if o not in fwd:
            fwd[o] = len(to); to.append([o, list(allobjs[o][1])])
        return fwd[o]
    for r in root_objs: copy(r)                  # root আগে কপি
    scan = 0
    while scan < len(to):                        # scan থেকে free (= len(to)) পর্যন্ত
        name, refs = to[scan]
        to[scan][1] = [copy(r) if r else None for r in refs]
        scan += 1
    return to, fwd
to, fwd = cheney()
for i, (name, refs) in enumerate(to): print(f"  to[{i}] {name:8} refs → {refs}")
print("কপি:", len(to), "∣ garbage ছোঁয়াই হয়নি:", sorted(set(allobjs) - set(fwd)))

আউটপুট (আগের ব্লক চালানোর পর):

root: ['M', 'D', 'A', 'A']
mark-এর ক্রম: ['A', 'A.step', 'A.count', 'D', 'M']
sweep মুছল: ['B.step', 'B.count', 'B', 'S', 'cG', 'G'] (heap-এর 11টি ঘরই দেখতে হলো)
  to[0] M        refs → []
  to[1] D        refs → []
  to[2] A        refs → [3, 4]
  to[3] A.count  refs → []
  to[4] A.step   refs → []
কপি: 5 ∣ garbage ছোঁয়াই হয়নি: ['B', 'B.count', 'B.step', 'G', 'S', 'cG']

Root-এর তালিকায় A দুবার (a আর b), কিন্তু চিহ্ন একবারই পড়ে। Mark ঠিক ৫টি জীবিত object পেয়েছে, আর sweep মুছেছে ৬টি, cG আর G-সহ: tracing-এর কাছে cycle কোনো সমস্যাই নয়, কারণ সে গণনা দেখে না, পথ দেখে। দাম: sweep-কে ১১টি ঘরই দেখতে হয়েছে, জীবিত হোক বা মৃত। Cheney-র অংশটি পরের অংশে।

1marked, grey = set(), list(root_objs)2while grey:3    o = grey.pop()4    if o in marked: continue5    marked.add(o)6    grey += refs(o)7swept = heap − marked
রং
ধূসর (stack)
কালো
সাদা
  1. শুরু। চারটি root-এর লক্ষ্য ধূসর stack-এ: M, D, A আর আবার A, কারণ a আর b দুটোই A দেখায়। ১১টির মধ্যে ৩টি ধূসর, বাকি ৮টি সাদা।
  2. pop A. চিহ্ন নেই, তাই কালো; তার দুটি pointer, A.count আর A.step, ধূসর হয়ে stack-এ। সাদা থাকল ৬টি।
  3. pop A.step. কালো। মান Int (1), pointer নয়, কিছু যোগ হলো না।
  4. pop A.count. কালো। এর মান তখনো Int 0, pointer নয়।
  5. pop A, আবার। আগেই কালো, তাই continue. Cycle থাকলেও এই লাইনই অসীম loop আটকায়।
  6. pop D. কালো; countdown কিছু capture করে না।
  7. pop M. কালো; stack খালি, mark শেষ। কালো ৫টি, সাদা ৬টি: B, B.count, B.step, S, cG, G. Mark-এর কাজ জীবিতদের সমানুপাতিক।
  8. Sweep. ১১টি ঘরই দেখা হলো; সাদা ৬টি free list-এ, কালো ৫টির চিহ্ন মুছে পরের বারের জন্য তৈরি। Cycle cG ↔ G বাড়তি কাজ ছাড়াই মুছে গেল।
প্রস্তাব ৭৫.২ — mark ঠিক reachable সেটটিকেই কালো করে

Mark phase শেষ হলে (program থামানো অবস্থায়) কালো object-এর সেট = সংজ্ঞা ৭৫.১-এর L.

প্রমাণের রূপরেখা.

  1. কালো ⊆ L: কোনো object ধূসর হয় শুধু root থেকে, বা একটি ইতিমধ্যে কালো object-এর pointer থেকে। ধাপের ওপর induction-এ প্রতিটি ধূসর, তাই প্রতিটি কালো object, L-এ আছে।
  2. L ⊆ কালো: Invariant: কোনো কালো object থেকে সাদা object-এ edge নেই। একটি object কালো হওয়ার মুহূর্তেই তার সব লক্ষ্য ধূসর হয়, আর ধূসর থেকে কেউ আর সাদা হয় না; program থেমে আছে বলে নতুন edge-ও আসে না।
  3. শেষে ধূসর নেই। ধরুন p ∈ L কিন্তু সাদা। Root থেকে p-এর একটি পথ নিন; পথের প্রথম node কালো (root-এর লক্ষ্যরা শুরুতেই ধূসর ছিল), শেষ node সাদা, তাই কোথাও একটি কালো → সাদা edge আছে, যা invariant ভাঙে। অতএব p কালো। ∎

ধাপ ২-এর “program থেমে আছে” কথাটি লক্ষ করুন; অংশ ৭-এর concurrent GC-র পুরো প্রকৌশল এই শর্ত ছাড়া invariant রক্ষা করা।

Mark-sweep-এর দুটি দুর্বলতা। প্রথমত, sweep পুরো heap-এর সমানুপাতিক। দ্বিতীয়ত, object সরানো হয় না, তাই সময়ের সঙ্গে জীবিত object-এর মাঝে মাঝে ছোট ছোট ফাঁকা টুকরো জমে, যাকে বলে external fragmentation: মোট খালি জায়গা যথেষ্ট, কিন্তু একটি বড় string-এর মতো টানা জায়গা নেই। নতুন object বসাতে free list-এ টুকরো খুঁজতে হয়, C-র malloc-এর মতো (C কোর্সের পর্ব ৪৭).

৪ · Copying আর mark-compact — জীবিতদের সরিয়ে গুছিয়ে রাখা

Copying collector-এর বুদ্ধি সাহসী: heap-কে দুই সমান ভাগে ভাগ করুন, from-space আর to-space (semispace). Program শুধু from-space-এ object বানায়। Collection-এর সময় জীবিত object-গুলোকে to-space-এ পরপর কপি করুন, তারপর দুই ভাগের নাম বদলে দিন। From-space-এ যা রইল, পুরোটাই garbage; তাকে এক ধাক্কায় খালি ধরা হয়, একটি একটি করে দেখার দরকারই নেই। Semispace নকশা Fenichel ও Yochelson-এর (১৯৬৯) বলে জানা যায়; C. J. Cheney (১৯৭০) দেখান কীভাবে আলাদা stack ছাড়াই শুধু দুটি index দিয়ে এটি করা যায়।

অ্যালগরিদম ৭৫.১ — Cheney-র copying (breadth-first)

to-space একটি array, দুটি index: scan আর free. (১) প্রতিটি root-এর লক্ষ্য copy করুন। copy(o): o-এর গায়ে যদি ইতিমধ্যে একটি forwarding pointer থাকে, সেই নতুন ঠিকানা ফেরত দিন; নইলে o-কে free-এ কপি করুন, পুরোনো জায়গায় নতুন ঠিকানা লিখে রাখুন, free এগিয়ে দিন। (২) scan < free যতক্ষণ: to-space-এর scan ঘরের object-এর প্রতিটি pointer-কে copy দিয়ে নতুন ঠিকানায় বদলান, তারপর scan এক বাড়ান। scan = free হলে শেষ। scan আর free-এর মাঝের অংশটিই আসলে ধূসর worklist, আলাদা stack লাগে না।

1for r in root_objs: copy(r)2scan = 03while scan < len(to):4    refs → copy(r) প্রতিটির5    scan += 1
To-space
to[]
scan, free
forwarding
  1. শুরু। To-space খালি, scan = free = 0.
  2. Root কপি। M, D, A পরপর to[0], to[1], to[2]-এ; প্রত্যেকের পুরোনো জায়গায় forwarding pointer. free = 3.
  3. Root b. A-এর গায়ে forwarding আছে (→ 2), তাই দ্বিতীয় কপি নয়; b শুধু ঠিকানা 2 পায়। নইলে a আর b আলাদা counter হয়ে যেত।
  4. scan M. ভেতরে pointer নেই। scan = 1.
  5. scan D. একই কথা। scan = 2.
  6. scan A. দুটি pointer, A.count আর A.step, প্রথমবার দেখা: to[3], to[4]-এ কপি, free = 5; A-এর pointer হয় [3, 4]. scan = 3.
  7. scan A.count, A.step. মান Int, pointer নেই; scan = 5 = free: শেষ। ৫টি কপি; B-দল, S আর cG ↔ G-এর দিকে collector একবারও তাকায়নি।

Copying-এর কাজ শুধু জীবিতদের সমানুপাতিক (এখানে ৫), garbage যত বেশিই হোক। জীবিতরা পাশাপাশি বসে, তাই fragmentation নেই, আর নতুন object বানানো মাত্র একটি pointer এগোনো (bump-pointer allocation). দাম: heap-এর অর্ধেক অব্যবহৃত, আর ঠিকানা বদলায় বলে runtime-কে প্রতিটি pointer চিনতে হয় (অংশ ৭)।

Mark-compact — জায়গা বদল না করেই গোছানো

অর্ধেক heap ফেলে রাখা সবসময় চলে না। Mark-compact একই heap-এর ভেতরে জীবিতদের এক প্রান্তে ঠেলে দেয়। LISP 2-এর জন্য বর্ণিত বলে পরিচিত “sliding” রূপে mark-এর পর তিনটি pass: (ক) heap ঘুরে প্রতিটি জীবিত object-এর নতুন ঠিকানা হিসাব (আগের জীবিতদের মোট আকার), (খ) প্রতিটি pointer নতুন ঠিকানায় বদলানো, (গ) object-গুলো সরানো। জন্মক্রম অক্ষত থাকে, যা cache-এর জন্য ভালো।

heap_demo.haat-এ এর কাজই নেই: ল্যাবের snapshot-এ জীবিত ৫টি জন্মক্রমে প্রথম ৫টি (M, D, A.step, A.count, A), তাই কেউ নড়ে না। কিন্তু let a-কে var a আর b = a;-কে a = b; করলে (reference-এ ফল 30) জীবিত হয় M, D, B.step, B.count, B; তখন ঠিকানা 5, 6, 7 থেকে 2, 3, 4-এ সরে, আর B-এর pointer [6, 5] হয়ে যায় [3, 2]. অনুশীলন ৩-এ এটি নিজে হিসাব করবেন।

পদ্ধতিকাজ কিসের সমানুপাতিকবাড়তি জায়গাObject সরে?Allocation
Mark-sweepmark: জীবিত; sweep: পুরো heapmark bitনাfree list থেকে খোঁজা
Copying (Cheney)শুধু জীবিতheap-এর অর্ধেকহ্যাঁbump pointer
Mark-compactmark: জীবিত; ২–৩ pass পুরো heapforwarding-এর ঘরহ্যাঁ, এক প্রান্তেbump pointer
Reference countingপ্রতিটি pointer-লেখা; মুক্তি garbage-এর সমানুপাতিকপ্রতি object-এ গণনানাfree list

৫ · CPython — reference counting আর পাশে একটি cycle collector

Haat-এর reference VM নিজেই CPython-এ চলে, যার প্রধান পদ্ধতি reference counting. তাহলে countdown-এর Cell ↔ Closure cycle কি Python-এর ভেতরেও আটকে থাকে? নিচের ব্লক reference-এর vm.py-র মতো দুটি class দিয়ে ঠিক সেই cycle বানায়, আর weak reference দিয়ে উঁকি দেয় (weak reference object-কে বাঁচিয়ে রাখে না, শুধু জানায় সে এখনো আছে কি না)।

# reference vm.py-র Cell আর Closure-এর মতো দুটি class; countdown-এর go-কে হাতে বানানো
import gc, sys, weakref
class Cell:
    def __init__(self, value): self.value = value
class Closure:
    def __init__(self, code, cells): self.code, self.cells = code, cells
print(sys.version.split()[0], "threshold:", gc.get_threshold())
gc.collect(); gc.disable()                    # পুরোনো আবর্জনা সাফ, এখন শুধু reference counting
def countdown():
    cell = Cell(None)                         # CONST (); MAKE_CELL go
    go = Closure("go", [cell])                # MAKE_CLOSURE go (cell ধরে)
    cell.value = go                           # STORE_CELL go: cycle
    return weakref.ref(go), weakref.ref(cell)
w_go, w_cell = countdown()                    # frame শেষ, local নাম দুটি গেল
print("ফেরার পর বেঁচে আছে?", w_go() is not None, w_cell() is not None)
print("cell-কে কে ধরে আছে:", [type(r).__name__ for r in gc.get_referrers(w_cell())])
def make_counter():                           # cycle নেই: শুধু closure → cell
    c = Cell(0)
    return weakref.ref(Closure("next", [c]))
w_next = make_counter()
print("cycle-হীন closure বেঁচে আছে?", w_next() is not None)
print("gc.collect() পেল:", gc.collect())
print("collect-এর পর বেঁচে আছে?", w_go() is not None, w_cell() is not None)
gc.enable()

লেখকের যন্ত্রে CPython 3.14.4-এ আউটপুট; browser-এর Pyodide-এ (CPython 3.14.2) শুধু প্রথম লাইনের version আলাদা, বাকি হুবহু:

3.14.4 threshold: (2000, 10, 0)
ফেরার পর বেঁচে আছে? True True
cell-কে কে ধরে আছে: ['list']
cycle-হীন closure বেঁচে আছে? False
gc.collect() পেল: 3
collect-এর পর বেঁচে আছে? False False

countdown() ফেরার পর দুটি local নাম মুছে গেছে, তবু দুটি object বেঁচে আছে, আর cell-কে ধরে আছে শুধু একটি list: closure-এর cells তালিকা। Cycle-হীন counter closure-টি ফেরার মুহূর্তেই মুক্ত (False), কোনো collector ছাড়া। তারপর gc.collect() ৩টি unreachable object পায়: Cell, Closure আর cells list. CPython-এর cycle collector শুধু container object (list, dict, class-এর instance) দেখে; সে প্রতিটির গণনা থেকে container-দের নিজেদের ভেতরের reference বাদ দেয়, যার গণনা তবু শূন্যের বেশি থাকে সে বাইরে থেকে ধরা, অর্থাৎ root; সেখান থেকে পৌঁছানো যায় না এমন সবাই garbage.

এবার reference VM-এর ওপর: লেখকের ল্যাবে vm.py-র কপি প্রতিটি Cell আর Closure-এ weak reference রেখে gc.disable() অবস্থায় nested.haat চালায়। সত্যিকারের run, CPython 3.14.4:

$ python -B vm_trace.py ~/haat/examples/nested.haat
OUT: 936
OUT: 15
OUT: 7
OUT: 300
OUT: 3
OUT: 2
OUT: 1
ALLOC COUNTS: {'closure': 13, 'cell': 9}
CPython, after run, gc disabled: still alive (refcount > 0): ['cell go@countdown', 'clo go']
gc.collect() found unreachable objects: 11
still alive after gc.collect(): []

আউটপুট reference-এর nested.out-এর সঙ্গে হুবহু। Program শেষে ২২টি Haat object-এর ২০টি reference counting-এই মুক্ত, কিন্তু go-র cell আর closure থেকে গেছে, ঠিক প্রস্তাব ৭৫.১ যেমন বলে। gc.collect() এখানে ১১টি Python object পেয়েছে: ল্যাবে gc.DEBUG_SAVEALL দিয়ে দেখা গেছে সেগুলো ওই Cell আর Closure, closure-এর cells list, go-র compile করা Code object (এই closure-টিই তাকে শেষ পর্যন্ত ধরে ছিল) আর Code-এর ভেতরের ৭টি list. একটি Haat-cycle মানে Python-এর হিসাবে অনেকগুলো object.

Python 3.14-এর GC নিয়ে সতর্কতা: Python-এর “What's New in 3.14” জানায়, 3.14.0–3.14.4-এ cycle collector ছিল incremental (দুটি প্রজন্ম, young আর old), কিন্তু production-এ memory চাপের অভিযোগে 3.14.5-এ 3.13-এর generational collector-এ ফেরানো হয়েছে। লেখকের যন্ত্র 3.14.4, তাই threshold (2000, 10, 0); অন্য patch version-এ সংখ্যা আলাদা হতে পারে, তাই নিজের version-এ চালিয়ে দেখুন। Cycle ধরার মূল আচরণ একই।

Swift-এর ARC-এ cycle collector নেই; প্রোগ্রামার একটি দিক weak বা unowned লিখে cycle ভাঙেন। Rust-এর Rc-এর সঙ্গে Weak, C++-এর shared_ptr-এর সঙ্গে weak_ptr একই কাজ করে (পর্ব ২৩, C++ কোর্সের পর্ব ১৭). Haat-এ প্রোগ্রামারের হাতে এমন কোনো উপায় নেই, আর প্রস্তাব ৭৫.১ বলে প্রতিটি nested recursive function-এর প্রতিটি call একটি cycle রেখে যায়। তাই Haat-এর জন্য শুধু reference counting যথেষ্ট নয়; লাগবে tracing, অথবা RC-এর পাশে একটি cycle collector.

৬ · Generational GC আর write barrier — নতুনদের আলাদা যত্ন

বাজারঘরের একটি অর্ডার প্রক্রিয়ায় হাজারো ক্ষণিকের string আর closure জন্মায় আর মরে, কিন্তু দামের তালিকা সারাদিন বাঁচে। এই পর্যবেক্ষণের নাম generational hypothesis: বেশিরভাগ object অল্প বয়সেই মরে। Lieberman ও Hewitt (১৯৮৩) আর David Ungar-এর “Generation Scavenging” (১৯৮৪, Berkeley Smalltalk) থেকে এর ওপর ভিত্তি করা collector-এর ধারা শুরু বলে ধরা হয়।

নকশা: heap দুই ভাগ। নতুন object জন্মায় young generation-এ; তাকে ঘন ঘন একটি ছোট copying collection (minor GC) দিয়ে পরিষ্কার করা হয়, যার খরচ শুধু বেঁচে যাওয়াদের সমানুপাতিক, আর hypothesis সত্য হলে তারা অল্প। কয়েকবার বেঁচে গেলে object উঠে যায় old generation-এ, যা কদাচিৎ, বড় collection-এ পরিষ্কার হয়।

ফাঁকটি হলো: minor GC old generation-এ হাঁটে না। কোনো old object যদি একটি young object-এর একমাত্র ধারক হয়, minor GC তাকে দেখবে না, মুছে দেবে, আর old object-এ থাকবে একটি dangling pointer. সমাধান: প্রতিটি pointer-লেখার সঙ্গে কয়েকটি বাড়তি নির্দেশ, যা দেখে “old object-এ young object লেখা হলো কি?”; হলে old object-টিকে একটি তালিকায় (remembered set) টুকে রাখে। Minor GC root-এর পাশাপাশি এই তালিকাও দেখে। এই বাড়তি নির্দেশগুলোই write barrier.

Haat-এ সেটি কোথায় বসবে? প্রস্তাব ৭৫.১-এর ধাপ ৩ বলেছে, নতুন object তৈরির সময় সব pointer নতুন থেকে পুরোনোর দিকে যায়; পুরোনো object-এর ভেতরে নতুন pointer আসে শুধু STORE_CELL আর STORE_FREE-এ। তাই Haat VM-এ barrier লাগে মাত্র এই দুই opcode-এ (globals আর frame-এর slot root, প্রতিটি minor GC সেগুলো এমনিই দেখে)। নিচের program-টি ঠিক এমন একটি লেখা করে:

// বাজারঘর: পুরোনো cell-এ নতুন closure লেখা
fn make_checkout() -> (Int) -> Int {
    var rule = fn(t: Int) -> Int { return t; };
    let pay = fn(t: Int) -> Int {
        if t >= 1000 { rule = fn(x: Int) -> Int { return x - x / 10; }; }
        return rule(t);
    };
    return pay;
}
let pay = make_checkout();
print(pay(500));
print(pay(1040));
print(pay(500));

Reference-এর run আর vm দুটিই ছাপে 500, 936, 450. dis-এ pay-এর ভেতরে MAKE_CLOSURE 1 ; <fn lambda@5:31> আর তারপর STORE_FREE 0 ; rule: নতুন closure পুরোনো cell-এ। নিচের JavaScript ব্লক ঘটনাগুলো দুই-প্রজন্মের heap-এ চালায়, barrier সহ আর ছাড়া, মাঝে দুটি minor GC.

// checkout.haat-এর ঘটনা, দুই প্রজন্মের heap-এ: write barrier সহ আর ছাড়া
function run(barrier) {
  const young = new Set(), old = new Set(), remembered = new Set(), g = {};
  const obj = (name, refs, fn) => { const o = { name, refs, fn }; young.add(o); return o; };
  const write = (o, v) => {                       // STORE_FREE rule
    o.refs[0] = v;
    if (barrier && old.has(o) && young.has(v)) remembered.add(o);
  };
  const minor = (tag) => {                        // শুধু young অংশ; root = global + remembered set
    const work = Object.values(g).filter(o => young.has(o));
    for (const o of remembered) work.push(...o.refs.filter(r => young.has(r)));
    const live = new Set();
    while (work.length) { const o = work.pop(); if (!live.has(o)) { live.add(o); work.push(...o.refs.filter(r => young.has(r))); } }
    const dead = [...young].filter(o => !live.has(o));
    dead.forEach(o => { o.freed = true; });
    live.forEach(o => old.add(o));
    console.log(`  ${tag}: old-এ গেল [${[...live].map(o => o.name)}], মুছল [${dead.map(o => o.name)}], remembered [${[...remembered].map(o => o.name)}]`);
    young.clear(); remembered.clear();
  };
  const pay = (t) => {                            // lambda@4:15
    const cell = g.pay.refs[0];
    if (t >= 1000) write(cell, obj("R1", [], x => x - Math.trunc(x / 10)));
    const rule = cell.refs[0];
    return rule.freed ? `ভুল: cell rule মুছে ফেলা ${rule.name}-কে দেখায়` : rule.fn(t);
  };
  console.log(barrier ? "write barrier সহ:" : "write barrier ছাড়া:");
  g.make_checkout = obj("K", []);
  const r0 = obj("R0", [], t => t), cell = obj("cell rule", [r0]);
  g.pay = obj("P", [cell]);
  console.log("  pay(500) =", pay(500)); minor("minor GC ১");
  console.log("  pay(1040) =", pay(1040)); minor("minor GC ২");
  console.log("  pay(500) =", pay(500), `∣ old-এ ${old.size}টি, তার মধ্যে R0 এখন আবর্জনা`);
}
run(true); run(false);

আউটপুট (Node 24-এ ল্যাবে, browser-এও একই):

write barrier সহ:
  pay(500) = 500
  minor GC ১: old-এ গেল [P,cell rule,R0,K], মুছল [], remembered []
  pay(1040) = 936
  minor GC ২: old-এ গেল [R1], মুছল [], remembered [cell rule]
  pay(500) = 450 ∣ old-এ 5টি, তার মধ্যে R0 এখন আবর্জনা
write barrier ছাড়া:
  pay(500) = 500
  minor GC ১: old-এ গেল [P,cell rule,R0,K], মুছল [], remembered []
  pay(1040) = 936
  minor GC ২: old-এ গেল [], মুছল [R1], remembered []
  pay(500) = ভুল: cell rule মুছে ফেলা R1-কে দেখায় ∣ old-এ 4টি, তার মধ্যে R0 এখন আবর্জনা

Barrier সহ ফল reference-এর সঙ্গে হুবহু: 500, 936, 450. Barrier ছাড়া দ্বিতীয় minor GC R1-কে মুছে দেয়, কারণ তার একমাত্র ধারক cell rule old-এ, যেখানে minor GC তাকায় না; তৃতীয় call একটি মুছে ফেলা closure ডাকতে যায়। আসল runtime-এ এটি একটি use-after-free. আর R0 garbage হয়েও old-এ বসে আছে; তাকে মুছবে শুধু বড় (major) collection.

5  if t >= 1000 { rule = fn(x: Int) … }6  return rule(t);10let pay = make_checkout();11print(pay(500));12print(pay(1040));13print(pay(500));
দুই প্রজন্ম
young
old
remembered
  1. make_checkout()। চারটি object, সবাই young-এ: closure K, প্রথম নিয়ম R0, var rule-এর cell (মান R0), আর closure P (pay, cell-টি ধরে)।
  2. pay(500). t < 1000, কিছু লেখা হয় না; ফল 500.
  3. Minor GC ১। Global থেকে চারজনই পৌঁছানো যায়; সবাই old-এ ওঠে।
  4. pay(1040): নতুন closure, পুরোনো cell. MAKE_CLOSURE R1 বানায় (young), STORE_FREE 0 তাকে cell rule-এ লেখে: old → young. Barrier cell-টিকে remembered set-এ রাখে।
  5. rule(1040). rule = R1: 1040 − 104 = 936.
  6. Minor GC ২। K আর P old, তাই তাদের ভেতরে হাঁটা হয় না; কিন্তু remembered cell R1-কে দেখায়, তাই R1 বাঁচে আর old-এ ওঠে। Barrier না থাকলে এখানেই R1 মুছে যেত।
  7. pay(500). rule = R1: 500 − 50 = 450, reference-এর সঙ্গে মিল। Old-এ ৫টি, যার R0 garbage; সে মুছবে শুধু বড় collection-এ।

বাস্তব runtime-এ remembered set প্রায়ই একটি card table: old heap-এর প্রতিটি ছোট “card”-এর জন্য একটি byte, barrier শুধু সেটি “নোংরা” চিহ্ন দেয়, আর minor GC নোংরা card-গুলো স্ক্যান করে। JIT compiler (পর্ব ৬১, JIT compilation) প্রমাণ করতে পারলে barrier বাদ দেয়, যেমন সদ্য বানানো object-এ লেখার সময়।

৭ · থামা কমানো, pointer চেনা আর বাস্তব runtime

Incremental আর concurrent — tri-colour invariant রক্ষা

এখন পর্যন্ত সব collector stop-the-world: program থামিয়ে কাজ। Incremental GC কাজটি ছোট টুকরোয় program-এর ফাঁকে ফাঁকে চালায়; concurrent GC আলাদা thread-এ পাশাপাশি চালায়। তখন mark চলার সময় program (“mutator”) pointer বদলায়, আর বিপদ নির্দিষ্ট: mutator একটি কালো object-এ সাদা object-এর pointer লেখে আর সেই সাদা object-এর শেষ ধূসর পথটি মুছে দেয়। তখন collector তাকে কখনো দেখবে না।

Tri-colour invariant আর দুই রকম barrier

Strong invariant: কোনো কালো object থেকে সাদা object-এ edge নেই। Weak invariant: কালো থেকে যে সাদা object-এ edge আছে, সে অন্তত কোনো ধূসর object থেকে সাদা-পথে পৌঁছানো যায়। দুটি প্রচলিত barrier দুটি শর্তের একটি ভাঙতে দেয় না। Insertion barrier (Dijkstra ও সহকর্মীদের ১৯৭৮ সালের “on-the-fly” collector-এর ধারা): কালো object-এ pointer লেখার সময় নতুন লক্ষ্যটিকে ধূসর করুন। Deletion barrier (Yuasa-র “snapshot-at-the-beginning” ধারা): একটি pointer মুছে ফেলার আগে পুরোনো লক্ষ্যটিকে ধূসর করুন, যাতে mark শুরুর মুহূর্তে জীবিত সবাই বাঁচে। Haat-এ দুটিই আবার সেই STORE_CELL আর STORE_FREE-এ বসত (সঙ্গে root-এর লেখার জন্য আলাদা সতর্কতা)।

Concurrent copying-এ collector object সরাতে থাকে, তাই লাগে read barrier: প্রতিটি pointer-পড়ায় “এটি কি সরে গেছে?” পরীক্ষা। Baker-এর ১৯৭৮ সালের incremental copying collector এই ধারার সূচনা বলে ধরা হয়; HotSpot-এর ZGC heap-pointer লোডের সময় এমন একটি পরীক্ষা (load barrier) চালায় বলে তার নকশা-দলিল জানায়। Go-র collector concurrent tri-colour mark-sweep, object সরায় না, আর Go 1.8 থেকে insertion ও deletion barrier-এর একটি মিশ্র রূপ ব্যবহার করে বলে Go-র নকশা-প্রস্তাবে পাওয়া যায়। Memory model-এর প্রশ্ন পর্ব ৭৭-এর (ভাষার স্তরে concurrency).

Precise বনাম conservative — কোনটি pointer?

Mark বা copy করতে collector-কে জানতে হয় একটি word pointer কি না। Haat VM-এ সেটি সহজ: Python-এর প্রতিটি মান নিজের type জানে। কিন্তু Haat যখন পর্ব ৭২-এর (Haat থেকে RISC-V assembly) মতো native code হবে, register বা stack-এর একটি 64-bit word কি Int 1040, নাকি একটি closure-এর ঠিকানা? Precise GC-এর জন্য compiler প্রতিটি safepoint-এ (call, loop-এর পেছনের লাফ, allocation; যেখানে GC চলতে পারে) একটি stack map লিখে দেয়: কোন slot আর কোন register-এ এখন pointer আছে। JVM-এর verifier-এর StackMapTable (পর্ব ৬০, বাস্তব virtual machine) আলাদা উদ্দেশ্যের হলেও একই রকম “প্রতিটি বিন্দুতে কোথায় কোন type” তথ্য।

এই তথ্য না থাকলে, যেমন C বা C++-এ, collector হয় conservative: ঠিকানার মতো দেখতে যেকোনো word-কে pointer ধরে নেয় (Boehm ও Weiser, ১৯৮৮)। দাম: কিছু garbage বেঁচে যায়, আর এমন object সরানো যায় না (প্রশ্ন ০৪ দেখুন)।

Finalizer আর weak reference

Object মোছার আগে চলা কাজ, finalizer (Python-এর __del__, Java-র পুরোনো finalize(), JavaScript-এর FinalizationRegistry), tracing GC-তে কখন চলবে তা অনির্দিষ্ট; Java 18-এ JEP 421 দিয়ে finalize() deprecated for removal. তাই ফাইল বা lock with, try-with-resources বা RAII দিয়ে নির্দিষ্ট মুহূর্তে বন্ধ করাই নিয়ম। CPython-এ cycle-হীন object-এর __del__ সাধারণত সঙ্গে সঙ্গে চলে, কিন্তু সেটি বাস্তবায়নের বৈশিষ্ট্য, ভাষার নিশ্চয়তা নয় (PyPy-তে আলাদা)।

বাস্তব runtime নিজের মুখে — সত্যিকারের log

একটি Java program বিশ লাখ ক্ষণিকের Order record বানায় আর প্রতি হাজারে একটি রেখে দেয়। লেখকের ল্যাব থেকে Wandbox-এর OpenJDK 21-এ -Xmx32m -Xlog:gc দিয়ে সত্যিকারের run (সময় ওই সার্ভারের ওই run-এর, শুধু উদাহরণ):

$ java -Xmx32m -Xlog:gc Main
[0.009s][info][gc] Using G1
[0.181s][info][gc] GC(0) Pause Young (Normal) (G1 Evacuation Pause) 7M->1M(32M) 3.920ms
[0.259s][info][gc] GC(1) Pause Young (Normal) (G1 Evacuation Pause) 18M->1M(32M) 2.295ms
[0.279s][info][gc] GC(2) Pause Young (Normal) (G1 Evacuation Pause) 19M->1M(32M) 2.718ms
…
[0.353s][info][gc] GC(8) Pause Young (Normal) (G1 Evacuation Pause) 19M->1M(32M) 1.986ms
made 2000000, kept 2000
G1 Young Generation: ran yes
G1 Concurrent GC: ran no
G1 Old Generation: ran no

প্রতিটি লাইন একটি minor GC: ব্যবহার 19M থেকে 1M-এ নামে, কারণ প্রায় সবাই মৃত, আর জীবিতদের সরানো (“Evacuation”, একধরনের copying) কয়েক মিলিসেকেন্ডের কাজ; old generation-এর collection একবারও হয়নি। G1 Java 9 থেকে HotSpot-এর ডিফল্ট; একই program -XX:+UseSerialGC দিলে log বলে Using Serial, প্রতিটি লাইন Pause Young (Allocation Failure) 9M->1M(30M), আর collector দুটির নাম Copy আর MarkSweepCompact: young-এ copying, old-এ mark-compact, ঠিক অংশ ৪-এর দুই পদ্ধতি। (-XX:+UseZGC Wandbox-এ চালু হয়নি: JVM শুরুতেই backing file-এর error দিয়ে থেমেছে, তাই ZGC-এর log এখানে নেই।) JVM-এর মেমরি-মানচিত্র আর collector বাছাই Java কোর্সের পর্ব ৪৪-এ বিস্তারিত।

V8-এর collector (প্রকল্পের নাম Orinoco), Node 24.15.0-এ (V8 13.6), লেখকের যন্ত্রে: node --trace-gc --expose-gc --max-old-space-size=32 node_gc.js. Program-টি তিন লাখ ক্ষণিকের অর্ডার বানায় আর একটি Haat-ধাঁচের cell ↔ closure cycle-কে WeakRef দিয়ে নজরে রাখে। সত্যিকারের আউটপুট, process-এর পরিচয় বাদ, মাঝের লাইন সংক্ষেপিত:

kept 30
cycle collected: true
16 ms: Scavenge 4.8 (5.9) -> 4.0 (6.9) MB, pooled: 0 MB, 0.37 / 0.00 ms  (average mu = 1.000, current mu = 1.000) allocation failure;
16 ms: Scavenge 4.8 (6.9) -> 4.2 (6.9) MB, pooled: 0 MB, 0.32 / 0.00 ms  (average mu = 1.000, current mu = 1.000) allocation failure;
…  (মোট ১৪টি Scavenge, প্রতিটি ০.২৫–০.৩৭ ms)
43 ms: Mark-Compact 7.5 (13.7) -> 4.1 (13.4) MB, pooled: 0 MB, 1.52 / 0.00 ms  (average mu = 0.961, current mu = 0.961) testing; GC in old space requested

“Scavenge” হলো V8-এর young-অংশের copying collection, আর শেষ লাইনের “Mark-Compact” এসেছে globalThis.gc()-এর ডাকে (“testing”): পুরো heap-এর mark আর compaction. সেই বড় collection-ই cycle-টি মুছেছে, তাই WeakRef-এর deref() দিয়েছে undefined (“cycle collected: true”). এই run-এ log-এর লাইনগুলো program-এর নিজের console.log-এর পরে ছাপা হয়েছে (pipe-এ output buffering-এর কারণে বলে ধারণা); আসল ক্রম বলে লাইনের শুরুর সময়ের ছাপ, 16 ms আর 43 ms. Browser-এ memory কীভাবে মাপবেন, তা JavaScript কোর্সের পর্ব ৫৩-এ.

৮ · Haat-এর জন্য কোন GC — একটি নকশার সিদ্ধান্ত

Haat-এর একটি native runtime-এর জন্য যুক্তিসঙ্গত নকশা কেমন হবে? লেখকের প্রস্তাব (নকশার যুক্তি, একমাত্র সত্য নয়):

  1. Precise, কারণ compiler সব জানে। Type checker (পর্ব ৫২) প্রতিটি মানের type জানে: Int আর Bool কখনো pointer নয়, closure আর Str সবসময়। তাই back end প্রতিটি safepoint-এ সঠিক stack map লিখতে পারে, conservative অনুমানের দরকার নেই। পর্ব ৭১-এর (Calling convention আর ABI) চুক্তিতে “কোন register-এ pointer” তথ্যও যোগ হবে।
  2. Tracing, RC নয়। প্রস্তাব ৭৫.১ বলে প্রতিটি nested recursive function-এর call একটি cycle রেখে যায়, আর Haat-এ weak নেই। RC নিতে হলে পাশে একটি cycle collector লাগবেই।
  3. Young-এ copying, old-এ mark-sweep বা mark-compact. Haat-এর বেশিরভাগ allocation ক্ষণিকের (loop-এর cell, string-এর মাঝের ফল), আর bump allocation closure বানানোকে প্রায় বিনামূল্য করে।
  4. Barrier মাত্র দুই জায়গায়। STORE_CELL আর STORE_FREE: generational barrier আর পরে incremental mark-এর barrier, দুটোরই। Closure-এর cells তালিকা জন্মের পর কখনো বদলায় না, string কখনো বদলায় না: এই অপরিবর্তনীয়তাই Haat-এর GC-কে সহজ রাখে।
  5. Space safety আগেই। পর্ব ৫৭-এর flat closure শুধু দরকারি cell ধরে; আর escape analysis (পর্ব ১৬) যে cell বাইরে যায় না বলে প্রমাণ করে, তাকে frame-এই রাখা যায়।

উল্টো নকশাটি পর্ব ৭৬-এ (Memory safety আর ownership): Rust কঠিন নিয়মের বিনিময়ে compile-এর সময়েই ফেরতের মুহূর্ত ঠিক করে, collector ছাড়া।

আরও গভীরে: David Bacon, Perry Cheng আর V. T. Rajan-এর ২০০৪ সালের OOPSLA প্রবন্ধ “A Unified Theory of Garbage Collection” দেখায় tracing আর reference counting একই সমস্যার দুই প্রান্ত (সবচেয়ে ছোট বনাম সবচেয়ে বড় fixpoint), আর বাস্তব collector-গুলো দুইয়ের মিশ্রণ। RC-এর পাশে cycle ধরার “trial deletion” Bacon ও Rajan-এর ২০০১ সালের কাজে পরিচিত। পুরো ক্ষেত্রের মানক বই Jones, Hosking ও Moss-এর “The Garbage Collection Handbook”.

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • Reference counting কোথায় হারে? Cycle-এ: পরস্পরকে ধরে রাখা object-এর গণনা শূন্য হয় না; সমাধান weak reference বা আলাদা cycle collector.
  • Mark-sweep বনাম copying? Mark-sweep: object নড়ে না, sweep পুরো heap-এর, fragmentation হয়; copying: কাজ শুধু জীবিতদের, fragmentation নেই, কিন্তু অর্ধেক heap খালি রাখতে হয়।
  • Cheney-র algorithm-এ scan আর free কী? to-space-এ free = পরের কপির জায়গা, scan = যার pointer এখনো ঠিক করা হয়নি; দুটির মাঝের অংশ ধূসর worklist, scan = free হলে শেষ।
  • Write barrier কেন লাগে? Minor GC old-এ হাঁটে না; old থেকে young-এ pointer লিখলে barrier সেটি remembered set-এ রাখে, নইলে জীবিত young object মুছে যায়।
  • Conservative GC object সরাতে পারে না কেন? সে নিশ্চিত নয় একটি word আসলে pointer কি না; Int-কে “ঠিকানা” ভেবে বদলে দিলে program-এর মান ভেঙে যাবে।

৯ · AI-এর যুগে garbage collection

GC নিয়ে AI assistant-এর উত্তর প্রায়ই আত্মবিশ্বাসী আর আধা-সত্য; এক ভাষার নিয়ম আরেক ভাষার নামে চলে আসে। বারবার দেখা ভুল:

AI-এর দাবি বা ভুলকীভাবে যাচাই করবেন
“Python-এ object সঙ্গে সঙ্গে মুছে যায়” বা উল্টো, “Python-এ শুধু tracing GC”Cycle-সহ আর cycle-ছাড়া দুটি object বানিয়ে weakref আর gc.collect() দিয়ে দেখুন, ঠিক অংশ ৫-এর মতো
এক ভাষার GC-র নিশ্চয়তা সব ভাষায় চাপানো (“finalizer সবসময় চলে”, “GC-ভাষায় leak হয় না”)ভাষার নিজের দলিল আর version দেখুন; ধরে রাখা collection বা listener দিয়ে leak বানিয়ে মাপুন
JVM flag বা threshold-এর সংখ্যা বানিয়ে বলা, পুরোনো version-এর flag দেওয়া-Xlog:gc বা java -XX:+PrintFlagsFinal, Python-এ gc.get_threshold(); নিজের version-এ চালান
Copying collector-এ forwarding pointer বা “আগে কপি হয়েছে কি না” পরীক্ষা বাদ দেওয়াদুটি root একই object দেখায় এমন graph-এ চালিয়ে কপির সংখ্যা আর aliasing মেলান
Generational বা incremental collector-এ write barrier ভুলে যাওয়া, বা ভুল opcode-এ বসানোcheckout.haat-এর মতো old → young লেখার পরীক্ষা, collection-কে জোর করে ঘন ঘন চালিয়ে (stress mode)
“X collector Y-এর চেয়ে দশ গুণ দ্রুত” ধরনের সংখ্যা উৎস ছাড়ানিজের workload-এ GC log আর মোট সময় মাপুন, যন্ত্র আর version লিখে রাখুন

Collector-এর কোড চাওয়ার সঙ্গে invariant আর পরীক্ষার তালিকাও চান, আর নিজে চালিয়ে মেলান।

আমি Haat নামের একটি ছোট ভাষার VM-এর জন্য garbage collector বানাচ্ছি। Heap-এ তিন রকম object: closure (code + cell-এর তালিকা, জন্মের পর তালিকা বদলায় না), cell (একটি মান, STORE_CELL আর STORE_FREE দিয়ে বদলায়) আর string (pointer নেই)। Root: global array, প্রতিটি frame-এর slot, আর operand stack. নিচের কাজগুলো করো: ১. Python-এ একটি Cheney copying collector লেখো; forwarding pointer কোথায় রাখছ আর scan/free-এর invariant কী, তা মন্তব্যে লেখো। ২. Young/old দুই প্রজন্ম যোগ করো, আর বলো write barrier কোন কোন opcode-এ লাগবে আর কেন বাকিগুলোয় লাগবে না। ৩. পাঁচটি test program লেখো যা এই ভুলগুলো ধরবে: forwarding বাদ পড়া, cycle মুছতে না পারা, barrier বাদ পড়া, root-এর তালিকায় operand stack ভুলে যাওয়া, আর একটি object দুবার কপি হওয়া। প্রতিটির প্রত্যাশিত আউটপুট আলাদা করে লেখো; আমি reference বাস্তবায়নে চালিয়ে মেলাব, নিশ্চিত না হলে "অনুমান" লেখো। ৪. কোনো ভাষার GC-র নিশ্চয়তা বা কোনো JVM/Python flag-এর কথা বললে version উল্লেখ করো; গতির কোনো সংখ্যা বানিয়ে দেবে না।

AI-এর লেখা collector বা GC-দাবি হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১১৯৬০ সালে প্রায় একসঙ্গে দুটি পদ্ধতি এল: McCarthy-র tracing আর Collins-এর reference counting. ছয় দশক পরেও দুটিই টিকে আছে কেন?

LISP-এর list cell-গুলো program-এর ভেতরে অবাধে ভাগ হয়: একই tail অনেক list-এর অংশ হতে পারে। প্রোগ্রামারকে free ডাকতে বললে কে শেষ ব্যবহারকারী তা জানা প্রায় অসম্ভব হতো। McCarthy-র সমাধান ছিল memory ফুরোলে থেমে root থেকে সব চিহ্ন দেওয়া; প্রায় একই সময়ে Collins প্রস্তাব দেন প্রতিটি cell-এ একটি গণনা রাখার, যাতে থামার দরকার না পড়ে। প্রথমটি “জীবিত কারা” প্রশ্ন করে, দ্বিতীয়টি “মৃত কারা”। এই পর্বে দুটির শক্তি আর দুর্বলতা একই heap-এ দেখেছেন: RC ৪টি object সঙ্গে সঙ্গে মুক্ত করেছে কিন্তু cycle-এর ২টিতে অন্ধ; tracing cycle-সহ ৬টি মুছেছে কিন্তু কাজ করেছে একবারে, থেমে।

দুটি টিকে আছে কারণ তারা ভিন্ন জিনিস কেনে। RC দেয় তাৎক্ষণিকতা আর পূর্বানুমান: object ঠিক কখন মরবে জানা থাকে, তাই ফাইল বন্ধের মতো কাজ ধ্বংসের মুহূর্তে বাঁধা যায়, আর pause প্রায় নেই। এজন্য Swift, Objective-C আর C++-এর shared_ptr RC বেছেছে, আর CPython-এর C extension-এর পুরো API reference count-এর ওপর দাঁড়িয়ে আছে, যা বদলানো প্রায় অসম্ভব। কিন্তু প্রতিটি pointer-লেখায় দুটি গণনা বদলায়, যা multi-thread পরিবেশে atomic হতে হয় আর cache-এ চাপ দেয়; আর cycle-এর জন্য weak reference বা বাড়তি collector লাগে। Tracing দেয় উচ্চ throughput: pointer-লেখা প্রায় বিনামূল্য (barrier ছাড়া), আর cycle কোনো সমস্যা নয়; বিনিময়ে মৃত্যুর মুহূর্ত অনির্দিষ্ট আর মাঝে মাঝে বিরতি।

২০০৪ সালে Bacon, Cheng আর Rajan দেখান দুটি আসলে একটি সমীকরণের দুই সমাধান: tracing সবচেয়ে ছোট fixpoint খোঁজে, RC সবচেয়ে বড়, আর মাঝের সব বাস্তব নকশা (deferred RC, যেখানে stack-এর গণনা বাদ দেওয়া হয়; generational GC-র remembered set, যা আসলে old থেকে young-এ একধরনের গণনা) দুইয়ের মিশ্রণ। CPython নিজেই মিশ্রণ: RC আর পাশে tracing-ভিত্তিক cycle collector.

মূল উপলব্ধি: “কোনটি ভালো” প্রশ্নটি ভুল; প্রশ্ন হলো কোন খরচ কোথায় দিতে রাজি: প্রতিটি লেখায় (RC) না মাঝে মাঝে একসঙ্গে (tracing), আর cycle-এর দায় প্রোগ্রামারের না runtime-এর।

প্র ০২Cheney-র algorithm আসলে breadth-first search. এর ফলে জীবিত object-গুলোর ক্রম কেমন হয়, আর সেটি program-এর গতির ওপর কী প্রভাব ফেলতে পারে?

Cheney-র to-space একটি queue-র মতো আচরণ করে: free-এ নতুন object ঢোকে (enqueue), scan থেকে তোলা হয় (dequeue). তাই কপির ক্রম root থেকে দূরত্বের স্তর অনুযায়ী: আগে সব root-এর লক্ষ্য, তারপর তাদের সন্তানেরা, তারপর নাতিরা। DSA কোর্সের পর্ব ৪০-এর BFS-এর সঙ্গে পার্থক্য শুধু একটি: queue-র জন্য আলাদা memory লাগে না, কারণ কপি করা object-গুলোই queue. ১৯৭০ সালে memory যখন অত্যন্ত দামি, এই চালাকিই algorithm-টিকে বিখ্যাত করে: recursion-এর stack উপচে পড়ার ভয় নেই, যত গভীর list-ই হোক।

কিন্তু BFS-ক্রম সবসময় program-এর ব্যবহারের ক্রমের সঙ্গে মেলে না। ধরুন একটি লম্বা linked list: program প্রতিটি node পড়ার পরেই তার পরের node পড়ে। Depth-first কপি করলে node-গুলো পাশাপাশি বসত, cache-এর একটি line-এ কয়েকটি। BFS-এ একটি node আর তার পরের node-এর মাঝে অন্য শাখার object বসে যেতে পারে, ফলে cache miss বাড়ে। Haat-এ একটি closure আর তার cell-গুলো এই পর্বের উদাহরণে পাশাপাশি বসেছে (A, A.count, A.step = 2, 3, 4) কারণ graph ছোট; বড় graph-এ একই closure-এর cell দূরে চলে যেতে পারে।

গবেষণায় এর উত্তর হিসেবে নানা কৌশল প্রস্তাবিত হয়েছে: approximately depth-first copying (Moon-এর ১৯৮৪ সালের কাজ এ ধারার বলে পরিচিত), hierarchical decomposition, আর runtime-এর profiling দেখে কাছাকাছি ব্যবহৃত object একসঙ্গে রাখা। Mark-compact-এর sliding রূপ আবার জন্মক্রম রক্ষা করে, যা প্রায়ই ব্যবহারের ক্রমের ভালো অনুমান। মোট কথা, copying collector শুধু memory ফেরত দেয় না, সে object-এর বসার জায়গাও ঠিক করে, আর সেই সিদ্ধান্ত program-এর গতিতে দেখা যায়।

মূল উপলব্ধি: যে collector object সরায়, সে memory layout-এর মালিক; তার traversal-ক্রম (BFS, DFS, জন্মক্রম) program-এর cache-আচরণের অংশ হয়ে যায়।

প্র ০৩Generational hypothesis কি সবসময় সত্য? কোন ধরনের program-এ এটি ভাঙে, আর তখন generational collector-এর কী হয়?

Hypothesis একটি পর্যবেক্ষণ, নিয়ম নয়। Ungar-এর Smalltalk থেকে শুরু করে বহু ভাষার মাপে দেখা গেছে, সাধারণ program-এর বেশিরভাগ object খুব অল্প সময় বাঁচে: একটি function-এর মাঝের ফল, string জোড়ার টুকরো, loop-এর এক round-এর closure. এই পর্বের Java run-এ ঠিক তা দেখেছেন: বিশ লাখ object, প্রতিটি minor GC-র পর জীবিত মাত্র প্রায় 1M, আর old generation-এর collection একবারও লাগেনি।

কিন্তু কিছু workload উল্টো। একটি cache বা LRU table-এর কথা ভাবুন: object-গুলো মাঝারি সময় বাঁচে, young-এ কয়েকটি collection পার করে old-এ ওঠে, তারপর সেখানে মরে। তখন minor GC বারবার একই object কপি করে (খরচ), promotion old-কে ভরিয়ে দেয়, আর old-এর বড় collection ঘন ঘন লাগে। আরেকটি সমস্যা হলো old থেকে young-এ অনেক pointer: একটি বড়, দীর্ঘজীবী data structure যদি ক্রমাগত নতুন object-কে দেখায় (যেমন একটি queue-তে নতুন অর্ডার রাখা), write barrier-এর খরচ আর remembered set-এর আকার দুটিই বাড়ে, আর minor GC-কে বড় অংশ স্ক্যান করতে হয়।

বাস্তব collector তাই নানা সামঞ্জস্য রাখে: survivor space-এ কয়েকবার বয়স গুনে তবে promotion (HotSpot-এর tenuring threshold), young-এর আকার স্বয়ংক্রিয়ভাবে বদলানো, আর G1-এর মতো region-ভিত্তিক নকশা যেখানে প্রজন্ম কোনো স্থির ঠিকানার ভাগ নয়। কিছু collector প্রজন্মই রাখে না: Go-র collector লেখার সময় পর্যন্ত non-generational বলে জানা যায়, কারণ escape analysis অনেক ক্ষণিকের object আগেই stack-এ সরিয়ে দেয় আর কম pause-এর লক্ষ্যে barrier সরল রাখা হয়। ZGC-ও প্রথমে non-generational ছিল, পরে Java 21-এ generational রূপ এসেছে।

মূল উপলব্ধি: Generational GC একটি বাজি যে বেশিরভাগ object অল্প বয়সে মরবে; বাজি জিতলে বিরাট লাভ, হারলে barrier আর promotion-এর খরচ। নিজের workload-এ GC log পড়েই জানা যায় বাজি জিতছে কি না।

প্র ০৪C বা C++-এর মতো ভাষায় precise GC প্রায় অসম্ভব কেন, আর conservative GC তবু কীভাবে কাজ চালায়? Haat-এর native back end-এর জন্য এর শিক্ষা কী?

Precise GC-র মূল শর্ত: প্রতিটি word-এর ব্যাপারে নিশ্চিত হওয়া সেটি pointer কি না। C-তে এই তথ্য হারিয়ে যায় অনেক পথে। একটি pointer-কে uintptr_t-এ cast করে integer হিসেবে রাখা বৈধ; union-এ একই ঘর কখনো pointer, কখনো সংখ্যা; pointer-এর নিচের bit-এ flag লুকানো চলে; আর optimizer register-এ একটি pointer থেকে offset বিয়োগ করা মান রাখতে পারে, যা আসলে কোনো object-এর শুরু নয় (interior pointer). Compiler চাইলে stack map লিখতে পারত, কিন্তু ভাষা নিজেই নিশ্চয়তা দেয় না যে type-তথ্য সত্য।

Boehm আর Weiser-এর ১৯৮৮ সালের collector তাই সাবধানী অনুমান করে: stack, register আর global data-র যে word-কে heap-এর কোনো বরাদ্দ ঘরের ঠিকানা (বা ভেতরের ঠিকানা) বলে মনে হয়, তাকে pointer ধরা হয়। এটি নিরাপদ দিকে ভুল করে: একটি সংখ্যা ঘটনাক্রমে ঠিকানার মতো দেখালে একটি মৃত object বেঁচে যায়, কিন্তু কোনো জীবিত object কখনো মোছে না। দাম দুটি: কিছু leak, আর object সরানো নিষেধ, কারণ সেই “pointer” আসলে সংখ্যা হলে তাকে নতুন ঠিকানায় বদলে দেওয়া program-এর হিসাব নষ্ট করবে। তাই এমন collector সাধারণত mark-sweep. কিছু runtime মাঝামাঝি পথ নেয়: stack conservative-ভাবে স্ক্যান, কিন্তু heap-এর object-এর ভেতর precise; তখন stack থেকে দেখানো object গুলো স্থির রেখে বাকিদের সরানো যায় (mostly-copying, Bartlett-এর ধারণা বলে পরিচিত)।

Haat-এর শিক্ষা উৎসাহজনক। Type checker জানে কোন মান Int আর কোনটি closure; Haat-এ cast, union বা pointer-গণিত নেই। তাই back end প্রতিটি safepoint-এ সঠিক stack map লিখতে পারে, আর runtime precise, সরানো-যায় এমন (copying) collector নিতে পারে। শর্ত একটিই: optimizer (পর্ব ৬৫–৬৭) কোনো pointer-কে এমন রূপে বদলাবে না যা stack map চিনতে পারে না, আর register allocator (পর্ব ৭০) প্রতিটি safepoint-এ কোন register-এ pointer আছে তা লিখে রাখবে। LLVM-এ এই কাজের জন্য statepoint নামে একটি ব্যবস্থা আছে বলে তার দলিল জানায়।

মূল উপলব্ধি: GC-র ক্ষমতা নির্ভর করে compiler কতটা সত্য তথ্য দিতে পারে তার ওপর; শক্ত type system শুধু ভুল ধরে না, runtime-কে উন্নত collector বেছে নেওয়ার স্বাধীনতাও দেয়।

প্র ০৫Concurrent GC-তে program আর collector একসঙ্গে চলে। Dijkstra-র ১৯৭৮ সালের tri-colour ধারণা কোন বিপদ ঠেকায়, আর barrier-এর দাম কে দেয়?

Dijkstra, Lamport ও সহকর্মীদের ১৯৭৮ সালের প্রবন্ধ “On-the-fly garbage collection: an exercise in cooperation” প্রশ্ন তোলে: collector যদি নিজের processor-এ program-এর পাশাপাশি চলে, কোন নিয়ম মানলে সে কখনো জীবিত object মুছবে না? তাঁদের উত্তর ছিল তিন রঙের ভাষা আর একটি invariant: কোনো কালো node সরাসরি সাদা node-কে দেখাবে না। এই পর্বের প্রস্তাব ৭৫.২-এর প্রমাণ ঠিক এই invariant-এর ওপর দাঁড়িয়ে; program থেমে থাকলে এটি নিজে থেকেই টেকে, চললে পাহারা লাগে।

বিপদটি দুই ঘটনার মিলন: program একটি সাদা object-এর pointer একটি কালো object-এ লেখে, আর একই সময়ে সেই সাদা object-এর শেষ ধূসর-পথটি মুছে দেয়। দুটি একসঙ্গে না ঘটলে ক্ষতি নেই। তাই দুই রকম পাহারা: লেখার সময় নতুন লক্ষ্যকে ধূসর করা (insertion barrier, Dijkstra-ধারা), অথবা মোছার সময় পুরোনো লক্ষ্যকে ধূসর করা (deletion barrier, Yuasa-র snapshot-at-the-beginning ধারা)। প্রথমটি বেশি সাবধানী নয়, কিন্তু stack-এর লেখায় barrier না থাকলে শেষে stack আবার স্ক্যান করতে হয়; দ্বিতীয়টি mark শুরুর মুহূর্তের সব জীবিতকে বাঁচায়, ফলে কিছু garbage এক চক্র দেরিতে মোছে। Go-র collector দুটি মিশিয়ে stack আবার স্ক্যানের প্রয়োজন কমিয়েছে বলে তার নকশা-প্রস্তাব জানায়।

দামটি দেয় program নিজে: প্রতিটি pointer-লেখায় (আর read barrier থাকলে প্রতিটি pointer-পড়ায়) বাড়তি নির্দেশ, যা throughput কমায়। বিনিময়ে বিরতি ছোট হয়, যা interactive server বা UI-এর জন্য জরুরি। তাই runtime-গুলো ভিন্ন জায়গায় দাঁড়ায়: HotSpot-এর Parallel GC throughput-কেন্দ্রিক, ZGC আর Shenandoah কম বিরতির দিকে; এমনকি একই JVM-এ flag দিয়ে বাছা যায়। Haat-এর সৌভাগ্য: barrier লাগবে মাত্র দুটি opcode-এ, তাই তার খরচ সীমিত আর মাপা সহজ।

মূল উপলব্ধি: Concurrent GC মানে collector আর program-এর মধ্যে একটি চুক্তি; barrier সেই চুক্তির program-পক্ষের কিস্তি, আর throughput বনাম বিরতির আপস এই কিস্তির আকারেই ঠিক হয়।

অনুশীলন

প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। প্রতিটি সংখ্যা আর আউটপুট ল্যাবে CPython 3.14.4-এ, Haat reference বাস্তবায়নের সঙ্গে মিলিয়ে নেওয়া।

  1. বাস্তবায়ন — Haat VM-এ generational barrier: Reference-এর vm.py-র ধাঁচে একটি VM ধরুন, যেখানে প্রতিটি heap object-এর একটি old flag আছে আর minor GC সব বেঁচে যাওয়াকে সঙ্গে সঙ্গে old করে। (ক) STORE_CELL আর STORE_FREE-এর জন্য barrier-সহ কোড লিখুন। (খ) MAKE_CLOSURE, MAKE_CELL, STORE_GLOBAL আর STORE_LOCAL-এ কেন barrier লাগে না, প্রতিটির এক লাইনের কারণ দিন। (গ) যদি বেঁচে যাওয়ারা কয়েক collection young-এ থেকে তবে old হয় (বয়স গোনা), তাহলে কোন নতুন জায়গায় remembered set-এ entry লাগবে?
    def barrier(holder, value, remembered):   # HeapStr: জোড়া লাগানো string-এর class (ধরে নেওয়া)
        if getattr(holder, "old", False) and isinstance(value, (Cell, Closure, HeapStr)) \
                and not getattr(value, "old", False):
            remembered.add(holder)            # old → young: পরের minor GC-তে root
    
    elif op == "STORE_CELL":
        cell, v = f.slots[arg], stack.pop()
        barrier(cell, v, remembered); cell.value = v
    elif op == "STORE_FREE":
        cell, v = f.closure.cells[arg], stack.pop()
        barrier(cell, v, remembered); cell.value = v

    (খ) MAKE_CLOSURE: নতুন (young) closure পুরোনো cell-কে দেখায়, young → old, যা minor GC-র জন্য নিরাপদ। MAKE_CELL: নতুন cell stack-এর একটি আগের মানকে দেখায়, আবারও নতুন → পুরোনো। STORE_GLOBAL/DEFINE_GLOBAL/STORE_LOCAL: global আর slot heap-object নয়, root; প্রতিটি minor GC সব root এমনিই দেখে। এটিই প্রস্তাব ৭৫.১-এর ধাপ ৩ আর ৪-এর প্রয়োগ। (গ) Promotion-এর মুহূর্তে: একটি object old হচ্ছে কিন্তু তার কোনো pointer এখনো young-এ থাকা object-এ যায়, তাহলে সেই নতুন old object-টিকেও remembered set-এ রাখতে হবে। বাস্তব collector এটি promotion-এর কোডেই করে। checkout.haat-এ যাচাই: ল্যাবের JavaScript মডেলে barrier সহ 500, 936, 450, ছাড়া তৃতীয় call মুছে ফেলা closure-এ ঢোকে।

  2. ভুল খুঁজুন — forwarding-হীন Cheney: একজন সহকর্মী (বা একটি AI) Cheney-র copy সরল করেছেন: def copy(o): to.append([o, list(allobjs[o][1])]); return len(to) - 1, অর্থাৎ “আগে কপি হয়েছে কি না” দেখা বাদ। heap_demo.haat-এর একই heap-এ (root: M, D, A, A) চালালে (ক) কতগুলো কপি হবে, কোনগুলো? (খ) Collection-এর পর print(a() + b()); কী ছাপবে, আর সঠিক উত্তর কী? (গ) Heap-এ একটি জীবিত cycle থাকলে কী হতো?

    (ক) ল্যাবে চালানো ফল: ৮টি কপি, ক্রমে ['M', 'D', 'A', 'A', 'A.count', 'A.step', 'A.count', 'A.step']. Root a আর b দুটি আলাদা A পায় (to[2] আর to[3]), আর প্রতিটির নিজের দুটি cell-কপি। (খ) a আর b এখন দুটি আলাদা counter: a() = 1, b() = 1, ছাপা হয় 2; সঠিক উত্তর 3, কারণ একই counter-এ 1 + 2 হয়। দুটি আলাদা counter-এর ফল 2, ল্যাবে reference-এ b = make_counter(1); দিয়ে চালিয়ে মিলেছে। Collector program-এর অর্থ বদলে দিয়েছে: aliasing ভেঙেছে। (গ) জীবিত cycle থাকলে (যেমন go চলার সময় cG ↔ G) copy প্রতিবার নতুন কপি বানাত, free কখনো থামত না: অসীম loop, যতক্ষণ না to-space ফুরায়। Forwarding pointer একসঙ্গে দুটি কাজ করে: identity রক্ষা আর cycle-এ থামা।

  3. হিসাব — mark-compact হাতে: heap_demo.haat-এ let a-কে var a, আর b = a;-কে a = b; করা হলো (reference-এ আউটপুট 30, তারপর শেষ)। জন্মক্রমে ঠিকানা: 0 M, 1 D, 2 A.step, 3 A.count, 4 A, 5 B.step, 6 B.count, 7 B, 8 S, 9 cG, 10 G; A-এর pointer [3, 2], B-এর [6, 5], cG → 10, G → 9. note = "শেষ";-এর পর একটি sliding mark-compact চললে (ক) কে কে জীবিত, (খ) প্রত্যেকের নতুন ঠিকানা, (গ) B-এর নতুন pointer, (ঘ) compaction-এর পর পরের allocation কোন ঠিকানায়?

    (ক) Root: make_counter → M, countdown → D, a আর b দুটোই → B; note literal. B থেকে B.count আর B.step. জীবিত: M, D, B.step, B.count, B (৫টি)। A-দল এবার garbage. ল্যাবের snapshot-ও ঠিক এই ৫টিকে LIVE দেখিয়েছে। (খ) Pass ১, ঠিকানা ক্রমে জীবিতদের নতুন জায়গা: 0 → 0, 1 → 1, 5 → 2, 6 → 3, 7 → 4. (গ) Pass ২: B-এর [6, 5] হয় [3, 2]; root a, b 7 থেকে 4. Pass ৩: সরানো; ফল [M, D, B.step, B.count, B(3, 2)], ল্যাবের ছোট script-এর আউটপুটের সঙ্গে মিল। (ঘ) Bump pointer এখন 5-এ, তাই পরের object ঠিকানা 5-এ। জন্মক্রম রক্ষা পেয়েছে: B-এর cell দুটি এখনো B-এর আগে।

  4. আউটপুট অনুমান — কত leak: heap_demo.haat-এ countdown(2);-এর পরে আরও দুটি লাইন যোগ হলো: countdown(5); আর countdown(1);. (ক) শুধু reference counting থাকলে program শেষে কতগুলো Haat object leak করবে? (খ) go-র recursion-এর গভীরতা (5 বনাম 1) কি উত্তর বদলায়? (গ) মোট কতটি closure আর কতটি cell allocate হবে (<main>-সহ)?

    (ক) ৬টি: প্রতিটি countdown call একটি নতুন cell go আর একটি নতুন closure G বানিয়ে STORE_CELL দিয়ে cycle করে, আর তিনটি call তিনটি cycle রেখে যায়। ল্যাবে reference VM-এর কপি gc.disable() অবস্থায় চালালে run-শেষে জীবিত পাওয়া গেছে ঠিক তিন জোড়া: cell go@countdown, clo go, clo go#2, clo go#3 আর তাদের তিনটি cell. (খ) না। go(i - 1)-এর call নতুন frame বানায়, নতুন heap object নয়। (গ) ল্যাবের গণনা: closure ৮টি (<main>, M, D, A, B আর তিনটি G), cell ৭টি (A-এর দুটি, B-এর দুটি, তিনটি cG), string ১টি।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমএকটি Cheney copying collection-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. to-space খালি ধরা, scan আর free দুটোই শুরুতে
  2. প্রতিটি root-এর লক্ষ্য to-space-এ কপি করা আর পুরোনো জায়গায় forwarding pointer লেখা
  3. scan-এর object-এর প্রতিটি pointer কপি বা forwarding দিয়ে নতুন ঠিকানায় বদলানো
  4. scan এক ঘর এগিয়ে আবার একই কাজ, যতক্ষণ scan free-এর পেছনে
  5. scan আর free সমান হলে from-space আর to-space-এর ভূমিকা বদল

একটি ভাষার runtime শুধু reference counting ব্যবহার করে (কোনো cycle collector নেই)। একটি function-এর ভেতরে একটি cell আর একটি closure বানানো হলো, যেখানে closure cell-টিকে ধরে আর cell-এর মান সেই closure. Function ফিরে যাওয়ার পর কী হবে?

  • দুটিই সঙ্গে সঙ্গে মুক্ত হবে, কারণ frame মুছে গেছে
  • আগে closure, পরে cell মুক্ত হবে
  • দুটিই চিরকাল থেকে যাবে, কারণ প্রত্যেকের গণনা ১
  • Runtime একটি error দিয়ে program থামাবে

Cheney-র copying collector-এ to-space-এর দুটি index, scan আর free. কোন মুহূর্তে collection শেষ হয়?

  • যখন free to-space-এর শেষে পৌঁছায়
  • যখন scan আর free সমান হয়
  • যখন সব root কপি হয়ে যায়
  • যখন from-space-এর সব garbage গোনা শেষ হয়

একটি heap-এ ১০,০০০টি object, যার মাত্র ১০০টি জীবিত। Mark-sweep collector-এর কোন অংশের কাজ মোট heap-এর আকারের সমানুপাতিক?

  • Mark phase
  • Root স্ক্যান
  • Pointer-গুলো নতুন ঠিকানায় বদলানো
  • Sweep phase

Haat-এর stack VM-এ heap object হলো closure (জন্মের পর তার cell-তালিকা বদলায় না), cell আর string. একটি generational collector-এর write barrier কোন opcode-গুলোতে দরকার?

  • STORE_CELL আর STORE_FREE
  • MAKE_CLOSURE আর MAKE_CELL
  • STORE_GLOBAL আর STORE_LOCAL
  • VM-এর প্রতিটি opcode-এ

একটি conservative garbage collector (যেমন C program-এর জন্য Boehm–Weiser ধাঁচের) সাধারণত object সরাতে (copy বা compact) পারে না। কেন?

  • কারণ object সরানো খুব ধীর
  • কারণ C-তে memory কপি করা যায় না
  • কারণ সে নিশ্চিত নয় কোন word আসলে pointer, তাই “pointer” বদলানো বিপজ্জনক
  • কারণ সরালে fragmentation বেড়ে যায়

Java 21-এ -Xlog:gc দিয়ে চালানো একটি program-এর log-এ এই লাইন: GC(1) Pause Young (Normal) (G1 Evacuation Pause) 18M->1M(32M) 2.295ms. এর সবচেয়ে সঠিক ব্যাখ্যা কোনটি?

  • পুরো heap-এর একটি full GC, যা 32M মুক্ত করেছে
  • Young-অংশের একটি collection, যাতে ব্যবহার 18M থেকে 1M হয়েছে আর বিরতি প্রায় 2.3 ms
  • Program না থামিয়ে চলা একটি concurrent collection
  • Heap-এর আকার 18M থেকে কমিয়ে 1M করা হয়েছে

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Garbage = unreachable: root (global, frame-এর slot, operand stack) থেকে pointer ধরে যা পাওয়া যায় না। Haat-এর heap-এ শুধু closure, cell আর জোড়া লাগানো string; Int আর Bool সরাসরি মান।
  2. Reference counting: আগে বাড়ানো, পরে কমানো; শূন্যে সঙ্গে সঙ্গে মুক্তি। Cycle-এ অন্ধ: heap_demo.haat-এ ৪টি মুক্ত, ২টি (cG ↔ G) leak; CPython-এ সেই cycle ধরে আলাদা cycle collector.
  3. Haat-এর cycle আর old → young pointer: দুটিই জন্মায় শুধু STORE_CELL আর STORE_FREE-এ (প্রস্তাব ৭৫.১), তাই barrier লাগে মাত্র এই দুই জায়গায়।
  4. Tracing: mark-sweep (mark জীবিতের, sweep পুরো heap-এর সমানুপাতিক; fragmentation), Cheney copying (শুধু জীবিত; scan/free; forwarding identity রাখে), mark-compact (এক প্রান্তে গোছানো, জন্মক্রম রক্ষা)।
  5. বাস্তব runtime: generational (G1-এর “Pause Young”, V8-এর “Scavenge”); concurrent হলে tri-colour invariant আর barrier; precise হলে compiler-এর stack map.

পরের পর্বে: GC চলার সময় খুঁজে memory ফেরত নেয়। পর্ব ৭৬-এ (Memory safety আর ownership) দেখবেন উল্টো পথ: Rust-এর borrow checker compile-এর সময়েই প্রমাণ করে কোন ঘর কখন ফেরত যাবে, কোনো collector ছাড়া, আর Haat-এর জন্য একটি ছোট borrow checker বানানো।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান