Bagaimana cara pengumpul sampah menghindari tumpukan meluap?

23

Jadi saya berpikir tentang cara kerja pengumpul sampah dan saya memikirkan masalah yang menarik. Agaknya pengumpul sampah harus melintasi semua struktur dengan cara yang sama. Mereka tidak dapat mengetahui cuaca mereka melintasi daftar tertaut atau pohon seimbang atau apa pun. Mereka juga tidak dapat menggunakan terlalu banyak memori dalam pencarian mereka. Satu cara yang mungkin, dan satu-satunya cara saya bisa berpikir untuk melintasi SEMUA struktur, mungkin hanya dengan melintasi semuanya secara rekursif seperti yang Anda lakukan pada pohon biner. Namun ini akan memberikan stack overflow pada daftar tertaut atau bahkan hanya pohon biner yang kurang seimbang. Tetapi semua sampah yang dikumpulkan bahasa yang pernah saya gunakan tampaknya tidak punya masalah dalam menangani kasus-kasus seperti itu.

Dalam buku naga itu menggunakan semacam antrian "Tidak dipindai". Pada dasarnya daripada melintasi struktur secara rekursif itu hanya menambahkan hal-hal yang perlu ditandai juga antrian dan kemudian untuk setiap hal yang tidak ditandai pada akhirnya dihapus. Tapi bukankah antrian ini menjadi sangat besar?

Jadi, bagaimana pengumpul sampah melintasi struktur sewenang-wenang? Bagaimana teknik traversal ini menghindari overflow?

Jake
sumber
1
GC melintasi semua struktur dengan cara yang kurang lebih sama, tetapi hanya dalam arti yang sangat abstrak (lihat jawaban). Cara mereka melacak hal secara konkret jauh lebih canggih daripada yang ditunjukkan oleh presentasi dasar yang dapat Anda temukan di buku teks. Dan mereka tidak menggunakan rekursi. Lebih jauh lagi, dengan memori virtual, implementasi yang buruk menunjukkan perlambatan GC, jarang karena memori meluap.
babou
Anda khawatir tentang ruang yang dibutuhkan untuk pelacakan. Tetapi bagaimana dengan ruang atau struktur yang diperlukan untuk membedakan memori yang telah ditelusuri dan diketahui sedang digunakan, dari memori yang berpotensi dapat direklamasi. Ini mungkin memiliki biaya memori yang signifikan, mungkin sebanding dengan ukuran tumpukan.
babou
Saya pikir itu akan dilakukan dengan bitvector pada ukuran objek yang lebih besar dari 16 byte atau lebih sehingga kepala lebih dari 1000 kali lebih sedikit.
Jake
Ada banyak cara untuk melakukannya (lihat jawaban), dan mereka juga dapat digunakan untuk melacak, yang kemudian akan menjawab pertanyaan Anda (bitvektor atau bitmap dapat digunakan untuk melacak, daripada tumpukan atau antrian yang Anda sarankan). Anda tidak dapat mengasumsikan semua benda besar, kecuali jika Anda ingin menyia-nyiakan ruang untuk benda kecil, yang jumlahnya bisa banyak, dan Anda tidak perlu khawatir untuk ruang. Jika Anda berada dalam memori virtual, ruang sering kali jauh lebih sedikit masalah dan masalahnya sangat berbeda.
babou

Jawaban:

13

Perhatikan bahwa saya bukan ahli pengumpulan sampah. Jawaban ini hanya memberikan contoh teknik. Saya tidak mengklaim bahwa ini adalah gambaran representatif dari teknik pengumpulan sampah.

Antrian yang tidak dipindai adalah pilihan umum. Antrian bisa menjadi besar - berpotensi sebesar struktur data terdalam. Antrian biasanya disimpan secara eksplisit, bukan di tumpukan thread pengumpulan sampah.

