Setelah menelusuri beberapa jawaban Stack Overflow, jelas bahwa beberapa bahasa yang dikompilasi secara asli memiliki pengumpulan sampah . Tetapi tidak jelas bagi saya bagaimana ini akan bekerja.
Saya mengerti bagaimana pengumpulan sampah dapat bekerja dengan bahasa yang ditafsirkan. Pengumpul sampah hanya akan berjalan bersama penerjemah dan menghapus objek yang tidak terpakai dan tidak terjangkau dari memori program. Mereka berdua berjalan bersama.
Bagaimana cara kerjanya dengan bahasa yang dikompilasi? Pemahaman saya adalah bahwa begitu kompiler telah mengkompilasi kode sumber ke kode target - khususnya kode mesin asli - selesai. Pekerjaannya selesai. Jadi bagaimana bisa program yang dikompilasi menjadi sampah juga dikumpulkan?
Apakah kompiler bekerja dengan CPU dalam beberapa cara sementara program dijalankan untuk menghapus objek "sampah"? Atau apakah kompiler menyertakan beberapa pengumpul sampah minimal dalam program yang dapat dieksekusi.
Saya percaya pernyataan terakhir saya akan memiliki lebih banyak validitas daripada yang pertama karena kutipan dari jawaban ini di Stack Overflow :
Salah satu bahasa pemrograman tersebut adalah Eiffel. Sebagian besar kompiler Eiffel menghasilkan kode C untuk alasan portabilitas. Kode C ini digunakan untuk menghasilkan kode mesin oleh kompiler C standar. Implementasi Eiffel menyediakan GC (dan kadang-kadang bahkan GC akurat) untuk kode yang dikompilasi ini, dan tidak perlu untuk VM. Khususnya, kompiler VisualEiffel menghasilkan kode mesin x86 asli secara langsung dengan dukungan GC penuh .
Pernyataan terakhir tampaknya menyiratkan bahwa kompiler menyertakan beberapa program dalam executable akhir yang bertindak sebagai pengumpul sampah saat program sedang berjalan.
Halaman di situs web bahasa D tentang pengumpulan sampah - yang secara asli dikompilasi dan memiliki pengumpul sampah opsional - juga tampaknya mengisyaratkan bahwa beberapa program latar belakang berjalan berdampingan dengan program yang dapat dieksekusi asli untuk mengimplementasikan pengumpulan sampah.
D adalah bahasa pemrograman sistem dengan dukungan untuk pengumpulan sampah. Biasanya tidak perlu membebaskan memori secara eksplisit. Alokasikan saja sesuai kebutuhan, dan pemulung akan secara berkala mengembalikan semua memori yang tidak digunakan ke kumpulan memori yang tersedia.
Jika metode yang disebutkan di atas adalah digunakan, bagaimana tepatnya itu akan berhasil? Apakah kompiler menyimpan salinan dari beberapa program pengumpulan sampah dan menempelkannya ke setiap executable yang dihasilkannya?
Atau apakah saya cacat dalam pemikiran saya? Jika demikian, metode apa yang digunakan untuk menerapkan pengumpulan sampah untuk bahasa yang dikompilasi dan bagaimana cara kerjanya?
sumber
malloc()
.Jawaban:
Pengumpulan sampah dalam bahasa yang dikompilasi bekerja dengan cara yang sama seperti dalam bahasa yang ditafsirkan. Bahasa seperti Go menggunakan pelacakan pengumpul sampah meskipun kode mereka biasanya dikompilasi ke kode mesin sebelumnya.
(Tracing) pengumpulan sampah biasanya dimulai dengan berjalan di tumpukan panggilan dari semua utas yang saat ini berjalan. Benda-benda di tumpukan itu selalu hidup. Setelah itu, pengumpul sampah melintasi semua objek yang ditunjuk oleh objek hidup, hingga seluruh grafik objek hidup ditemukan.
Jelas bahwa melakukan ini memerlukan informasi tambahan yang tidak disediakan oleh bahasa seperti C. Secara khusus, ini membutuhkan peta bingkai stack dari masing-masing fungsi yang berisi offset semua pointer (dan mungkin datatypes mereka) serta peta semua tata letak objek yang berisi informasi yang sama.
Namun mudah untuk melihat bahwa bahasa yang memiliki jaminan tipe kuat (mis. Jika pointer dilemparkan ke tipe data yang berbeda tidak diizinkan) memang dapat menghitung peta tersebut pada waktu kompilasi. Mereka hanya menyimpan hubungan antara alamat instruksi dan peta bingkai tumpukan dan hubungan antara tipe data dan peta tata letak objek di dalam biner. Informasi ini kemudian memungkinkan mereka untuk melakukan traversal grafik objek.
Pengumpul sampah itu sendiri tidak lebih dari sebuah perpustakaan yang terhubung ke program, mirip dengan perpustakaan standar C. Misalnya, pustaka ini bisa menyediakan fungsi yang mirip dengan
malloc()
yang menjalankan algoritma pengumpulan jika tekanan memori tinggi.sumber
Kedengarannya tidak sopan dan aneh, tapi ya. Kompiler memiliki seluruh pustaka utilitas, yang mengandung jauh lebih banyak dari sekadar kode pengumpulan sampah, dan panggilan ke pustaka ini akan dimasukkan ke dalam setiap executable yang dibuatnya. Ini disebut perpustakaan runtime , dan Anda akan terkejut betapa banyak tugas berbeda yang biasanya dilayani.
sumber
malloc()
danfree()
tidak dibangun ke bahasa, bukan bagian dari sistem operasi, tetapi fungsi di pustaka ini. C ++ juga terkadang dikompilasi dengan perpustakaan pengumpulan sampah, meskipun bahasa itu tidak dirancang dengan GC dalam pikiran.dynamic_cast
dan pengecualian berfungsi, bahkan jika Anda tidak menambahkan GC.main()
, dan itu sah untuk, katakanlah, jalankan utas GC dalam kode ini. (Dengan asumsi GC tidak dilakukan di dalam panggilan alokasi memori.) Saat runtime, GC hanya benar-benar perlu tahu bagian mana dari objek yang merupakan pointer atau referensi objek, dan kompiler perlu memancarkan kode untuk menerjemahkan referensi objek ke pointer. jika GC memindahkan objek.crt0.o
(Yang merupakan kependekan dari " C R un T ime, the basics"), yang dihubungkan dengan setiap program (atau setidaknya setiap program yang tidak berdiri sendiri ).Itu cara yang aneh untuk mengatakan "kompiler menghubungkan program dengan perpustakaan yang melakukan pengumpulan sampah". Tapi ya, itulah yang terjadi.
Ini tidak istimewa: kompiler biasanya menghubungkan banyak perpustakaan ke dalam program yang mereka kompilasi; jika tidak, program yang dikompilasi tidak dapat melakukan banyak hal tanpa menerapkan kembali banyak hal dari awal: bahkan menulis teks ke layar / file / ... memerlukan perpustakaan.
Tapi mungkin GC berbeda dari perpustakaan lain ini, yang menyediakan API eksplisit yang dipanggil pengguna?
Tidak: di sebagian besar bahasa, pustaka runtime melakukan banyak pekerjaan di belakang layar tanpa API yang menghadap publik, di luar GC. Perhatikan tiga contoh ini:
Jadi perpustakaan pengumpulan sampah sama sekali tidak istimewa, dan apriori tidak ada hubungannya dengan apakah suatu program dikompilasi sebelumnya.
sumber
Kata-kata Anda salah. Sebuah bahasa pemrograman adalah spesifikasi yang ditulis dalam beberapa laporan teknis (untuk contoh yang baik, lihat R5RS ). Sebenarnya Anda mengacu pada beberapa implementasi bahasa tertentu (yang merupakan perangkat lunak).
(beberapa bahasa pemrograman memiliki spesifikasi yang buruk, atau bahkan hilang, atau hanya sesuai dengan beberapa implementasi sampel; masih, bahasa pemrograman mendefinisikan perilaku - misalnya memiliki sintaks dan semantik -, itu bukan produk perangkat lunak, tetapi dapat berupa diimplementasikan oleh beberapa produk perangkat lunak; banyak bahasa pemrograman memiliki beberapa implementasi; khususnya, "dikompilasi" adalah kata sifat yang berlaku untuk implementasi - bahkan jika beberapa bahasa pemrograman lebih mudah diimplementasikan oleh penerjemah daripada oleh kompiler.)
Perhatikan bahwa penerjemah dan penyusun memiliki makna yang longgar, dan beberapa implementasi bahasa dapat dianggap sebagai keduanya. Dengan kata lain, ada kontinum di antaranya. Baca Buku Naga terbaru dan pikirkan tentang bytecode , kompilasi JIT , memancarkan kode C dinamis yang dikompilasi ke dalam beberapa "plugin" lalu dlopen (3) -dengan proses yang sama (dan pada mesin saat ini, ini cukup cepat untuk kompatibel dengan REPL interaktif , lihat ini )
Saya sangat merekomendasikan membaca buku pegangan GC . Seluruh buku diperlukan untuk menjawab . Sebelum itu, baca wikipage Pengumpulan Sampah (yang saya anggap sudah Anda baca sebelum membaca di bawah).
Sistem runtime dari implementasi bahasa yang dikompilasi berisi pengumpul sampah, dan kompiler menghasilkan kode yang sesuai dengan sistem runtime tertentu. Secara khusus, alokasi primitif (dikompilasi ke kode mesin yang) akan (atau mungkin) memanggil sistem runtime.
Hanya dengan memancarkan kode mesin yang menggunakan (dan "ramah" dan "kompatibel dengan") sistem runtime.
Perhatikan bahwa Anda dapat menemukan beberapa perpustakaan pengumpulan sampah, khususnya Boehm GC , MPS Ravenbrook , atau bahkan Qish saya (yang tidak dirawat ) . Dan mengkode GC sederhana tidak terlalu sulit (namun, men-debug lebih sulit, dan mengkode GC kompetitif sulit ).
Dalam beberapa kasus, kompiler akan menggunakan GC konservatif (seperti Boehm GC ). Kemudian, tidak ada banyak kode. GC konservatif akan (ketika kompiler memanggil rutin alokasi, atau seluruh rutin GC) kadang-kadang memindai seluruh tumpukan panggilan , dan menganggap bahwa setiap zona memori (secara tidak langsung) yang dapat dijangkau dari tumpukan panggilan itu aktif. Ini disebut GC konservatif karena informasi pengetikan hilang: jika bilangan bulat pada tumpukan panggilan terlihat seperti beberapa alamat, itu akan diikuti, dll.
Dalam kasus lain (lebih sulit), runtime menyediakan pengumpulan sampah penyalinan generasional (contoh khasnya adalah kompiler Ocaml, yang mengkompilasi kode Ocaml ke kode mesin menggunakan GC semacam itu). Maka masalahnya adalah menemukan tepatnya pada tumpukan panggilan semua petunjuk, dan beberapa dari mereka digerakkan oleh GC. Kemudian kompiler menghasilkan meta-data yang menggambarkan frame panggilan stack, yang digunakan runtime. Jadi konvensi pemanggilan dan ABI menjadi spesifik untuk implementasi itu (yaitu kompiler) & sistem runtime.
Dalam beberapa kasus, kode mesin yang dihasilkan oleh kompiler (sebenarnya bahkan penutup menunjuk ke sana) adalah sampah yang dikumpulkan . Ini khususnya kasus untuk SBCL (implementasi Common Lisp yang baik) yang menghasilkan kode mesin untuk setiap interaksi REPL . Ini juga membutuhkan beberapa meta-data yang menggambarkan kode dan bingkai panggilan yang digunakan di dalamnya.
Sortir-dari. Namun, sistem runtime dapat berupa pustaka bersama, dll. Kadang-kadang (di Linux dan beberapa sistem POSIX lainnya) itu bahkan bisa menjadi juru bahasa skrip, misalnya diteruskan ke mengeksekusi (2) dengan shebang . Atau juru bahasa ELF , lihat peri (5) dan
PT_INTERP
, dll.BTW, kebanyakan kompiler untuk bahasa dengan pengumpulan sampah (dan sistem runtime mereka) saat ini adalah perangkat lunak gratis . Jadi unduh kode sumber dan pelajari.
sumber
Array#[]
O (1) kasus terburuk,Hash#[]
adalah O (1) amortisasi kasus terburuk). Dan yang terakhir: otak matz.Sudah ada beberapa jawaban bagus, tetapi saya ingin menghapus beberapa kesalahpahaman di balik pertanyaan ini.
Tidak ada yang namanya "bahasa kompilasi asli" per se. Misalnya, kode Java yang sama ditafsirkan (dan sebagian dikompilasi tepat waktu saat runtime) di ponsel lama saya (Java Dalvik) dan dikompilasi di telepon baru saya (ART).
Perbedaan antara menjalankan kode secara asli dan diinterpretasikan jauh lebih ketat daripada yang terlihat. Keduanya membutuhkan pustaka runtime dan beberapa sistem operasi untuk bekerja (*). Kode yang ditafsirkan membutuhkan penerjemah, tetapi penerjemah hanyalah bagian dari runtime. Tetapi meskipun ini tidak ketat, karena Anda dapat mengganti juru bahasa dengan kompiler (tepat waktu). Untuk kinerja maksimum, Anda mungkin menginginkan keduanya (desktop Java runtime berisi interpreter dan dua kompiler).
Tidak masalah bagaimana menjalankan kodenya, ia harus berperilaku sama. Mengalokasikan dan membebaskan memori adalah tugas untuk runtime (seperti halnya membuka file, memulai utas, dll.). Dalam bahasa Anda, Anda hanya menulis
new X()
atau sama. Spesifikasi bahasa mengatakan apa yang harus terjadi dan runtime yang melakukannya.Sebagian memori bebas dialokasikan, konstruktor dipanggil, dll. Ketika tidak ada cukup memori, maka pemulung akan dipanggil. Karena Anda sudah berada dalam runtime, yang merupakan bagian asli kode, keberadaan juru bahasa tidak masalah sama sekali.
Benar-benar tidak ada koneksi langsung antara penafsiran kode dan pengumpulan sampah. Hanya saja bahasa tingkat rendah seperti C dirancang untuk kontrol kecepatan dan segala sesuatu yang halus, yang tidak cocok dengan gagasan kode non-asli atau pengumpul sampah. Jadi hanya ada korelasi.
Ini sangat benar di masa lalu, di mana misalnya penerjemah Jawa sangat lambat dan pengumpul sampah agak tidak efisien. Saat ini, banyak hal berbeda dan berbicara tentang bahasa yang ditafsirkan telah kehilangan akal.
(*) Setidaknya ketika berbicara tentang kode tujuan umum, kesampingkan boot loader dan sejenisnya.
sumber
java myprog
adalah asli sebanyak atau sesedikitgrep myname /etc/passwd
atauld.so myprog
: Ini adalah executable (apa pun artinya) yang mengambil argumen dan melakukan operasi dengan data.Detailnya bervariasi di antara implementasi, tetapi umumnya beberapa kombinasi dari yang berikut:
Dalam GC tambahan dan bersamaan kode yang dikompilasi dan GC perlu bekerja sama untuk mempertahankan beberapa invarian. Misalnya dalam kolektor penyalinan, GC bekerja dengan menyalin data langsung dari ruang A ke ruang B, meninggalkan sampah. Untuk siklus berikutnya ia membalik A dan B dan berulang. Jadi satu aturan dapat memastikan bahwa setiap saat program pengguna mencoba merujuk ke objek di ruang A ini terdeteksi dan objek akan segera disalin ke ruang B, di mana program dapat terus mengaksesnya. Alamat penerusan ditinggalkan di ruang A untuk menunjukkan kepada GC bahwa ini telah terjadi sehingga referensi lain ke objek diperbarui saat mereka dilacak. Ini dikenal sebagai "pembatas baca".
Algoritma GC telah dipelajari sejak tahun 60an, dan ada literatur yang luas tentang subjek ini. Google jika Anda ingin informasi lebih lanjut.
sumber