Pengumpulan sampah di V8: cara kerja Orinoco GC baru

Sejujurnya, ini adalah salah satu artikel paling brutal yang saya baca baru-baru ini: ada banyak tentang kematian di usia muda, tentang penganiayaan dari satu bidang memori ke bidang lain dan tentang perjuangan keras untuk produktivitas. Secara umum, selamat datang di kat - ada terjemahan dari artikel yang bagus oleh Peter Marshall tentang cara pengumpulan sampah di V8 hari ini.



Selama beberapa tahun terakhir, pendekatan pengumpulan sampah di V8 telah banyak berubah. Sebagai bagian dari proyek Orinoco, ia telah beralih dari pendekatan stop-the-world yang konsisten ke pendekatan paralel dan kompetitif dengan penambahan mundur.

Catatan: jika Anda lebih suka menonton laporan daripada membaca artikel, Anda bisa melakukannya di sini . Jika tidak, baca terus.

Setiap pengumpul sampah memiliki serangkaian tugas yang perlu dilakukan secara berkala:

1. Temukan benda hidup / mati dalam memori.
   
2. Menggunakan kembali memori yang ditempati benda mati.
   
3. Memori compact / defragment (opsional).
   

Tugas-tugas ini dapat dilakukan secara berurutan, atau Anda dapat bergantian. Cara termudah adalah menghentikan eksekusi JavaScript dan melakukan semuanya secara berurutan di utas utama. Namun, ini dapat menyebabkan penundaan, yang kita bicarakan di posting sebelumnya , serta penurunan kinerja keseluruhan program.

GC Utama (mark-compact penuh)

GC utama mengumpulkan sampah dari seluruh tumpukan.

Pembersihan sampah dilakukan dalam tiga tahap: pelabelan, pembuangan, dan pemadatan

Menandai

Menentukan objek dari mana Anda dapat membebaskan memori adalah bagian penting dari pengumpul sampah. Dia menganggap objek hidup berdasarkan informasi tentang jangkauannya. Ini berarti bahwa setiap objek yang dirujuk dari runtime saat ini harus disimpan dalam memori, dan semua objek yang tidak dapat diakses dapat dirakit oleh GC.

Menandai adalah proses menemukan objek yang dapat dijangkau. GC memiliki satu set pointer yang mulai dicari, yang disebut root set. Set ini mencakup objek dari tumpukan eksekusi saat ini dan objek global. Dimulai dengan set ini, GC mengikuti setiap penunjuk ke objek JavaScript dan menandai masing-masing sebagai dapat dijangkau, setelah itu bergerak ke penunjuk dari objek ke objek lain dan mengulangi proses ini secara berulang hingga setiap objek yang dapat dijangkau ditandai.

Pembuangan

Pembuangan adalah proses di mana area memori yang tersisa dari benda mati dimasukkan ke dalam daftar yang disebut daftar bebas. Setelah proses penandaan selesai, GC menemukan area tersebut dan menambahkannya ke daftar yang sesuai. Daftar bebas berbeda satu sama lain dalam ukuran memori yang disimpan di dalamnya, yang memungkinkan Anda untuk dengan cepat menemukan yang tepat. Selanjutnya, ketika kita ingin mengalokasikan memori, kita akan melihat di salah satu daftar dan menemukan bagian dengan ukuran yang sesuai.

Seal

Juga, GC utama terkadang membuat keputusan tentang pembersihan / pemadatan beberapa halaman memori berdasarkan perkiraan heuristiknya sendiri berdasarkan tingkat fragmentasi halaman. Anda dapat menganggap pemadatan sebagai analog defragmentasi hard drive pada PC lama. Kami menyalin objek yang masih hidup ke halaman lain yang belum dikompres (di sini hanya menggunakan daftar gratis). Dengan demikian kita dapat menggunakan kembali potongan-potongan kecil memori yang tersebar yang tersisa dari benda mati.

Salah satu kelemahan dari GC yang menyalin objek yang masih hidup adalah bahwa ketika Anda membuat banyak objek berumur panjang, Anda harus membayar harga tinggi untuk menyalinnya. Karena alasan ini, hanya beberapa halaman memori yang sangat terfragmentasi yang dikompres, sedangkan sisanya dibuang, yang tidak memerlukan penyalinan benda yang masih hidup.

Perangkat pembangkit memori

