Topik ini memperkenalkan dua strategi pengelolaan memori pada runtime, yaitu mark-sweep dan reference counting, dengan implementasi mini yang dapat dieksekusi. Pembaca memperoleh kelas Heap dengan algoritma mark-sweep yang membangun root set, melakukan traversal untuk menandai objek hidup, lalu menyapu objek mati, kelas RefCountGC dengan reference counting, serta demo yang memperlihatkan kegagalan reference counting pada referensi siklis. Implementasi pada topik ini berdiri sendiri dan tidak terintegrasi dengan StackVM pada modul 5, sebab bahasa mini v1 belum memerlukan pengumpulan sampah otomatis. Tujuannya adalah menunjukkan algoritma dasar yang dibutuhkan ketika objek berlapis ditambahkan ke runtime. Setelah membaca topik ini, pembaca dapat menjelaskan tiga langkah mark-sweep, menjelaskan kelebihan dan kekurangan reference counting, dan menjelaskan mengapa siklus referensi tidak dapat dikumpulkan oleh reference counting murni.
Algoritma mark-sweep#
Mark-sweep bekerja dalam tiga langkah yang berurutan. Langkah pertama adalah menetapkan root set, yaitu kumpulan objek yang masih terjangkau dari program, biasanya berupa variabel global, variabel lokal pada seluruh frame di call stack, dan register mesin. Langkah kedua adalah traversal: dimulai dari root, algoritma menelusuri referensi keluar pada setiap objek dan menandai setiap objek yang dikunjungi. Penandaan ini mencegah kunjungan berulang sehingga traversal berhenti walaupun graf memuat siklus. Langkah ketiga adalah sweep: seluruh objek pada heap diperiksa, dan objek yang tidak ditandai dianggap mati, lalu dibebaskan.
Pemilihan root set adalah titik kritis pada algoritma ini. Bila sebuah objek terlewat dari root set padahal seharusnya hidup, algoritma akan salah mengumpulkannya sebagai sampah, sehingga program akan mengakses memori yang sudah dibebaskan. Sebaliknya, bila root set terlalu lebar, objek yang sebenarnya mati tetap dianggap hidup, sehingga kebocoran memori terjadi. Pada bahasa dengan ekstensi native, akar juga mencakup referensi yang disimpan oleh kode native, sehingga interaksi antara pengumpul sampah dan kode native perlu didaftarkan secara eksplisit melalui handle atau root barrier.
Traversal pada langkah kedua biasanya dilakukan dengan depth-first search atau breadth-first search. Pada implementasi referensi, depth-first search digunakan dengan stack eksplisit agar tidak menambah beban pada call stack rekursif yang dapat meluap untuk graf yang dalam. Setiap objek memiliki field marked yang direset pada awal setiap ronde pengumpulan. Bila objek sudah ditandai, traversal tidak melanjutkan, sehingga objek yang termasuk dalam siklus hanya dikunjungi sekali. Inilah yang membuat mark-sweep mampu mengumpulkan siklus dengan benar, berbeda dari reference counting.
Reference counting dan kegagalan pada siklus#
Reference counting memelihara jumlah referensi yang menunjuk ke setiap objek. Setiap kali referensi ditambahkan, refcount naik satu, dan setiap kali referensi dilepas, refcount turun satu. Bila refcount mencapai nol, objek segera dibebaskan, tanpa menunggu ronde pengumpulan. Sifat langsung ini menjadi kelebihan utama: deallokasi terjadi pada saat yang tepat sehingga tidak ada jeda yang dirasakan oleh program, dan memori yang dibebaskan dapat segera digunakan lagi.
Kelebihan reference counting sekaligus membawa kekurangan yang sulit dihilangkan. Bila dua objek saling merujuk, refcount keduanya tidak pernah mencapai nol, sebab setiap pelepasan referensi dari luar hanya menurunkan refcount ke satu, bukan nol. Akibatnya, pasangan objek tetap hidup padahal tidak ada lagi referensi dari luar yang menunjuk ke keduanya. Kondisi ini disebut cycle leak dan terjadi pada referensi siklis sebanyak apa pun, baik dua objek maupun rantai yang lebih panjang. Perbaikan yang umum dilakukan adalah memadukan reference counting dengan algoritma pelacak siklus, atau memadukan dengan mark-sweep yang berjalan sesekali untuk membersihkan siklus yang lolos.
Implementasi referensi#
Berkas gc_demo.py berisi kelas Heap dengan mark_sweep, kelas RefCountGC dengan collect, kelas objek masing-masing, dan dua demo. Pada mark-sweep, traversal menggunakan stack eksplisit sehingga tidak bergantung pada recursion limit Python. Pada reference counting, kelas RefCountObject menyimpan refcount eksplisit dan menambahnya pada link, sedangkan pelepasan akar dilakukan dengan release di luar kelas.
"""Mark-sweep dan reference counting mini.
Topik ini memperkenalkan dua strategi pengelolaan memori pada runtime,
yaitu mark-sweep dan reference counting. Implementasi ini berdiri
sendiri dan tidak terintegrasi dengan VM modul 5.
Antarmuka:
GCObject(id, slots) objek dengan daftar referensi keluar
Heap.mark_sweep(roots) kumpulkan objek mati, kembalikan statistik
RefCountGC.collect() kumpulkan objek dengan refcount == 0
"""
from typing import Any
class GCObject:
"""Objek pada heap mini. Setiap objek punya id unik dan daftar
referensi keluar (field) yang dapat menunjuk ke objek lain."""
_next_id = 0
def __init__(self, name: str, fields: list["GCObject"] | None = None) -> None:
GCObject._next_id += 1
self.id = GCObject._next_id
self.name = name
self.fields: list[GCObject] = fields or []
self.marked = False
def __repr__(self) -> str:
refs = ", ".join(f.name for f in self.fields)
return f"GCObject({self.name}, refs=[{refs}])"
class Heap:
"""Heap mini dengan algoritma mark-sweep.
Root set adalah daftar objek yang masih terjangkau dari program.
Traversal menandai seluruh objek hidup, lalu sweep membebaskan
objek yang tidak ditandai.
"""
def __init__(self) -> None:
self.objects: list[GCObject] = []
def alloc(self, obj: GCObject) -> GCObject:
self.objects.append(obj)
return obj
def _mark(self, root: GCObject) -> None:
# DFS dari root, tanda setiap objek yang dikunjungi
stack: list[GCObject] = [root]
while stack:
obj = stack.pop()
if obj.marked:
continue
obj.marked = True
for f in obj.fields:
if not f.marked:
stack.append(f)
def mark_sweep(self, roots: list[GCObject]) -> dict[str, int]:
# reset mark
for obj in self.objects:
obj.marked = False
# mark dari setiap root
for r in roots:
self._mark(r)
# sweep: keluarkan objek yang tidak ditandai
alive: list[GCObject] = []
dead: list[GCObject] = []
for obj in self.objects:
if obj.marked:
alive.append(obj)
else:
dead.append(obj)
self.objects = alive
for obj in dead:
obj.marked = False
return {"alive": len(alive), "dead": len(dead), "total": len(alive) + len(dead)}
class RefCountGC:
"""Manajemen memori berbasis reference counting.
Setiap objek menyimpan refcount. Saat refcount turun ke nol,
objek dibebaskan segera. Strategi ini sederhana, tetapi gagal
pada referensi siklis: dua objek yang saling merujuk tidak
pernah mencapai refcount nol, sehingga bocor.
"""
def __init__(self) -> None:
self.objects: dict[int, "RefCountObject"] = {}
def alloc(self, name: str) -> "RefCountObject":
obj = RefCountObject(name, self)
self.objects[obj.id] = obj
return obj
def collect(self) -> dict[str, int]:
# bebaskan objek dengan refcount == 0
freed = []
for oid, obj in list(self.objects.items()):
if obj.refcount == 0:
freed.append(obj)
del self.objects[oid]
return {"alive": len(self.objects), "freed": len(freed)}
def stats(self) -> dict[str, int]:
return {"alive": len(self.objects)}
class RefCountObject:
"""Objek dengan reference counting eksplisit."""
_next_id = 0
def __init__(self, name: str, gc: RefCountGC) -> None:
RefCountObject._next_id += 1
self.id = RefCountObject._next_id
self.name = name
self.refcount = 1
self.gc = gc
self.fields: list["RefCountObject"] = []
def add_ref(self) -> None:
self.refcount += 1
def release(self) -> None:
self.refcount -= 1
def link(self, other: "RefCountObject") -> None:
self.fields.append(other)
other.add_ref()
def __repr__(self) -> str:
return f"RefCount({self.name}, ref={self.refcount})"
def main() -> None:
print("=== Mark-sweep ===")
heap = Heap()
a = heap.alloc(GCObject("a"))
b = heap.alloc(GCObject("b"))
c = heap.alloc(GCObject("c"))
d = heap.alloc(GCObject("d")) # akan menjadi mati
e = heap.alloc(GCObject("e")) # akan menjadi mati
# graf: a -> b -> c, d -> e (d dan e tidak terjangkau dari root)
a.fields.append(b)
b.fields.append(c)
d.fields.append(e)
print(f"sebelum: total = {len(heap.objects)} objek")
print(f" {[o.name for o in heap.objects]}")
print(f"roots = [a]")
print(f"graf : a -> b -> c, d -> e (d dan e lepas)")
stat = heap.mark_sweep(roots=[a])
print(f"sesudah: alive = {stat['alive']}, dead = {stat['dead']}")
print(f" {[o.name for o in heap.objects]}")
print()
print("=== Reference counting dengan cycle ===")
RefCountObject._next_id = 0
rc = RefCountGC()
x = rc.alloc("x")
y = rc.alloc("y")
# siklus: x -> y -> x
x.link(y)
y.link(x)
print(f"sebelum release: {rc.stats()}")
print(f" x.refcount = {x.refcount}, y.refcount = {y.refcount}")
# lepas referensi akar ke x dan y
x.release() # refcount x turun dari 2 ke 1 (karena y masih merujuk)
y.release() # refcount y turun dari 2 ke 1 (karena x masih merujuk)
print(f"setelah release akar:")
print(f" x.refcount = {x.refcount}, y.refcount = {y.refcount}")
stat = rc.collect()
print(f"rc.collect(): alive = {stat['alive']}, freed = {stat['freed']}")
print(f" (siklus x <-> y tidak terkumpul karena refcount tidak nol)")
if __name__ == "__main__":
main()Demo pertama mengalokasikan lima objek dengan dua subgraf. Subgraf a -> b -> c terjangkau dari root a, sedangkan subgraf d -> e tidak memiliki root. Setelah mark_sweep(roots=[a]), tiga objek hidup dan dua objek mati dibebaskan, sehingga heap menyisakan a, b, dan c. Demo kedua membangun dua objek x dan y yang saling merujuk. Setelah referensi akar dilepas, refcount keduanya turun ke satu, bukan nol, sehingga rc.collect() tidak membebaskan apa pun. Keluaran berikut diperoleh dengan menjalankan python3 gc_demo.py.
=== Mark-sweep ===
sebelum: total = 5 objek
['a', 'b', 'c', 'd', 'e']
roots = [a]
graf : a -> b -> c, d -> e (d dan e lepas)
sesudah: alive = 3, dead = 2
['a', 'b', 'c']
=== Reference counting dengan cycle ===
sebelum release: {'alive': 2}
x.refcount = 2, y.refcount = 2
setelah release akar:
x.refcount = 1, y.refcount = 1
rc.collect(): alive = 2, freed = 0
(siklus x <-> y tidak terkumpul karena refcount tidak nol)Keluaran memperlihatkan dua perbedaan inti. Pada mark-sweep, dua objek yang lepas dari root berhasil dikumpulkan tanpa peduli pada jumlah referensi internal. Pada reference counting, siklus x <-> y tidak terkumpul karena refcount keduanya tetap satu walaupun referensi dari luar sudah dilepas, sehingga memori yang seharusnya bebas tetap dialokasikan.
Kesalahan umum#
Kesalahan paling sering pada mark-sweep adalah lupa mereset field marked sebelum ronde baru. Bila field itu masih bernilai True dari ronde sebelumnya, traversal baru akan menganggap objek sudah ditandai dan tidak menelusuri referensinya, sehingga objek yang seharusnya mati tetap dianggap hidup. Perbaikannya adalah selalu mereset marked ke False pada seluruh objek di awal mark_sweep, sebelum traversal dimulai.
Kesalahan kedua pada reference counting adalah lupa memanggil add_ref saat menyimpan referensi. Bila sebuah referensi disimpan tanpa menambah refcount, refcount akan menjadi lebih kecil dari jumlah referensi sebenarnya, sehingga objek dapat dibebaskan terlalu awal. Perbaikannya adalah membungkus penambahan referensi ke dalam metode link yang selalu memanggil add_ref, sehingga pelanggaran aturan ini menjadi lebih sulit terjadi.
Ringkasan#
- Mark-sweep bekerja dalam tiga langkah: menetapkan root set, menelusuri referensi untuk menandai objek hidup, lalu menyapu objek yang tidak ditandai.
- Reference counting membebaskan objek segera saat refcount mencapai nol, sehingga deallokasi bersifat tepat waktu dan tanpa jeda.
- Reference counting gagal pada referensi siklis, sebab pasangan objek yang saling merujuk tidak pernah mencapai refcount nol walaupun tidak ada lagi referensi dari luar.
- Bahasa produksi sering memadukan reference counting dengan pengumpul siklus cadangan sehingga keunggulan keduanya dapat digunakan bersama.
Referensi#
- Tracing garbage collection — Wikipedia — Penjelasan algoritma mark-sweep dan varian tracing lainnya.
- Reference counting — Wikipedia — Mekanisme reference counting, kelebihan, dan kegagalan pada siklus.
- Garbage Collection Handbook — Jones, Hosking, Moss — Buku rujukan utama tentang berbagai algoritma pengumpulan sampah, termasuk mark-sweep dan pengumpul siklus.