Java Heap Allocation Lebih cepat dari C ++

13

Saya sudah memposting pertanyaan ini pada SO dan itu tidak masalah. Sayangnya itu ditutup (hanya perlu satu suara untuk membuka kembali) tetapi seseorang menyarankan saya mempostingnya di sini karena lebih cocok sehingga berikut ini secara harfiah merupakan salinan dari pertanyaan.

Saya membaca komentar tentang jawaban ini dan saya melihat kutipan ini.

Instansiasi objek dan fitur berorientasi objek sangat cepat digunakan (lebih cepat daripada C ++ dalam banyak kasus) karena mereka dirancang sejak awal. dan Koleksi cepat. Java standar mengalahkan C / C ++ standar di area ini, bahkan untuk kode C paling optimal.

Satu pengguna (dengan rep yang sangat tinggi, saya dapat menambahkan) dengan berani membela klaim ini, menyatakan itu

  1. alokasi heap di java lebih baik daripada C ++

  2. dan menambahkan pernyataan ini membela koleksi di java

    Dan koleksi Java lebih cepat dibandingkan dengan koleksi C ++ karena sebagian besar subsistem memori yang berbeda.

Jadi pertanyaan saya adalah apakah semua ini benar, dan jika demikian mengapa alokasi tumpukan java jauh lebih cepat.

java c++ performance heap collections Harun
sumber
Anda mungkin menemukan jawaban saya untuk pertanyaan serupa di atas SO berguna / relevan.
Daniel Pryden
1
Itu sepele: dengan Java (atau lingkungan terkelola dan terlarang lainnya) Anda dapat memindahkan objek dan memperbarui pointer ke objek tersebut - yaitu, mengoptimalkan untuk lokalitas cache yang lebih baik secara dinamis. Dengan C ++ dan penunjuk aritmatisnya dengan bitcast yang tidak terkontrol, semua objek disematkan ke lokasi mereka selamanya.
SK-logic
3
Saya tidak pernah berpikir saya akan mendengar seseorang mengatakan manajemen memori Java lebih cepat karena menyalin memori sepanjang waktu. mendesah.
gbjbaanb
1
@ gbjbaanb, pernahkah Anda mendengar tentang hierarki memori? Cache miss penalti? Apakah Anda menyadari bahwa pengalokasi tujuan umum mahal, sedangkan alokasi generasi pertama hanya operasi penambahan tunggal?
SK-logic
1
Walaupun ini mungkin agak benar dalam beberapa kasus, ia melewatkan poin bahwa di java Anda mengalokasikan semua yang ada di heap dan di c ++ Anda mengalokasikan banyak objek pada stack yang masih bisa menjadi jauh lebih cepat.
JohnB

Jawaban:

23

Ini adalah pertanyaan yang menarik, dan jawabannya rumit.

Secara keseluruhan, saya pikir adil untuk mengatakan bahwa pemulung sampah JVM dirancang dengan sangat baik dan sangat efisien. Ini mungkin sistem manajemen memori tujuan umum terbaik .

C ++ dapat mengalahkan JVM GC dengan pengalokasi memori khusus yang dirancang untuk tujuan tertentu. Contohnya mungkin:

  • Alokasi memori per-bingkai, yang menghapus seluruh area memori secara berkala. Ini sering digunakan dalam game C ++, misalnya, di mana area memori sementara digunakan satu kali per frame dan segera dibuang.
  • Alokasi kustom mengelola kumpulan objek berukuran tetap
  • Alokasi berdasarkan tumpukan (walaupun perhatikan bahwa JVM juga melakukan ini dalam berbagai keadaan, misalnya melalui analisis pelarian )

Pengalokasi memori khusus, tentu saja, dibatasi oleh definisi. Mereka biasanya memiliki batasan pada siklus hidup objek dan / atau batasan pada jenis objek yang dapat dikelola. Pengumpulan sampah jauh lebih fleksibel.