Tumpukan di V8 dipecah menjadi daerah yang disebut generasi. Ada generasi muda (yang pada gilirannya dibagi menjadi generasi "palungan" dan "menengah") dan generasi tua. Objek yang dibuat ditempatkan di "palungan". Selanjutnya, jika mereka selamat dari pengumpulan sampah berikutnya, mereka tetap berada di generasi yang lebih muda, tetapi masuk ke dalam kategori "perantara". Jika mereka bertahan hidup setelah kebaktian berikutnya, mereka ditempatkan di generasi yang lebih tua.

Sekelompok V8 dipecah menjadi beberapa generasi. Benda bergerak dari muda ke tua jika mereka selamat dari pengumpulan sampah

Dalam pengumpulan sampah, ada istilah penting "hipotesis generasi". Secara sederhana, ini berarti bahwa sebagian besar benda "mati muda." Dengan kata lain, sebagian besar objek dibuat dan mati segera dari sudut pandang GC. Dan pernyataan ini berlaku tidak hanya untuk JavaScript, tetapi untuk sebagian besar bahasa pemrograman dinamis.

Organisasi tumpukan di V8 didasarkan pada hipotesis di atas. Sebagai contoh, pada pandangan pertama, mungkin tampak berlawanan dengan intuisi bahwa GC memadatkan / memindahkan objek yang selamat dari pengumpulan sampah, karena menyalin objek adalah operasi yang cukup mahal untuk dilakukan selama pengumpulan sampah. Tetapi, berdasarkan hipotesis generasi, kita tahu bahwa sangat sedikit objek yang akan selamat dari prosedur ini. Jadi, jika Anda hanya memindahkan objek yang masih hidup, semua yang tidak dipindahkan dapat secara otomatis dianggap sampah. Ini berarti bahwa harga yang kami bayar untuk penyalinan sebanding dengan jumlah objek yang bertahan, dan tidak semua dibuat.

Auxiliary GC (pemulung)

Sebenarnya ada dua pemulung di V8. Main (mark-compact) mengumpulkan sampah dengan cukup efisien dari seluruh tumpukan, sedangkan yang kedua mengumpulkan sampah hanya dalam memori yang masih muda, karena hipotesis generasi memberi tahu kita bahwa upaya pengumpulan sampah utama harus diarahkan ke sana.

Prinsip pengoperasian GC bantu adalah bahwa objek yang bertahan selalu pindah ke halaman memori baru. Dalam V8, memori muda dibagi menjadi dua bagian. Seseorang selalu bebas untuk membiarkan benda yang masih hidup dipindahkan ke dalamnya, dan selama perakitan, daerah yang awalnya kosong ini disebut To-space. Area tempat penyalinan disebut Dari-ruang. Dalam kasus terburuk, setiap objek dapat bertahan, dan kemudian Anda harus menyalinnya semua.

Untuk jenis perakitan ini, ada satu set pointer terpisah yang merujuk dari memori lama ke muda. Dan alih-alih memindai seluruh tumpukan, kami menggunakan penghalang tulis untuk mempertahankan set ini. Jadi, menggabungkan set ini dengan tumpukan dan objek global, kami mendapatkan semua tautan di memori muda tanpa harus memindai semua objek dari memori lama.

Saat menyalin objek dari Dari ruang ke Ke ruang, semua objek yang bertahan hidup ditempatkan di bagian memori yang berkelanjutan. Dengan demikian, adalah mungkin untuk menghilangkan fragmentasi - celah memori yang tersisa dari benda mati. Setelah transfer selesai, Ke-ruang menjadi Dari-ruang, dan sebaliknya. Segera setelah GC menyelesaikan tugasnya, memori untuk objek baru akan dialokasikan mulai dari alamat bebas pertama di Dari-ruang.

Pemulung memindahkan objek yang masih hidup ke halaman memori baru

Jika Anda hanya menggunakan strategi ini dan tidak memindahkan objek dari memori muda, maka memori akan berakhir dengan cepat. Oleh karena itu, objek yang selamat dari dua koleksi sampah dipindahkan ke memori lama.

Langkah terakhir adalah memperbarui pointer ke objek yang telah dipindahkan. Setiap objek yang disalin meninggalkan alamat aslinya, meninggalkan alamat penerusan, yang diperlukan untuk menemukan objek asli di masa depan.

Pemulung mentransfer objek "perantara" ke memori lama, dan objek dari "palungan" - ke halaman baru

Dengan demikian, pengumpulan sampah di memori muda terdiri dari tiga langkah: menandai objek, menyalinnya, memperbarui pointer.

Orinoco