Setelah semua kecuali satu anak dari sebuah node telah dipindai, node tersebut dapat dihapus dari antrian yang tidak dipindai. Ini pada dasarnya adalah optimasi panggilan ekor. Pengumpul sampah dapat menyertakan heuristik untuk mencoba memindai anak yang paling dalam dari simpul yang terakhir; misalnya GC untuk Lisp harus memindai cardari conssebelum cdr.

Salah satu cara untuk menghindari agar tidak ada antrian yang tidak terpindai adalah dengan memodifikasi pointer, membuat anak sementara menunjuk ke orang tua. Ini adalah teknik traversal pohon memori konstan yang digunakan dalam konteks selain pengumpul sampah. Kelemahan dari teknik ini adalah bahwa sementara GC melintasi struktur data, struktur data tidak valid, sehingga GC harus menghentikan dunia. Ini bukan pemecah kesepakatan: banyak pemulung yang memasukkan fase yang menghentikan dunia, selain fase yang tidak tapi bisa kehilangan sampah sebagai hasilnya.

Gilles 'SANGAT berhenti menjadi jahat'
sumber
2
Teknik yang dijelaskan dalam paragraf terakhir sering disebut " pembalikan pointer ".
Logika Pengembaraan
@WanderingLogic Ya, pembalikan pointer adalah bagaimana saya menyebutnya dalam jawaban saya sendiri. Ini karena Deutsch, Schorr dan Waite (1967). Namun, tidak benar untuk menyatakan bahwa ia bekerja dalam memori konstan: itu memang memerlukan bit tambahan untuk setiap sel dengan pointer , meskipun ini dapat dikurangi dengan menggunakan tumpukan bit. Jawaban diterima yang Anda referensi tidak sepenuhnya benar atau tidak lengkap karena alasan yang sama. plog2pp
babou
Saya telah menggunakan pembalikan pointer di GC kustom tanpa memerlukan bit tambahan ini; Triknya adalah menggunakan representasi objek khusus dalam memori dalam memori. Yaitu, objek "header" berada di tengah, dengan bidang pointer sebelum header, dan bidang non-pointer setelah; Selain itu, semua pointer disejajarkan, dan header menyertakan bidang dengan bit paling signifikan yang selalu ditetapkan. Dengan demikian, selama backtrack pembalikan pointer, mencapai pointer berikutnya dan memperhatikan kita telah selesai dengan suatu objek dapat dilakukan dengan jelas tanpa bit tambahan. Tata letak ini juga mendukung warisan OOP.
Thomas Pornin
@ThomasPornin Saya pikir informasi bit harus ada di suatu tempat. Pertanyaannya adalah dimana? Bisakah kita membahas ini dalam obrolan? Saya harus pergi sekarang, tetapi saya ingin membahas hal ini. Atau adakah deskripsi yang dapat dijangkau di web?
babou
1
@Babou dan Thomas tolong
Gilles 'SO- berhenti bersikap jahat'
11

Singkatnya : Pengumpul sampah tidak menggunakan rekursi. Mereka hanya mengontrol pelacakan dengan melacak dua set dasarnya (yang dapat menggabungkan). Urutan penelusuran dan pemrosesan sel tidak relevan, yang memberikan kebebasan implementasi yang cukup besar untuk mewakili set. Karenanya ada banyak solusi yang sebenarnya sangat murah dalam penggunaan memori. Ini penting karena GC disebut tepat ketika tumpukan kehabisan memori. Hal-hal agak berbeda dengan memori virtual besar, karena halaman baru dapat dengan mudah dialokasikan, dan musuh bukanlah kekurangan ruang, tetapi kurangnya data lokalitas .

Saya berasumsi Anda sedang mempertimbangkan melacak pemulung, bukan penghitungan referensi yang tampaknya tidak berlaku untuk pertanyaan Anda.

Pertanyaannya adalah fokus pada biaya memori pelacakan untuk melacak satu set: set (untuk yang tidak dilacak) dari sel memori yang dapat diakses yang masih mengandung pointer yang belum dilacak. Ini hanya setengah dari masalah memori untuk pengumpulan sampah. GC juga harus melacak set lain: set (untuk dikunjungi) dari semua sel yang telah ditemukan dapat diakses, sehingga dapat mengklaim kembali semua sel lain di akhir proses. Membahas satu dan bukan yang lain masuk akal terbatas, karena mereka mungkin memiliki biaya yang sama, menggunakan solusi yang sama, dan bahkan digabungkan.VUV

