Akankah menggunakan tabel hash dalam pengumpulan sampah memecahkan masalah dunia mark and sweep?

Dalam algoritma pengumpulan sampah mark-sweep-compact, Anda harus menghentikan dunia ketika memindahkan objek karena grafik referensi menjadi tidak konsisten dan Anda harus mengganti nilai semua referensi yang menunjuk ke objek.

Tetapi bagaimana jika Anda memiliki tabel hash dengan ID objek sebagai kunci dan penunjuk sebagai nilai, dan referensi akan menunjuk ke kata ID bukan alamat objek ... maka memperbaiki referensi hanya akan memerlukan perubahan satu nilai dan jeda hanya akan diperlukan jika objek dicoba untuk ditulis saat menyalin ...

Apakah ada kesalahan dalam pemikiran saya?

algorithms garbage-collection mrpyo
sumber

Jawaban:

Memperbarui referensi bukan satu-satunya hal yang membutuhkan jeda. Algoritma standar yang biasanya dikelompokkan dalam "mark-sweep" semuanya mengasumsikan bahwa seluruh grafik objek tetap tidak berubah saat sedang ditandai. Menangani modifikasi dengan benar (objek baru yang dibuat, referensi diubah) memerlukan algoritma alternatif yang agak rumit, seperti sebagai algoritma tri-warna. Istilah payung adalah "pengumpulan sampah bersamaan".

Tapi ya, memperbarui referensi setelah pemadatan juga perlu jeda. Dan ya, menggunakan tipuan (misalnya melalui objek ID persisten dan tabel hash ke pointer nyata) dapat sangat mengurangi jeda. Bahkan mungkin membuat bagian ini bebas dari penguncian jika diinginkan. Masih sulit untuk mendapatkan kebenaran seperti konkurensi memori bersama tingkat rendah, tetapi tidak ada alasan mendasar mengapa hal itu tidak berhasil.

Namun , itu akan memiliki kerugian parah. Selain mengambil ruang ekstra ( setidaknya dua kata tambahan untuk semua objek), itu membuat setiap dereferensi jauh lebih mahal. Bahkan sesuatu yang sederhana seperti mendapatkan atribut sekarang melibatkan pencarian tabel hash penuh. Saya memperkirakan kinerja hit jauh lebih buruk daripada untuk penelusuran tambahan.

sumber

Yah kami memiliki banyak memori hari ini sehingga kami dapat memiliki katakanlah 50 Mb tabel dan hash bisa menjadi modulo sederhana sehingga hanya satu instruksi ...

mrpyo

@ mrpyo mengambil ukuran tabel hash, operasi modulo, dereference dari hash table offset untuk mendapatkan pointer objek yang sebenarnya, dereference ke objek itu sendiri. Plus mungkin beberapa pengocokan register. Kami berakhir di 4+ instruksi. Juga, skema ini memiliki masalah mengenai memori lokal: Sekarang, tabel hash dan data itu sendiri harus masuk ke dalam cache.

amon

@ mrpyo Anda perlu satu entri (ID objek -> alamat saat ini) per objek, bukan? Dan terlepas dari seberapa murah fungsi hash, Anda akan memiliki tabrakan dan harus menyelesaikannya. Juga apa yang dikatakan amon.

@amon hanya tinggal menunggu waktu sebelum CPU memiliki cache 50MB atau lebih :)

Móż

@ Ӎσᶎ Pada saat kita dapat menempatkan 50 MiB transistor pada sebuah chip dan masih memiliki latensi yang cukup rendah untuk dapat berfungsi sebagai cache L1 atau L2 (cache L3 sudah berukuran hingga 15 MiB, tetapi biasanya AFAIK off-chip jauh dan jauh latensi yang lebih buruk daripada L1 dan L2), kami akan memiliki sejumlah besar memori utama (dan data untuk dimasukkan ke dalamnya). Tabel tidak bisa diperbaiki ukurannya, itu harus tumbuh dengan tumpukan.

Semua masalah dalam ilmu komputer dapat diselesaikan dengan tingkat tipuan yang lain ... kecuali untuk masalah terlalu banyak lapisan tipuan

Pendekatan Anda tidak segera menyelesaikan masalah pengumpulan sampah, tetapi hanya memindahkannya satu tingkat. Dan berapa biayanya! Sekarang, setiap akses memori melewati dereference pointer lain. Kami tidak dapat men-cache lokasi hasil, karena itu mungkin telah dipindahkan sementara itu, kami harus selalu melalui ID objek. Dalam kebanyakan sistem, tipuan ini tidak dapat diterima, dan menghentikan dunia diasumsikan memiliki total biaya runtime yang lebih rendah.

Saya mengatakan proposisi Anda hanya menggerakkan masalah, bukan menyelesaikannya. Masalahnya adalah sekitar penggunaan kembali ID objek. ID objek sekarang setara dengan pointer kami, dan hanya ada jumlah alamat yang terbatas. Dapat dibayangkan (khususnya pada sistem 32 bit) bahwa selama masa hidup program Anda, lebih dari objek INT_MAX akan dibuat, misalnya dalam satu lingkaran seperti