Sebagian besar algoritma ini dijelaskan dalam berbagai sumber dan sering digunakan dalam lingkungan runtime yang mendukung pengumpulan sampah otomatis. Tetapi GC di V8 telah datang jauh sebelum menjadi alat yang benar-benar modern. Salah satu metrik signifikan yang menggambarkan kinerjanya adalah seberapa sering dan berapa lama utas utama berhenti sementara pengumpul sampah menjalankan fungsinya. Untuk pembuat stop-the-world klasik, kali ini meninggalkan bekas pada pengalaman menggunakan halaman karena keterlambatan, kualitas rendering yang buruk dan peningkatan waktu respons.

Logo Orinoco GC V8

Orinoco adalah nama kode GC yang menggunakan teknik pengumpulan sampah paralel, inkremental, dan kompetitif yang canggih. Ada beberapa istilah yang memiliki makna khusus dalam konteks GC, jadi mari kita memberikan definisi mereka terlebih dahulu.

Paralelisme

Paralelisme adalah ketika utas utama dan tambahan melakukan kira-kira jumlah pekerjaan yang sama per unit waktu. Ini masih merupakan pendekatan stop-the-world, tetapi durasi jeda dalam kasus ini dibagi dengan jumlah utas yang berpartisipasi dalam pekerjaan (dikurangi biaya sinkronisasi).

Ini adalah yang paling sederhana dari tiga teknik. Tumpukan tidak berubah karena JavaScript tidak dijalankan, sehingga cukup untuk utas mempertahankan sinkronisasi akses ke objek.

Utas utama dan tambahan bekerja pada tugas yang sama pada saat yang sama

Inkrementalitas

Inkrementalitas adalah ketika utas utama melakukan sejumlah kecil pekerjaan sebentar-sebentar. Alih-alih pengumpulan sampah lengkap, tugas-tugas kecil untuk pengumpulan parsial dilakukan.

Ini adalah tugas yang lebih sulit, karena JavaScript berjalan di antara rakitan tambahan, yang berarti bahwa heap state berubah, yang pada gilirannya dapat membatalkan sebagian pekerjaan yang dilakukan pada iterasi sebelumnya.

Seperti dapat dilihat dari diagram, pendekatan ini tidak mengurangi jumlah total pekerjaan (dan, sebagai aturan, bahkan meningkatkannya), tetapi mendistribusikan pekerjaan ini tepat waktu. Oleh karena itu, ini adalah cara yang baik untuk menyelesaikan salah satu tugas utama - mengurangi waktu respons arus utama.
Dengan membiarkan JavaScript berjalan dengan sedikit gangguan dalam pengumpulan sampah, aplikasi dapat terus menjadi responsif: menanggapi input pengguna dan memperbarui animasi.

Area kecil GC berfungsi di utas utama

Daya saing

Persaingan adalah ketika utas utama menjalankan JavaScript terus menerus dan utas tambahan mengumpulkan sampah di latar belakang. Ini adalah yang paling sulit dari tiga teknik: heap dapat berubah kapan saja, membatalkan pekerjaan yang dilakukan oleh GC sebelumnya.

Selain itu, ada juga balapan baca / tulis, karena aliran bantu dan utama secara bersamaan membaca atau memodifikasi objek yang sama.

Perakitan berlangsung sepenuhnya di latar belakang, utas utama saat ini dapat menjalankan JavaScript

Status GC di V8

Memulung

V8 mendistribusikan pekerjaan pengumpulan sampah di antara thread tambahan di memori muda (scavenging). Setiap utas menerima satu set petunjuk, yang mengikuti itu memindahkan semua objek hidup ke ruang.

Saat memindahkan objek ke ruang, utas perlu disinkronkan melalui operasi baca / tulis / bandingkan atom untuk menghindari situasi di mana, misalnya, utas lain telah mendeteksi objek yang sama, tetapi mengikuti jalur yang berbeda, dan juga mencoba untuk memindahkannya.

Thread yang memindahkan objek ke To-space kemudian kembali dan meninggalkan pointer penerusan sehingga utas lain yang menemukan objek ini dapat mengikuti alamat yang benar. Untuk alokasi memori yang cepat dan bebas sinkronisasi untuk objek yang bertahan, utas menggunakan buffer lokal utas.

Perakitan paralel mendistribusikan kerja antara beberapa utas bantu dan utas utama

Core gc