Hal pertama yang perlu diperhatikan adalah bahwa semua pelacakan GC mengikuti model abstrak yang sama, berdasarkan eksplorasi sistematis dari sel-sel yang diarahkan dalam memori yang dapat diakses dari program, di mana sel-sel memori adalah simpul dan pointer adalah tepi yang diarahkan. Ini digunakan untuk set berikut:

  • himpunan (dikunjungi) dari sel-sel yang sudah ditemukan dapat diakses oleh mutator , yaitu program atau algoritma untuk mana GC dilakukan. Himpunan dipartisi menjadi dua himpunan bagian terpisah: ;V V = U TVVV=UT

  • set (tidak terlacak) dari sel yang dikunjungi dengan pointer yang belum diikuti;U

  • set (dilacak) dari sel-sel yang dikunjungi yang memiliki semua pointer mereka dilacak.T

  • kami juga mencatat himpunan semua sel dalam tumpukan, apakah digunakan atau tidak.H

Hanya dan , atau dan , yang perlu diwakili, agar algoritma bekerja.U U TVUUT

Algoritme dimulai dari beberapa root pointer yang dikenal dengan sistem run-time (biasanya pointer dalam memori yang dialokasikan stack), dan menempatkan semua sel yang mereka tunjuk dalam set tidak dilacak (maka dalam juga).VUV

Kemudian kolektor mengambil sel dalam satu per satu, dan memeriksa setiap sel semua petunjuknya. Untuk setiap pointer, jika sel runcing berada di , maka tidak ada yang dilakukan, selain itu sel runcing ditambahkan ke , karena penunjuknya belum diperiksa. Ketika semua pointer yang telah diproses, sel ditransfer dari set untraced ke set ditelusuri .c V U c U TUcVUcUT

Pelacakan berakhir ketika kosong. Ini pasti terjadi, karena tidak ada sel yang melewati lebih dari sekali. Pada titik itu, , dan semua sel dalam diketahui dapat diakses oleh program, sehingga tidak dapat direklamasi. Komplemen dari di heap menentukan sel-sel apa yang tidak dapat dijangkau oleh program mutator dan dapat direklamasi oleh kolektor untuk alokasi masa depan ke mutator.U V = T V H - V VUUV=TVHVV

Tentu saja, detailnya bervariasi tergantung pada bagaimana set diimplementasikan, dan apakah itu dan , atau dan , yang diwakili secara efektif.U U TVUUT

Saya juga melewatkan detail tentang apa itu sel, apakah mereka datang dalam satu ukuran atau banyak, bagaimana kita menemukan pointer di dalamnya, bagaimana mereka dapat dipadatkan, dan sejumlah masalah teknis lainnya yang dapat Anda temukan dalam buku dan survei tentang pengumpulan sampah .

Anda mungkin memperhatikan bahwa ini adalah algoritma yang sangat sederhana. Tidak ada rekursi, tetapi hanya satu lingkaran pada elemen-elemen himpunan yang dapat tumbuh saat sedang diprosesU , sampai akhirnya kosong. Tidak ada asumsi apriori tentang memori tambahan. Apa pun yang memungkinkan mengidentifikasi set, dan melakukan cukup murah operasi yang diperlukan akan dilakukan. Perhatikan bahwa urutan pemrosesan sel tidak relevan (tidak perlu tumpukan pushdown), yang memberikan banyak kebebasan untuk memilih cara untuk mewakili set secara efisien.

