ORC

ORC adalah pengelola memori bawaan Nim sejak versi 2.0, dibangun di atas ARC dan ditambah pengumpul siklus (cycle collector) untuk menangani siklus referensi yang tidak dapat dikumpulkan oleh penghitungan referensi saja. Topik ini membahas mengapa siklus membuat ARC gagal membebaskan memori, cara pengumpul siklus ORC bekerja, serta biaya yang menyertainya. Contohnya memakai satu program yang sama, yaitu dua simpul yang saling merujuk, yang dikompilasi dua kali dengan nilai --mm berbeda. Setelah perbedaannya terlihat, pemilihan antara ARC dan ORC dapat dilakukan dengan alasan yang jelas.

Siklus referensi yang tidak terkumpul oleh ARC#

Siklus referensi (reference cycle) terbentuk ketika dua objek ref saling menunjuk, sehingga masing-masing selalu punya pemegang selain variabel di luar siklus. Penghitung referensi kedua objek tidak pernah mencapai nol, walau tidak ada variabel biasa yang lagi menunjuknya. Program berikut membentuk siklus semacam itu di dalam sebuah proc, lalu memanggil GC_fullCollect() untuk memicu pemeriksaan memori secara eksplisit.

type
  Simpul = object
    id: int
    lawan: ref Simpul

proc `=destroy`(s: var Simpul) =
  echo "simpul ", s.id, " dimusnahkan"
  `=destroy`(s.lawan)

type
  RefSimpul = ref Simpul

proc buatSiklus() =
  var a = RefSimpul(id: 1)
  var b = RefSimpul(id: 2)
  a.lawan = b
  b.lawan = a

buatSiklus()
GC_fullCollect()
echo "program berakhir"

# kompilasi program siklus dengan ARC
nim c --mm:arc --hints:off siklus.nim
# jalankan program hasil kompilasi
./siklus

program berakhir

Keluarannya hanya satu baris, tanpa satu pun pesan pemusnahan. Kedua simpul masih saling menahan ketika buatSiklus() berakhir, sehingga penghitung masing-masing tidak pernah mencapai nol dan destruktor tidak pernah dijalankan. Pemanggilan GC_fullCollect() pun tidak menolong karena ARC memang tidak memiliki pengumpul siklus. Memori dua simpul itu menempel sampai program selesai, dan pola yang sama terulang setiap kali proc itu dipanggil.

Perhatikan pula mengapa siklus ini lolos dari penghitungan referensi yang selama ini terasa andal. Pada struktur tanpa siklus seperti pohon, rujukan mengalir satu arah dari pemilik ke yang dimiliki, sehingga ketika pemilik musnah, seluruh isinya ikut terbebaskan secara berantai. Siklus mematahkan pola itu karena tidak ada arah yang benar-benar memegang kepemilikan, sehingga sinyal pemusnahan tidak pernah tiba pada salah satu simpulnya. Atas alasan itulah penghitungan referensi saja tidak pernah cukup untuk struktur graf yang umum.

Cara pengumpul siklus ORC bekerja#

ORC memakai mekanisme ARC untuk semua data tanpa siklus, lalu menambah pengumpul siklus yang berbasis algoritma trial deletion. Kompilator menganalisis tipe secara statis dan hanya menghasilkan kode kolektor untuk tipe yang berpotensi membentuk siklus, sedangkan tipe yang dianotasi {.acyclic.} dikeluarkan dari perhitungan itu. Kandidat akar siklus didaftar dan dihapus dalam waktu tetap, sehingga pemeriksaan tidak memerlukan penelusuran seluruh heap seperti GC konvensional. Struktur tanpa siklus tetap dibebaskan segera oleh penghitungan referensi, persis seperti pada ARC.

Kompilasi ulang program yang sama dengan --mm:orc.

# kompilasi ulang program siklus dengan ORC
nim c --mm:orc --hints:off siklus.nim
# jalankan program hasil kompilasi
./siklus

simpul 2 dimusnahkan
simpul 1 dimusnahkan
program berakhir