GC utama di V8 dimulai dengan menandai objek. Segera setelah tumpukan mencapai batas tertentu (dihitung secara dinamis), penanda kompetitif memulai pekerjaan mereka. Setiap aliran menerima satu set petunjuk, dan, mengikuti mereka, mereka menandai setiap objek yang ditemukan dapat dijangkau.

Pelabelan kompetitif terjadi sepenuhnya di latar belakang saat JavaScript berjalan di utas utama. Hambatan tulis digunakan untuk melacak tautan baru antara objek yang dibuat dalam JavaScript saat utas menandai.


GC Utama menggunakan pelabelan kompetitif, pembuangan, dan pemadatan paralel dan pembaruan pointer

Pada akhir pelabelan kompetitif, utas utama melakukan langkah cepat untuk mengakhiri pelabelan. Selama ini, eksekusi JavaScript di utas utama dijeda.

Set root dipindai lagi untuk memastikan bahwa semua objek hidup ditandai, dan kemudian kompresi memori dan pembaruan pointer dimulai pada beberapa utas.
Tidak semua halaman di memori lama dipadatkan - mereka yang tidak akan dipindai ke area memori yang dibebaskan (sweeping) untuk daftar mereka dalam daftar bebas.

Selama jeda ini, tugas sweeping mulai, yang bekerja secara kompetitif dengan tugas-tugas kompresi memori dan utas utama dan dapat berlanjut bahkan ketika JavaScript dijalankan di utas utama.

GC waktu idle

Pengembang JavaScript tidak memiliki akses ke GC - ini adalah bagian dari lingkungan implementasi. Dan meskipun kode JS tidak dapat menggunakan GC secara langsung, V8 menyediakan akses ke lingkungan yang menyematkan engine.

GC dapat mengirim tugas (tugas idle) yang dapat dilakukan "di waktu luang Anda" dan yang merupakan bagian dari pekerjaan yang harus tetap dilakukan. Lingkungan seperti Chrome, tempat mesin tertanam, mungkin memiliki gagasan tentang apa yang harus dipertimbangkan sebagai waktu luang. Misalnya, di Chrome, pada kecepatan bingkai 60 frame per detik, browser memiliki sekitar 16,6 ms untuk membuat bingkai animasi.

Jika pekerjaan animasi selesai lebih awal, di waktu luang Anda, sebelum frame berikutnya, Chrome dapat melakukan beberapa tugas yang diterima dari GC.

GC menggunakan waktu bebas aliran utama untuk melakukan pra-pembersihan

Detail dapat ditemukan di publikasi kami di Idle-time GC .

Ringkasan

GC di V8 telah berkembang jauh sejak diperkenalkan. Menambahkan teknik paralel, inkremental, dan kompetitif memerlukan waktu beberapa tahun, tetapi terbayar, memungkinkan Anda untuk melakukan sebagian besar pekerjaan di latar belakang.

Semua yang terkait dengan jeda dari aliran utama, waktu respons, dan pemuatan halaman telah meningkat secara signifikan, yang memungkinkan membuat animasi, pengguliran, dan interaksi pengguna pada halaman menjadi lebih lancar. Kolektor paralel memungkinkan untuk mengurangi waktu pemrosesan total memori muda sebesar 20-50%, tergantung pada beban.

Idle-time GC mengurangi ukuran tumpukan yang digunakan untuk Gmail sebesar 45%. Pelabelan dan pembuangan kompetitif (sweeping) dapat mengurangi durasi jeda GC di game WebGL yang berat hingga 50%.

Namun, pekerjaannya belum selesai. Mengurangi jeda tetap merupakan tugas penting untuk menyederhanakan kehidupan pengguna web, dan kami sedang mencari kemungkinan menggunakan teknik yang lebih maju untuk mencapai tujuan.

Selain itu, Blink (renderer di Chrome) juga dilengkapi dengan pelumas, dan kami sedang berupaya meningkatkan interaksi antara kedua GC, serta menggunakan teknik Orinoco di Oilpan.

Sebagian besar pengembang JavaScript tidak perlu memikirkan cara kerja GC, tetapi beberapa pemahaman tentang hal ini dapat membantu Anda membuat keputusan terbaik terkait penggunaan memori dan pola pemrograman. Sebagai contoh, mengingat struktur generasi dari tumpukan V8, objek yang hidup rendah sebenarnya cukup murah dari sudut pandang GC, karena kami membayar terutama untuk objek yang selamat. Dan pola-pola semacam ini bukan hanya karakteristik JavaScript, tetapi juga banyak bahasa dengan dukungan untuk pengumpulan sampah.