Mengapa Pengumpulan Sampah hanya menyapu tumpukan?

Pada dasarnya, saya telah belajar sejauh ini bahwa pengumpulan sampah menghapus selamanya semua struktur data yang saat ini tidak diarahkan. Tetapi ini hanya memeriksa tumpukan untuk kondisi seperti itu.

Mengapa tidak memeriksa bagian data (global, konstanta, dll, dll) atau stack juga? Ada apa dengan tumpukan itu bahwa satu-satunya hal yang kita inginkan adalah pengumpulan sampah?

Pengumpul sampah tidak memindai tumpukan - untuk melihat benda apa yang ada di tumpukan saat ini sedang digunakan (diarahkan ke) oleh benda-benda di tumpukan.

Tidak masuk akal bagi pemulung untuk mempertimbangkan pengumpulan memori tumpukan karena tumpukan tidak dikelola seperti itu: Semua yang ada di tumpukan dianggap "sedang digunakan." Dan memori yang digunakan oleh stack secara otomatis direklamasi ketika Anda kembali dari panggilan metode. Manajemen memori ruang stack sangat sederhana, murah dan mudah sehingga Anda tidak ingin pengumpulan sampah dilibatkan.

(Ada sistem, seperti smalltalk, di mana frame stack adalah objek kelas satu yang disimpan di heap dan sampah dikumpulkan seperti semua objek lain. Tapi itu bukan pendekatan yang populer saat ini. Java JVM dan Microsoft CLR menggunakan stack perangkat keras dan memori yang berdekatan .)

Balikkan pertanyaan Anda. Pertanyaan yang benar-benar memotivasi adalah dalam keadaan apa kita dapat menghindari biaya pengumpulan sampah?

Nah, pertama, apa yang biaya pengumpulan sampah? Ada dua biaya utama. Pertama, Anda harus menentukan apa yang hidup ; yang membutuhkan banyak pekerjaan. Kedua, Anda harus memadatkan lubang yang terbentuk ketika Anda membebaskan sesuatu yang dialokasikan di antara dua hal yang masih hidup. Lubang-lubang itu boros. Tapi memadatkannya juga mahal.

Bagaimana kita bisa menghindari biaya ini?

Jelas jika Anda dapat menemukan pola penggunaan penyimpanan di mana Anda tidak pernah mengalokasikan sesuatu yang berumur panjang, kemudian mengalokasikan sesuatu yang berumur pendek, kemudian mengalokasikan sesuatu yang berumur panjang, Anda dapat menghilangkan biaya lubang. Jika Anda dapat menjamin bahwa untuk beberapa bagian penyimpanan Anda, setiap alokasi berikutnya lebih pendek dari yang sebelumnya dalam penyimpanan itu maka tidak akan pernah ada lubang dalam penyimpanan itu.

Tetapi jika kita telah memecahkan masalah lubang maka kita juga memecahkan masalah pengumpulan sampah . Apakah Anda memiliki sesuatu di penyimpanan yang masih hidup? Iya nih. Apakah semuanya dialokasikan sebelum berumur panjang? Ya - asumsi itu adalah bagaimana kita menghilangkan kemungkinan lubang. Karena itu yang perlu Anda lakukan adalah mengatakan "apakah alokasi terbaru masih hidup?" dan Anda tahu bahwa semuanya hidup di penyimpanan itu.

Apakah kita memiliki seperangkat alokasi penyimpanan di mana kita tahu bahwa setiap alokasi berikutnya lebih pendek dari alokasi sebelumnya? Iya nih! Kerangka aktivasi metode selalu dihancurkan dengan urutan yang berbeda karena mereka dibuat lebih singkat daripada aktivasi yang menciptakannya.

Oleh karena itu kami dapat menyimpan bingkai aktivasi di tumpukan dan mengetahui bahwa mereka tidak perlu dikumpulkan. Jika ada bingkai di tumpukan, seluruh rangkaian bingkai di bawahnya berumur panjang, sehingga tidak perlu dikumpulkan. Dan mereka akan dihancurkan dengan urutan yang berlawanan bahwa mereka diciptakan. Biaya pengumpulan sampah dengan demikian dihilangkan untuk bingkai aktivasi.

Itulah mengapa kami memiliki kumpulan sementara pada stack di tempat pertama: karena ini adalah cara mudah mengimplementasikan aktivasi metode tanpa menimbulkan penalti manajemen memori.

