Ketika seorang pemulung mengumpulkan benda-benda di tumpukan, apakah itu mengubah referensi di tumpukan?

18

Ini sepertinya pertanyaan sederhana, tetapi setelah banyak membaca tentang masalah ini, saya masih belum menemukan jawaban yang pasti (mungkin karena itu sangat sederhana).

Pertanyaan saya adalah ini: ketika seorang pemulung mengumpulkan benda-benda di tumpukan, bagaimana referensi ke benda-benda di tumpukan diperbarui? Saya dapat memikirkan dua solusi yang mungkin:

  1. Pergi melalui tumpukan (dan referensi di tumpukan) dan perbarui referensi untuk menunjuk ke lokasi baru objek. Dalam analogi dengan pindah, ini seperti mengirim surat kepada siapa pun yang memiliki alamat Anda dan meminta mereka untuk memperbarui buku alamat mereka dengan alamat baru Anda.
  2. Berikan semacam tabel pencarian. Ini seperti meninggalkan alamat penerusan dengan kantor pos setempat.

Apakah pemulung secara dominan menggunakan salah satu dari dua metode ini? Beberapa metode lain? Kedua?

garbage-collection todorojo
sumber
Lihat stackoverflow.com/questions/3799203/… dan en.wikipedia.org/wiki/…
Gort the Robot
@StevenBurnap memperbaiki saya jika saya salah, tapi saya yakin utas yang Anda tautkan tidak memiliki jawaban pasti. Mereka tampaknya berspekulasi tentang pertanyaan yang tepat ini juga. Saya mungkin salah baca. Jika mereka memang memberikan jawaban untuk pertanyaan itu, jika Anda tidak keberatan, saya pikir akan sangat membantu untuk meringkas jawaban di sini untuk pengguna SE di masa mendatang (dan saya sendiri!)
todorojo
Istilah untuk hal yang Anda bicarakan adalah "pengumpul sampah yang bergerak". Terus terang saya tidak tahu seberapa umum mereka digunakan.
Gort the Robot

Jawaban:

9

Saya tidak memiliki keahlian khusus dalam hal ini, tetapi pemahaman saya adalah bahwa metode pertama umumnya digunakan.

Pengumpul sampah harus menganalisis tumpukan apa pun untuk menemukan hal-hal apa di tumpukan yang dirujuk dari tumpukan. Begitu ia memutuskan untuk memindahkan sesuatu, ia harus memperbaiki referensi untuk itu, dan tidak ada alasan untuk membedakan antara tumpukan dan tumpukan pada titik itu.

Pendekatan tabel pencarian pada prinsipnya bisa berhasil. Namun itu akan membuat semua akses pointer perlu mengambil 2 langkah. Itu akan menjadi dampak kinerja yang sangat besar pada waktu lari normal. Khususnya untuk kasus penggunaan banyak benda kecil. (Yang merupakan kasus di mana program-program GC canggih biasanya mengalahkan penghitungan referensi.)

btilly
sumber
3
Saya akan menambahkan bahwa saya pikir GC mungkin mencoba untuk tidak memindahkan barang-barang di tumpukan kecuali mereka harus. Dalam dunia multi-prosesor saat ini, itu harus menjadi mimpi buruk sinkronisasi ketika mereka perlu memperbarui semua referensi ke sesuatu di tumpukan sementara program yang menggunakan referensi tersebut sedang berjalan. Tabel pencarian akan menyederhanakan ini, tapi saya pikir itu pengecualian daripada norma, jadi sebagian besar GC mungkin harus mengunci beberapa referensi, memindahkan memori, lalu memperbarui referensi. +1 pertanyaan menarik, +1 jawaban bagus.
GlenPeterson
3
@GlenPeterson Banyak GCs memang tidak memindahkan banyak hal, dan tidak menghadapi masalah ini. Tetapi GC pemadatan menurut definisi memindahkan objek langsung ke memori defragment.
btilly
@ GlenPeterson, ini adalah pengamatan yang baik bahwa memindahkan barang-barang di tumpukan adalah rasa sakit sinkronisasi yang besar, ini sering diabaikan meskipun pemadatan GC memiliki efek riak besar pada proses yang berjalan karena ini. Itu satu-satunya alasan terbesar orang disuruh melakukan segala yang mereka bisa untuk menjaga objek sesingkat mungkin, untuk menghindari pembaruan tumpukan besar yang menyebabkan pemadatan menahan mutasi yang panjang. Ketidaktahuan tentang bagaimana hal ini berperilaku dapat menyebabkan apa yang disebut sebagai Mode Freakout GC.
Jimmy Hoffa
2
Macintosh dan Palm OS asli keduanya menggunakan pendekatan tabel pencarian untuk manajemen memorinya. Pointer ke dalam tabel disebut sebagai pegangan. GC yang pindah harus mengetahui keberadaan dari setiap referensi yang benar-benar positif untuk objek apa pun yang bergerak; menggunakan satu tabel untuk keperluan seperti itu sangat menyederhanakan banyak hal.
supercat