Pengumpulan sampah juga memberi Anda beberapa keuntungan signifikan dari perspektif kinerja:

  • Objek Instansiasi memang sangat cepat. Karena cara objek baru dialokasikan secara berurutan dalam memori, sering membutuhkan sedikit lebih dari satu penambahan pointer, yang tentu saja lebih cepat daripada algoritma alokasi tumpukan C ++.
  • Anda menghindari kebutuhan akan biaya manajemen siklus hidup - mis. Penghitungan referensi (kadang-kadang digunakan sebagai alternatif untuk GC) sangat buruk dari perspektif kinerja karena peningkatan yang terus-menerus dan penurunan jumlah referensi menambah banyak overhead kinerja (biasanya jauh lebih banyak daripada GC) .
  • Jika Anda menggunakan objek yang tidak dapat diubah, Anda dapat memanfaatkan pembagian struktural untuk menghemat memori dan meningkatkan efisiensi cache. Ini banyak digunakan oleh bahasa fungsional pada JVM seperti Scala dan Clojure. Sangat sulit untuk melakukan ini tanpa GC, karena sangat sulit untuk mengelola masa hidup objek yang dibagikan. Jika Anda percaya (seperti yang saya lakukan) bahwa ketidakmampuan dan pembagian struktural adalah kunci untuk membangun aplikasi berbarengan besar, maka ini bisa dibilang keuntungan kinerja terbesar dari GC.
  • Anda dapat menghindari penyalinan jika semua jenis objek dan siklusnya masing-masing dikelola oleh sistem pengumpulan sampah yang sama. Berbeda dengan C ++, di mana Anda sering harus mengambil salinan penuh data karena tujuan memerlukan pendekatan manajemen memori yang berbeda atau memiliki siklus hidup objek yang berbeda.

Java GC memiliki satu kelemahan utama: karena pekerjaan mengumpulkan sampah ditangguhkan dan dilakukan dalam potongan-potongan pekerjaan secara berkala, itu menyebabkan GC sesekali berhenti mengumpulkan sampah, yang dapat memengaruhi latensi. Ini biasanya bukan masalah untuk aplikasi tipikal, tetapi dapat mengesampingkan Java dalam situasi di mana hard realtime merupakan persyaratan (misalnya kontrol robot). Soft realtime (mis. Game, multimedia) biasanya OK.

mikera
sumber
ada perpustakaan khusus di area c ++ yang mengatasi masalah itu. Contoh yang mungkin paling terkenal untuk itu adalah SmartHeap.
Tobias Langner
5
Soft-realtime tidak berarti Anda boleh berhenti biasanya . Ini hanya berarti Anda dapat menjeda / mencoba lagi dalam situasi yang sangat buruk - biasanya tidak terduga - bukannya berhenti / macet / gagal. Tidak ada yang ingin menggunakan pemutar musik yang biasanya dijeda. Masalah jeda GC adalah hal itu biasanya terjadi dan tidak dapat diprediksi . Dengan cara itu, jeda GC tidak dapat diterima bahkan untuk aplikasi soft-realtime. Jeda GC hanya dapat diterima bila pengguna tidak memedulikan kualitas aplikasi. Dan saat ini, orang tidak begitu naif lagi.
Eonil
1
Silakan kirim beberapa pengukuran kinerja untuk mendukung klaim Anda, jika tidak kami akan membandingkan apel dan jeruk.
JBRWilkinson
1
@ Demetri Tetapi pada kenyataannya, itu hanya jika kasus terjadi terlalu banyak (dan sekali lagi, bahkan tidak terduga!) Kecuali Anda dapat memenuhi beberapa kendala yang tidak praktis. Dengan kata lain, C ++ jauh lebih mudah untuk situasi realtime apa pun.
Eonil
1
Untuk kelengkapan: ada sisi buruk lain dari kinerja GC: karena sebagian besar memori yang membebaskan GC terjadi di utas lain yang kemungkinan akan berjalan pada inti yang berbeda, itu berarti bahwa GCs mengeluarkan biaya pembatalan cache yang parah untuk sinkronisasi L1 / L2 cache antara core yang berbeda; Selain itu, pada server yang didominasi NUMA, cache L3 juga harus disinkronkan (dan lebih dari Hypertransport / QPI, aduh (!)).
No-Bugs Hare
3