Dimana implementasi yang dikenal berbeda dalam cara set ini sebenarnya diwakili. Banyak teknik yang sebenarnya telah digunakan:

  • bit map: Beberapa ruang memori disimpan untuk peta yang memiliki satu bit untuk setiap sel memori, yang dapat ditemukan menggunakan alamat sel. Bit aktif ketika sel yang sesuai berada di set yang ditentukan oleh peta. Jika hanya peta bit yang digunakan, Anda hanya perlu 2 bit per sel.

  • sebagai alternatif, Anda mungkin memiliki ruang untuk bit tag khusus (atau 2) di setiap sel untuk menandainya.

  • log2pp

  • Anda dapat menguji predikat pada konten sel, dan petunjuknya.

  • Anda dapat memindahkan sel di bagian memori bebas yang ditujukan untuk semua sel yang hanya dimiliki oleh perangkat yang diwakili.

  • VTTU

  • Anda sebenarnya dapat menggabungkan teknik-teknik ini, bahkan untuk satu set tunggal.

Seperti yang dikatakan, semua hal di atas telah digunakan oleh beberapa pengumpul sampah yang diimplementasikan, aneh karena beberapa mungkin terlihat. Itu semua tergantung pada berbagai kendala implementasi. Dan mereka bisa agak murah dalam penggunaan memori, mungkin dibantu dengan memproses kebijakan pesanan yang dapat dipilih secara bebas untuk tujuan itu, karena mereka tidak masalah untuk hasil akhirnya.

Apa yang mungkin tampak paling aneh, mentransfer sel di area baru, sebenarnya sangat umum: ini disebut kumpulan salinan. Sebagian besar digunakan dengan memori virtual.

Jelas tidak ada rekursi, dan tumpukan algoritma mutator tidak harus digunakan.

Poin penting lainnya adalah banyak GC modern diterapkan untuk memori virtual besar . Maka mendapatkan ruang untuk mengimplementasikan dan daftar atau tumpukan tambahan tidak menjadi masalah karena halaman baru dapat dengan mudah dialokasikan. Namun, dalam ingatan virtual yang besar, musuh bukanlah kekurangan ruang tetapi kurangnya lokalitas . Kemudian, struktur yang mewakili set, dan penggunaannya, harus diarahkan untuk melestarikan lokalitas struktur data dan pelaksanaan GC. Masalahnya bukan ruang tetapi waktu. Implementasi yang tidak memadai lebih cenderung menunjukkan perlambatan yang tidak dapat diterima daripada limpahan memori.

Saya tidak memberikan referensi ke banyak algoritma spesifik, yang dihasilkan dari berbagai kombinasi teknik ini, karena ini tampaknya cukup lama.

babou
sumber
4

Cara standar untuk menghindari stack overflow adalah dengan menggunakan stack eksplisit (disimpan sebagai struktur data di heap). Itu juga berfungsi untuk tujuan ini. Pengumpul sampah sering kali memiliki daftar benda kerja yang perlu diperiksa / dilalui, yang melayani peran ini. Misalnya, antrian "Tidak dipindai" Anda adalah contoh pola semacam ini. Antrian berpotensi menjadi besar, tetapi tidak menyebabkan stack overflow, karena tidak disimpan di segmen stack. Bagaimanapun, itu tidak akan pernah menjadi lebih besar dari jumlah objek hidup di heap.

DW
sumber
Ketika GC dipanggil, heap biasanya penuh. Poin lain adalah bahwa tumpukan dan tumpukan tumbuh dari kedua ujung ruang memori yang sama ..
babou
4