while (true) {
    Object garbage = new Object();
}

Jika kami hanya menambah ID objek untuk setiap objek, kami akan kehabisan ID di beberapa titik. Oleh karena itu kita harus mencari tahu ID mana yang masih digunakan dan yang gratis sehingga dapat direklamasi. Terdengar akrab? Kami sekarang kembali di titik awal.

amon
sumber

Seseorang mungkin dapat menggunakan ID yang hanya 'cukup besar' kata bignum 256 bit? Saya tidak mengatakan bahwa ide ini bagus secara keseluruhan, tetapi Anda hampir pasti dapat menggunakan kembali IDS.

Vality

@Vality realistis ya - sejauh yang bisa kita lihat yang akan mengatasi masalah penggunaan kembali ID. Tapi ini hanyalah argumen “640K yang seharusnya cukup untuk siapa pun”, dan tidak benar-benar menyelesaikan masalah. Aspek yang lebih dahsyat adalah bahwa ukuran semua objek (dan tabel hash) harus meningkat untuk mengakomodasi pseudo-pointer besar ini, dan bahwa selama akses hash kita perlu membandingkan bigint ini dengan ID lain yang mungkin akan memiliki banyak register. , dan ikuti beberapa instruksi untuk menyelesaikan (pada 64bit: 8 × memuat, 4 × bandingkan, 3 × dan yang merupakan peningkatan 5 × dari int asli).

amon

Ya, Anda akan kehabisan ID setelah beberapa waktu dan perlu mengubah semuanya yang memerlukan jeda. Tapi mungkin itu akan menjadi peristiwa langka ...

mrpyo

@amon Sangat setuju, semua poin yang sangat bagus di sana, jauh lebih baik memiliki sistem yang benar-benar berkelanjutan. Saya setuju. Ini akan menjadi lambat tak tertahankan, apa pun yang Anda lakukan, bagaimanapun, hanya menarik secara teori. Namun secara pribadi saya bukan penggemar berat sampah: P

Vality

@amon: ada lebih banyak kode di dunia daripada hanya ini yang akan salah setelah Anda membungkus ID 64 bit (584 tahun nanodetik, dan Anda mungkin dapat mengatur alokasi memori untuk mengambil 1ns terutama jika Anda tidak membuang global counter yang meludahkan ID!). Tapi tentu saja, jika Anda tidak perlu bergantung pada itu maka Anda tidak perlu.

Steve Jessop

Tidak ada kesalahan dalam pemikiran Anda, Anda baru saja menggambarkan sesuatu yang sangat dekat dengan cara kerja pengumpul sampah Java asli

Mesin virtual Java asli [6] dan beberapa mesin virtual Smalltalk menggunakan pointer tidak langsung, yang disebut pegangan di [6], untuk merujuk ke objek. Pegangan memungkinkan relokasi objek dengan mudah selama pengumpulan sampah karena, dengan pegangan, hanya ada satu penunjuk langsung ke setiap objek: yang ada di pegangannya. Semua referensi lain ke objek tidak langsung melalui han-dle. Dalam sistem memori berbasis pegangan seperti itu, sementara alamat objek berubah sepanjang masa objek dan karenanya tidak dapat digunakan untuk hashing, alamat pegangan tetap konstan.

Hashing ruang dan efisien waktu benda-benda yang dikumpulkan sampah

Dalam implementasi Sun dari Java Virtual Machine saat ini, referensi ke instance kelas adalah pointer ke handle yang merupakan sepasang pointer: satu ke tabel yang berisi metode objek dan pointer ke objek Class yang mewakili jenis objek, dan yang lainnya ke memori yang dialokasikan dari Java heap untuk data objek.

Spesifikasi Mesin Virtual Java (1997)

Jadi itu berhasil, telah dicoba, dan inefisiensi menyebabkan pengembangan tanda generasi dan sistem sapuan.

Pete Kirkham
sumber

Agaknya pegangan ini bukan kunci dalam hashtable (seperti dalam pertanyaan), meskipun? Tidak perlu, hanya struktur yang mengandung pointer. Kemudian semua pegangan memiliki ukuran yang sama sehingga mereka dapat dialokasikan keluar dari pengalokasi tumpukan. Yang pada dasarnya tidak memerlukan pemadatan internal karena tidak terfragmentasi. Anda mungkin meratapi ketidakmampuan blok besar yang digunakan oleh pengalokasi itu, untuk direlokasi sendiri. Yang bisa diselesaikan dengan tingkat tipuan yang lain ;-)

Steve Jessop

@SteveJessop ya, tidak ada hashtable dalam implementasi gc, meskipun nilai pegangan juga nilai yang dikembalikan olehObject.getHashCode()

Pete Kirkham