Ini bukan klaim ilmiah. Saya hanya memberikan beberapa bahan untuk dipikirkan tentang masalah ini.

Satu analogi visual adalah ini: Anda diberi apartemen (unit perumahan) yang berkarpet. Karpetnya kotor. Apa cara tercepat (dalam hal jam) untuk membuat lantai apartemen berkilau bersih?

Jawaban: cukup gulung karpet lama; membuang; dan gulung karpet baru.

Apa yang kita abaikan di sini?

  • Biaya memindahkan barang-barang pribadi yang ada dan kemudian pindah.
    • Ini dikenal sebagai biaya pengumpulan sampah "stop-the-dunia".
  • Biaya karpet baru.
    • Yang, kebetulan untuk RAM, itu gratis.

Pengumpulan sampah adalah topik besar dan ada banyak pertanyaan baik di Programmers.SE dan StackOverflow.

Pada masalah sampingan, manajer alokasi C / C ++ yang dikenal sebagai TCMalloc bersama-sama dengan penghitungan referensi objek secara teoritis dapat memenuhi klaim kinerja terbaik dari setiap sistem GC.

rwong
sumber
sebenarnya c ++ 11 bahkan memiliki pengumpulan sampah ABI , ini sangat mirip dengan beberapa jawaban yang saya dapatkan pada SO
aaronman
Ini adalah ketakutan untuk merusak program C / C ++ yang ada (basis kode, seperti kernel Linux dan perpustakaan archaic_but_still_economically_important seperti libtiff) yang menghambat kemajuan inovasi bahasa di C ++.
rwong
Masuk akal, saya akan menebak dengan c ++ 17 itu akan lebih lengkap, tetapi kenyataannya adalah sekali Anda benar-benar belajar bagaimana memprogram dalam c ++ Anda bahkan tidak menginginkannya lagi, mungkin mereka dapat menemukan cara untuk menggabungkan dua idiom baik
aaronman
Apakah Anda sadar bahwa ada pemulung yang tidak menghentikan dunia? Sudahkah Anda mempertimbangkan implikasi kinerja pemadatan (di sisi GC) dan penumpukan tumpukan (untuk pengalokasi C ++ umum)?
SK-logic
2
Saya pikir kelemahan utama dalam analogi ini adalah bahwa apa yang sebenarnya dilakukan GC adalah menemukan potongan-potongan kotor, memotongnya dan kemudian melihat potongan-potongan yang tersisa kembali bersama-sama untuk membuat karpet baru.
svick
3

Alasan utama adalah bahwa, ketika Anda meminta Jawa untuk benjolan memori baru, itu langsung menuju ke ujung tumpukan dan memberi Anda sebuah blok. Dengan cara ini, alokasi memori secepat mengalokasikan pada stack (yang merupakan cara Anda melakukannya sebagian besar waktu di C / C ++, tetapi terlepas dari itu ..)

Jadi alokasi cepat seperti apa pun tetapi ... itu tidak termasuk biaya membebaskan memori. Hanya karena Anda tidak membebaskan apa pun sampai nanti tidak berarti itu tidak memerlukan biaya yang cukup besar, dan dalam kasus sistem GC, biayanya jauh lebih banyak daripada alokasi tumpukan 'normal' - tidak hanya GC harus menjalankan semua objek untuk melihat apakah mereka masih hidup atau tidak, itu juga kemudian harus membebaskan mereka, dan (biaya besar) menyalin memori sekitar untuk memadatkan tumpukan - sehingga Anda dapat memiliki alokasi cepat di akhir mekanisme (atau Anda kehabisan memori, C / C ++ misalnya akan berjalan tumpukan pada setiap alokasi mencari blok ruang kosong berikutnya yang dapat sesuai dengan objek).

Ini adalah salah satu alasan mengapa tolok ukur Java / .NET menunjukkan kinerja yang sangat baik, namun aplikasi dunia nyata menunjukkan kinerja yang sangat buruk. Saya hanya perlu melihat aplikasi di ponsel saya - yang sangat cepat, responsif semuanya ditulis menggunakan NDK, bahkan saya sangat terkejut.