(Tentu saja biaya sampah mengumpulkan memori yang dirujuk oleh referensi pada bingkai aktivasi masih ada.)

Sekarang pertimbangkan sistem aliran kontrol di mana bingkai aktivasi tidak dihancurkan dalam urutan yang dapat diprediksi. Apa yang terjadi jika aktivasi yang berumur pendek dapat menimbulkan aktivasi yang berumur panjang? Seperti yang Anda bayangkan, di dunia ini Anda tidak lagi dapat menggunakan tumpukan untuk mengoptimalkan kebutuhan mengumpulkan aktivasi. Himpunan aktivasi dapat berisi lubang lagi.

C # 2.0 memiliki fitur ini dalam bentuk yield return. Metode yang menghasilkan pengembalian akan diaktifkan kembali di lain waktu - waktu berikutnya yang disebut MoveNext - dan ketika itu terjadi tidak dapat diprediksi. Oleh karena itu informasi yang biasanya berada di tumpukan untuk bingkai aktivasi blok iterator malah disimpan di heap, di mana itu adalah sampah yang dikumpulkan ketika enumerator dikumpulkan.

Demikian pula, fitur "async / await" yang hadir dalam versi C # dan VB berikutnya akan memungkinkan Anda untuk membuat metode yang aktivasi "menghasilkan" dan "melanjutkan" pada titik yang ditentukan dengan baik selama aksi metode. Karena frame aktivasi tidak lagi dibuat dan dihancurkan dengan cara yang dapat diprediksi, semua informasi yang digunakan untuk disimpan dalam stack harus disimpan di heap.

Ini hanya kebetulan dalam sejarah yang kami putuskan selama beberapa dekade bahwa bahasa dengan bingkai aktivasi yang dibuat dan dihancurkan dengan cara yang benar-benar teratur sangat modis. Karena bahasa modern semakin kekurangan properti ini, berharap untuk melihat semakin banyak bahasa yang mengubah kelanjutan ke tumpukan sampah, bukan tumpukan.

Jawaban yang paling jelas, dan mungkin tidak sepenuhnya, adalah bahwa heap adalah lokasi data instan. Dengan data instan, kami maksudkan data yang mewakili instance kelas, alias objek, yang dibuat pada saat run time. Data ini secara inheren dinamis dan jumlah objek ini, dan dengan demikian jumlah memori yang mereka ambil, hanya diketahui saat runtime. Harus ada luka pemulihan memori ini atau program yang berjalan lama akan menghabiskan semua memori dari waktu ke waktu.

Memori yang dikonsumsi oleh definisi kelas, konstanta, dan struktur data statis lainnya secara inheren tidak mungkin meningkat tanpa dicentang. Karena hanya ada satu definisi kelas dalam memori per jumlah run time yang tidak diketahui dari kelas itu, masuk akal bahwa jenis struktur ini bukan ancaman bagi penggunaan memori.

Perlu diingat alasan mengapa kita memiliki pengumpulan sampah: karena kadang-kadang sulit untuk mengetahui kapan harus mengalokasikan memori. Anda benar-benar hanya memiliki masalah dengan tumpukan ini. Data yang dialokasikan pada stack pada akhirnya akan di-deallocated, jadi sebenarnya tidak perlu melakukan pengumpulan sampah di sana. Hal-hal di bagian data umumnya dianggap dialokasikan untuk seumur hidup program.

1. Ukurannya dapat diprediksi (konstan kecuali untuk stack, dan stack biasanya terbatas pada beberapa MB) dan biasanya sangat kecil (setidaknya dibandingkan dengan ratusan MB aplikasi besar dapat mengalokasikan).

2. Objek yang dialokasikan secara dinamis biasanya memiliki kerangka waktu kecil yang dapat dijangkau. Setelah itu, tidak mungkin mereka bisa direferensikan lagi. Bandingkan dengan entri di bagian data, variabel global, dan semacamnya: Seringkali, ada sepotong kode yang mereferensikannya secara langsung (pikirkan const char *foo() { return "foo"; }). Biasanya, kode tidak berubah, jadi referensi tetap ada dan referensi lain akan dibuat setiap kali fungsi dipanggil (yang bisa kapan saja sejauh yang diketahui komputer - kecuali jika Anda memecahkan masalah penghentian, yaitu ). Dengan demikian, Anda tidak dapat membebaskan sebagian besar memori itu, karena akan selalu dapat dijangkau.