Kali ini kedua pesan pemusnahan muncul. Pengumpul siklus menemukan grup simpul yang anggotanya hanya saling menahan, lalu memusnahkan seluruh grup dan menjalankan destruktor masing-masing. Urutannya deterministik pada program ini, yaitu simpul 2 sebelum simpul 1, dan berulang sama pada setiap eksekusi. Pada program pendek, pengumpul siklus belum tentu sempat berjalan sebelum program berakhir, sehingga GC_fullCollect() dipanggil di dalam contoh agar pemusnahan teramati secara pasti.

Ketika pengumpul siklus berjalan, pemeriksaannya tidak menelusuri seluruh heap, sesuai klaim dokumentasi bahwa perilaku runtime ORC tidak terpengaruh oleh ukuran heap dan stack yang terlibat. Kandidat akar siklus didaftar dan dihapus dalam waktu tetap, sehingga biaya pemeliharaannya kecil pada program yang datanya jarang bersiklus. Saat sebuah kandidat kehilangan pemegang terluarnya, algoritma trial deletion menguji secara sementara apakah grup tersebut benar-benar saling menahan, lalu memutuskan pemusnahan atau pengembalian keadaan semula. Inilah alasan struktur tanpa siklus pada contoh tidak merasakan adanya kolektor sama sekali.

Biaya dan batasan ORC#

Pengumpulan siklus membawa biaya yang dapat diukur. Dokumentasi memori Nim mencatat bahwa overhead pengumpul siklus dapat terasa pada praktiknya, dan anotasi {.acyclic.} menjadi kunci untuk mendekatkan performa ORC ke performa ARC pada tipe yang diketahui tidak mungkin bersiklus, misalnya pohon yang rujukannya satu arah. Pembaruan penghitung pada ORC juga tidak memakai instruksi atomik, sehingga model ini cepat pada program tanpa berbagi rujukan lintas thread. Untuk kebutuhan berbagi lintas thread, tersedia varian --mm:atomicArc dan --mm:yrc yang mengorbankan sebagian kecepatan demi keamanan.

Diagram berikut merangkum perbedaan perlakuan terhadap siklus yang sama.

Sebagai pengelola bawaan, ORC menjadi pilihan tanpa konfigurasi untuk program Nim modern. Pengecualian yang wajar adalah program embedded yang mengutamakan ukuran kode dan tidak membentuk siklus, yang dapat memilih --mm:arc, serta program warisan yang masih bergantung pada kolektor lama. Pilihan antar pengelola dibahas lengkap pada topik tentang sakelar --mm.

Keputusan untuk berpindah kolektor sebaiknya diambil dari pengukuran, bukan dari kesan. Profil konsumsi memori yang naik perlahan pada program berumur panjang menandakan siklus yang dibiarkan, dan dalam kasus itu pindah ke ORC adalah jawabannya. Sebaliknya, bila profil menunjukkan overhead kolektor pada tipe yang rujukannya sederhana, anotasi acyclic pada tipe tersebut biasanya cukup tanpa perlu meninggalkan ORC. Dua langkah kecil ini menyelesaikan sebagian besar dilema antara kecepatan ARC dan keamanan ORC.

Ringkasan#

• Siklus referensi membuat penghitung dua objek saling menahan sehingga ARC tidak pernah memusnahkannya, bahkan setelah GC_fullCollect().
• ORC melengkapi ARC dengan pengumpul siklus berbasis trial deletion yang hanya disertakan untuk tipe yang berpotensi bersiklus.
• Biaya pengumpul siklus dapat ditekan dengan anotasi {.acyclic.} pada tipe yang rujukannya satu arah.
• ORC menjadi pengelola bawaan Nim sejak versi 2.0 dan memusnahkan siklus secara deterministik pada contoh program ini.

Referensi#

• Nim’s Memory Management — Nim documentation — Penjelasan resmi ORC, ARC, dan varian lain beserta catatan overhead pengumpul siklusnya.
• ORC — Vorsprung durch Algorithmen — Nim Blog — Pengantar resmi algoritma pengumpul siklus ORC dan anotasi {.acyclic.}.
• Version 2.0 released — Nim Blog — Pengumuman resmi ORC sebagai model manajemen memori bawaan Nim 2.0.