Koleksi saat ini dapat cepat jika semua objek dialokasikan secara lokal, misalnya dalam satu blok yang berdekatan. Sekarang, di Jawa, Anda tidak mendapatkan blok yang berdekatan karena objek dialokasikan satu per satu dari ujung bebas heap. Anda dapat berakhir dengan mereka berdekatan dengan senang hati, tetapi hanya dengan keberuntungan (yaitu sampai ke kemauan rutinitas pemadatan GC dan bagaimana ia menyalin objek). C / C ++ di sisi lain secara eksplisit mendukung alokasi yang berdekatan (via stack, jelas). Secara umum tumpukan objek dalam C / C ++ tidak berbeda dengan BTW Java.

Sekarang dengan C / C ++ Anda bisa menjadi lebih baik daripada pengalokasi default yang dirancang untuk menghemat memori dan menggunakannya secara efisien. Anda dapat mengganti pengalokasi dengan kumpulan kumpulan blok tetap, sehingga Anda selalu dapat menemukan blok yang persis berukuran tepat untuk objek yang Anda alokasikan. Berjalan tumpukan hanya menjadi masalah pencarian bitmap untuk melihat di mana blok gratis berada, dan de-alokasi hanya mengatur ulang sedikit dalam bitmap itu. Biayanya adalah Anda menggunakan lebih banyak memori saat Anda mengalokasikan dalam blok ukuran tetap, sehingga Anda memiliki tumpukan blok 4 byte, yang lain untuk blok 16 byte, dll.

gbjbaanb
sumber
2
Sepertinya Anda sama sekali tidak mengerti GC. Pertimbangkan skenario paling umum - ratusan benda kecil dialokasikan secara konstan, tetapi hanya selusin di antaranya yang akan bertahan lebih dari satu detik. Dengan cara ini, sama sekali tidak ada biaya dalam membebaskan memori - selusin ini disalin dari generasi muda (dan dipadatkan, sebagai manfaat tambahan), dan sisanya dibuang tanpa biaya. Dan, omong-omong, Dalvik GC yang menyedihkan tidak ada hubungannya dengan GC modern yang canggih yang akan Anda temukan dalam implementasi JVM yang tepat.
SK-logic
1
Jika salah satu benda yang dibebaskan berada di tengah tumpukan, sisa tumpukan akan dipadatkan untuk merebut kembali ruang. Atau apakah Anda mengatakan pemadatan GC tidak terjadi kecuali yang terbaik yang Anda gambarkan? Saya tahu GC generasi jauh lebih baik di sini, kecuali jika Anda merilis objek di tengah generasi selanjutnya, dalam hal ini dampaknya bisa relatif besar. Ada sesuatu yang ditulis oleh Microsoftie yang mengerjakan GC mereka yang saya baca yang menggambarkan pengorbanan GC saat membuat GC generasi. Saya akan lihat apakah saya bisa menemukannya lagi.
gbjbaanb
1
"Tumpukan" apa yang kamu bicarakan? Sebagian besar sampah direklamasi pada tahap generasi muda, dan sebagian besar manfaat kinerja datang tepat dari pemadatan itu. Tentu saja, sebagian besar terlihat pada profil alokasi memori yang khas untuk pemrograman fungsional (banyak objek kecil yang berumur pendek). Dan, tentu saja, ada banyak peluang pengoptimalan yang belum dieksplorasi - misalnya, analisis kawasan dinamis yang dapat mengubah alokasi tumpukan di jalur tertentu menjadi alokasi tumpukan atau kumpulan secara otomatis.
SK-logic
3
Saya tidak setuju dengan klaim Anda bahwa alokasi tumpukan adalah 'secepat tumpukan' - alokasi tumpukan memerlukan sinkronisasi utas dan tumpukan tidak (menurut definisi)
JBRWilkinson
1
Saya kira begitu, tetapi dengan Java dan .net Anda mengerti maksud saya - Anda tidak perlu berjalan menimbun untuk menemukan blok gratis berikutnya sehingga secara signifikan lebih cepat dalam hal itu, tapi ya - Anda benar, itu harus terkunci yang akan merusak aplikasi berulir.
gbjbaanb
2