3. Dalam banyak bahasa yang dikumpulkan sampah, semua yang termasuk dalam program yang dijalankan adalah heap-dialokasikan. Dalam Python, tidak ada bagian data dan tidak ada nilai yang dialokasikan stack (ada referensi bahwa variabel lokal, dan ada panggilan stack, tetapi tidak ada nilai dalam arti yang sama dengan intdi C). Setiap objek ada di heap.

Seperti yang dikatakan oleh sejumlah responden lainnya, tumpukan adalah bagian dari set root, sehingga dipindai untuk referensi tetapi tidak "dikumpulkan", per se.

Saya hanya ingin menanggapi beberapa komentar yang menyiratkan bahwa sampah di tumpukan tidak masalah; ya, karena dapat menyebabkan lebih banyak sampah di tumpukan dianggap dapat dijangkau. VM yang teliti dan penulis kompiler tidak ada atau mengecualikan bagian tumpukan yang mati dari pemindaian. IIRC, beberapa VM memiliki tabel yang memetakan rentang PC untuk menumpuk bit-slot-liveness dan yang lain hanya membatalkan slot. Saya tidak tahu teknik apa yang saat ini disukai.

Satu istilah yang digunakan untuk menggambarkan pertimbangan khusus ini adalah ruang yang aman .

Izinkan saya menunjukkan beberapa kesalahpahaman mendasar yang Anda dan banyak orang lain salahkan:

"Mengapa Koleksi Sampah hanya menyapu tumpukan?" Itu sebaliknya. Hanya pengumpul sampah yang paling sederhana, paling konservatif dan paling lambat yang menyapu tumpukan itu. Itu sebabnya mereka sangat lambat.

Pengumpul sampah cepat hanya menyapu tumpukan (dan opsional beberapa root lainnya, seperti beberapa global untuk pointer FFI, dan register untuk pointer langsung), dan hanya menyalin pointer yang dapat dijangkau oleh objek stack. Sisanya dibuang (diabaikan), tidak memindai sama sekali.

Karena tumpukan sekitar 1000x lebih besar dari tumpukan, tumpukan-pemindaian GC biasanya jauh lebih cepat. ~ 15ms vs 250ms pada tumpukan ukuran normal. Karena itu menyalin (memindahkan) objek dari satu ruang ke ruang lain, itu sebagian besar disebut kolektor penyalinan semi-ruang, itu membutuhkan memori 2x dan karena itu sebagian besar tidak dapat digunakan pada perangkat yang sangat kecil seperti ponsel dengan memori yang tidak banyak. Ini kompak, jadi nanti sangat ramah cache, tidak seperti tanda sederhana & pemindai tumpukan tumpukan.

Karena ini adalah pointer yang bergerak, FFI, identitas dan referensi adalah rumit. Identitas biasanya diselesaikan dengan id acak, referensi melalui forwarding pointer. FFI rumit, karena benda asing tidak dapat menahan pointer ke ruang lama. Pointer FFI biasanya disimpan di arena tumpukan terpisah, misalnya dengan tanda lambat & menyapu, kolektor statis. Atau malloc sepele dengan penghitungan ulang. Perhatikan bahwa malloc memiliki overhead yang sangat besar, dan menghitung ulang lebih banyak lagi.

Mark & ​​sweep mudah untuk diterapkan tetapi tidak boleh digunakan dalam program nyata, dan terutama tidak diajarkan sebagai pengumpul standar. Yang paling terkenal dari kolektor penyalinan pemindaian tumpukan yang cepat ini disebut kolektor dua jari Cheney .

Apa yang dialokasikan pada stack? Variabel lokal dan alamat pengirim (dalam C). Ketika suatu fungsi kembali, variabel lokalnya dibuang. Itu tidak perlu, bahkan merugikan, untuk menyapu tumpukan.

Banyak bahasa dinamis, dan juga Java atau C # diimplementasikan dalam bahasa pemrograman sistem, sering dalam C. Anda bisa mengatakan Java diimplementasikan dengan fungsi C dan menggunakan variabel lokal C dan oleh karena itu pengumpul sampah Jawa tidak perlu menyapu tumpukan.

Ada pengecualian yang menarik: Pengumpul sampah Skema Ayam memang menyapu tumpukan (dengan cara), karena implementasinya menggunakan tumpukan sebagai tempat pengumpulan sampah generasi pertama: lihat Chicken Scheme Design Wikipedia .