Dalam deskripsi "klasik" tentang pengumpulan sampah (mis., Mark Wilson, " Teknik Pengumpulan Sampah Uniprocessor ", Lokakarya Int'l tentang Manajemen Memori , 1992, ( tautan alternatif ), atau deskripsi dalam Implementasi Kompiler Modern Andrew Appel (Cambridge University Press, 1998)), kolektor diklasifikasikan sebagai "Tandai dan Sapu" atau "Menyalin".

Tandai dan kolektor Sapu menghindari membutuhkan ruang ekstra dengan menggunakan pointer-reversal, seperti yang dijelaskan dalam jawaban @ Gilles. Appel mengatakan bahwa Knuth mengaitkan algoritma pointer-reversal ke Peter Deutsch, dan ke Herbert Schorr dan WM Waite.

Menyalin pengumpul sampah menggunakan apa yang sering disebut algoritma Cheyney untuk melakukan antrian traversal tanpa memerlukan ruang ekstra. Algoritma ini diperkenalkan di CJ Cheyney, "A Nonrecursive List Compacting Algorithm", Comm. ACM , 13 (11): 677-678, 1970.

Di pengumpul sampah menyalin Anda memiliki sepotong memori yang Anda coba kumpulkan, disebut dari-ruang , dan sepotong memori yang Anda gunakan untuk salinan yang disebut ke-ruang . scanTo -space diatur sebagai antrian dengan penunjuk yang menunjuk ke catatan terlama yang tidak disalin, dan freepenunjuk yang menunjuk ke posisi bebas berikutnya di ruang. Gambar ini dari makalah Wilson adalah:

Contoh algoritma Cheyney

Saat Anda memindai setiap item di ruang, Anda menyalin anak-anak dari ruang ke freepointer di ruang, dan kemudian mengubah pointer ke anak dari dari ruang ke salinan baru anak di ruang. Ada trik tambahan yang perlu Anda gunakan ketika struktur data Anda bukan pohon (ketika seorang anak dapat memiliki lebih dari satu orangtua). Dalam hal itu, ketika Anda menyalin anak dari dari ruang ke ruang, Anda harus menimpa versi lama anak dengan pointer penerusan ke salinan baru anak. Kemudian jika Anda pernah memindai pointer lain ke versi lama anak Anda menyadari bahwa itu sudah disalin, dan jangan salin lagi.

Logika Pengembaraan
sumber
Sebenarnya, seperti yang dijelaskan dalam jawaban saya, baik Mark + Sweep dan Salin koleksi adalah algoritma grafik abstrak yang sama. Koleksi MS dan Salin berbeda hanya dalam cara set yang digunakan oleh algoritma abstrak diimplementasikan, dan kedua keluarga dimasukkan, dengan banyak varian, dalam beberapa kombinasi dari teknik implementasi set yang saya jelaskan dalam jawaban saya. Beberapa varian GC sebenarnya mencampur MS dan Salin dalam GC yang sama. Memisahkan MS dan Copy dipandang oleh beberapa orang sebagai cara yang nyaman untuk menyusun buku, tetapi itu adalah visi yang sewenang-wenang, dan saya percaya sudah ketinggalan zaman.
babou
@ Babou: Jika seseorang menggunakan algoritma penyalinan di mana segala sesuatu yang dikunjungi akan disalin (lambat, tetapi mungkin berguna pada platform kecil di mana set kerja tidak pernah sebesar itu), beberapa algoritma mungkin agak disederhanakan karena seseorang dapat menggunakan memori yang sebelumnya ditempati oleh objek yang dipindahkan sebagai alas mouse. Seseorang juga dapat memperoleh kemampuan terbatas untuk membuat utas lain melakukan akses baca-saja ke objek selama pengumpulan asalkan seseorang memeriksa validitas objek sebelum dan sesudah setiap pembacaan, dan mengikuti pointer penerusan jika suatu objek telah dipindahkan.
supercat
@supercat Saya tidak yakin apa yang ingin Anda katakan, apa maksud Anda. Beberapa pernyataan Anda tampaknya benar. Tapi saya tidak mengerti bagaimana Anda bisa menggunakan dari luar angkasa sebelum siklus GC berakhir (ini mengandung forwarding pointer). Dan itu akan menjadi alas untuk apa? Sederhanakan algoritmanya bagaimana? Mengenai beberapa utas mutator yang dijalankan saat GC sedang berlangsung, ini sebagian besar merupakan masalah ortogonal, meskipun hal itu dapat berdampak besar pada implementasi. Saya tidak akan berusaha mengatasinya dalam komentar. Seharusnya lebih sedikit menimbulkan masalah dalam akses baca-saja, tetapi iblis ada dalam perinciannya.
babou