Eden Space

Jadi pertanyaan saya adalah apakah semua ini benar, dan jika demikian mengapa alokasi tumpukan java jauh lebih cepat.

Saya telah belajar sedikit tentang cara kerja Java GC karena sangat menarik bagi saya. Saya selalu mencoba untuk memperluas koleksi strategi alokasi memori saya di C dan C ++ (tertarik mencoba mengimplementasikan sesuatu yang serupa di C), dan itu adalah cara yang sangat, sangat cepat untuk mengalokasikan banyak objek secara burst mode dari sebuah perspektif praktis tetapi terutama karena multithreading.

Cara alokasi Java GC bekerja adalah dengan menggunakan strategi alokasi yang sangat murah untuk awalnya mengalokasikan objek ke ruang "Eden". Dari apa yang saya tahu, itu menggunakan pengalokasi kumpulan sekuensial.

Itu jauh lebih cepat hanya dalam hal algoritma dan mengurangi kesalahan halaman wajib daripada tujuan umum mallocdalam C atau default, melempar operator newdalam C ++.

Tapi pengalokasi sekuensial memiliki kelemahan mencolok: mereka dapat mengalokasikan potongan berukuran variabel, tetapi mereka tidak dapat membebaskan potongan individu. Mereka hanya mengalokasikan secara berurutan lurus dengan padding untuk perataan, dan hanya dapat membersihkan semua memori yang mereka dialokasikan sekaligus. Mereka biasanya berguna dalam C dan C ++ untuk membangun struktur data yang hanya membutuhkan penyisipan dan tanpa penghapusan elemen, seperti pohon pencarian yang hanya perlu dibangun sekali ketika program dimulai dan kemudian berulang kali dicari atau hanya memiliki kunci baru yang ditambahkan ( tidak ada kunci yang dihapus).

Mereka juga dapat digunakan bahkan untuk struktur data yang memungkinkan elemen untuk dihapus, tetapi elemen-elemen itu tidak benar-benar akan dibebaskan dari memori karena kita tidak dapat membatalkan alokasi mereka secara individual. Struktur seperti itu menggunakan pengalokasi sekuensial hanya akan mengkonsumsi lebih banyak dan lebih banyak memori, kecuali jika ada beberapa penundaan ditangguhkan di mana data disalin ke salinan yang baru, dipadatkan menggunakan pengalokasi sekuensial terpisah (dan itu kadang-kadang teknik yang sangat efektif jika pengalokasi tetap menang lakukan karena suatu alasan - hanya dengan lurus mengalokasikan salinan baru dari struktur data dan membuang semua memori yang lama).

Koleksi

Seperti pada contoh struktur data / kumpulan sekuensial di atas, itu akan menjadi masalah besar jika Java GC hanya mengalokasikan cara ini meskipun itu super cepat untuk alokasi burst banyak potongan individu. Itu tidak akan dapat membebaskan apa pun sampai perangkat lunak dimatikan, pada titik mana itu bisa membebaskan (membersihkan) semua kumpulan memori sekaligus.

Jadi, alih-alih, setelah siklus GC tunggal, pass dibuat melalui objek yang ada di ruang "Eden" (dialokasikan secara berurutan), dan yang masih direferensikan kemudian dialokasikan menggunakan pengalokasi yang lebih umum yang mampu membebaskan potongan individual. Orang-orang yang tidak lagi direferensikan akan dengan mudah dialokasikan dalam proses pembersihan. Jadi pada dasarnya itu "menyalin objek dari ruang Eden jika mereka masih dirujuk, dan kemudian membersihkan".

Ini biasanya akan cukup mahal, jadi itu dilakukan di utas latar belakang yang terpisah untuk menghindari secara signifikan menghentikan utas yang awalnya mengalokasikan semua memori.

Setelah memori disalin dari ruang Eden dan dialokasikan menggunakan skema yang lebih mahal ini yang dapat membebaskan potongan individu setelah siklus GC awal, objek bergerak ke wilayah memori yang lebih persisten. Potongan-potongan individual tersebut kemudian dibebaskan dalam siklus GC berikutnya jika tidak lagi menjadi referensi.

Kecepatan

Jadi, katakan dengan kasar, alasan Java GC mungkin mengungguli C atau C ++ pada alokasi heap langsung adalah karena menggunakan strategi alokasi termurah, yang sepenuhnya terdegenerasi di utas yang meminta untuk mengalokasikan memori. Maka menghemat pekerjaan yang lebih mahal yang biasanya perlu kita lakukan ketika menggunakan pengalokasi yang lebih umum seperti straight-up mallocuntuk utas lainnya.

Jadi secara konseptual GC sebenarnya harus melakukan lebih banyak pekerjaan secara keseluruhan, tetapi mendistribusikannya di seluruh utas sehingga biaya penuh tidak dibayar dimuka dengan satu utas. Hal ini memungkinkan thread mengalokasikan memori untuk melakukannya dengan sangat murah, dan kemudian menunda pengeluaran sebenarnya yang diperlukan untuk melakukan sesuatu dengan benar sehingga objek individu sebenarnya dapat dibebaskan ke utas lainnya. Dalam C atau C ++ ketika kami mallocatau panggilan operator new, kami harus membayar biaya penuh dimuka dalam utas yang sama.

Ini adalah perbedaan utama, dan mengapa Java mungkin mengungguli C atau C ++ dengan menggunakan panggilan naif ke mallocatau operator newuntuk mengalokasikan sekelompok potongan kecil secara individual. Tentu saja biasanya akan ada beberapa operasi atom dan beberapa potensi penguncian ketika siklus GC dimulai, tetapi mungkin dioptimalkan sedikit.

Pada dasarnya penjelasan sederhana bermuara pada membayar biaya yang lebih berat dalam satu utas ( malloc) vs. membayar biaya yang lebih murah dalam satu utas dan kemudian membayar biaya yang lebih berat di yang lain yang dapat berjalan secara paralel ( GC). Sebagai downside melakukan hal-hal dengan cara ini menyiratkan bahwa Anda memerlukan dua tipuan untuk mendapatkan dari referensi objek ke objek yang diperlukan untuk memungkinkan pengalokasi untuk menyalin / memindahkan memori di sekitar tanpa membatalkan referensi objek yang ada, dan juga Anda dapat kehilangan spasial lokalitas setelah memori objek adalah pindah dari ruang "Eden".

Terakhir tetapi tidak kalah pentingnya, perbandingannya agak tidak adil karena kode C ++ biasanya tidak mengalokasikan muatan kapal secara individual pada heap. Kode C ++ yang layak cenderung mengalokasikan memori untuk banyak elemen di blok yang berdekatan atau di stack. Jika itu mengalokasikan muatan kapal benda-benda kecil satu per satu di toko gratis, kodenya shite.


sumber
0

Itu semua tergantung siapa yang mengukur kecepatan, kecepatan implementasi apa yang mereka ukur, dan apa yang ingin mereka buktikan. Dan apa yang mereka bandingkan.

Jika Anda hanya melihat alokasi / deallocating, di C ++ Anda mungkin memiliki 1.000.000 panggilan ke malloc, dan 1.000.000 panggilan gratis (). Di Jawa, Anda akan memiliki 1.000.000 panggilan ke objek baru () dan seorang pengumpul sampah berjalan dalam satu lingkaran menemukan 1.000.000 objek yang dapat dibebaskan. Pengulangan dapat lebih cepat daripada panggilan gratis ().

Di sisi lain, malloc / free telah meningkatkan waktu lainnya, dan biasanya malloc / free hanya menetapkan satu bit dalam struktur data yang terpisah, dan dioptimalkan untuk malloc / free terjadi di utas yang sama, sehingga dalam lingkungan multithreaded tidak ada variabel memori bersama digunakan dalam banyak kasus (dan variabel penguncian atau memori bersama sangat mahal).

Di pihak ketiga, ada hal-hal seperti penghitungan referensi yang mungkin Anda perlukan tanpa pengumpulan sampah, dan itu tidak gratis.

gnasher729
sumber