(Ini bukan pemrograman game sendiri, tapi saya yakin jika saya menanyakan ini pada SO, saya akan diberitahu untuk tidak mengoptimalkan secara prematur, meskipun sejarah memberitahu kita bahwa setiap game besar akhirnya mengkhawatirkan hal-hal ini.)
Apakah ada dokumen di mana saja yang merangkum perbedaan dalam kinerja, dan khususnya penggunaan memori, antara implementasi perpustakaan C ++ standar yang berbeda? Detail dari beberapa implementasi dilindungi oleh NDA, tetapi perbandingan antara bahkan STLport vs libstdc ++ vs libc ++ vs MSVC / Dinkumware (vs EASTL?) Sepertinya sangat bermanfaat.
Secara khusus saya mencari jawaban untuk pertanyaan seperti:
- Berapa besar memori yang terkait dengan wadah standar?
- Wadah apa, jika ada, yang dilakukan alokasi dinamis hanya dengan diumumkan?
- Apakah std :: string melakukan copy-on-write? Optimasi string pendek? Tali?
- Apakah std :: deque menggunakan buffer cincin atau itu omong kosong?
deque
selalu diimplementasikan dalam STL dengan vektor.Jawaban:
Jika Anda tidak menemukan bagan perbandingan seperti itu, alternatifnya adalah menyuntikkan pengalokasi sendiri ke kelas STL yang dimaksud dan menambahkan beberapa pencatatan.
Implementasi yang saya uji (VC 8.0) tidak menggunakan alokasi memori hanya dengan mendeklarasikan string / vektor / deque, tetapi untuk itu daftar dan peta. String memiliki optimasi string pendek, karena menambahkan 3 karakter tidak memicu alokasi. Output ditambahkan di bawah kode.
Sejauh ini VC8 dan STLPort 5.2 diuji, berikut ini perbandingannya (termasuk dalam tes: string, vektor, deque, daftar, peta)
String keluaran VC8 / vektor / deque / daftar / peta:
STLPort 5.2. output dikompilasi dengan VC8
Hasil EASTL , tidak ada deque yang tersedia
sumber
std::string
tidak melakukan copy on write. CoW dulu merupakan pengoptimalan, tetapi begitu beberapa utas masuk ke dalam gambar, ini melampaui pesimis - ia dapat memperlambat kode dengan faktor besar. Sangat buruk bahwa Standar C ++ 0x secara aktif melarangnya sebagai strategi implementasi. Bukan hanya itu, tetapi permisifstd::string
dengan mengeluarkan iterator yang bisa berubah dan referensi karakter berarti bahwa "menulis" untukstd::string
memerlukan hampir setiap operasi.Optimasi string pendek adalah sekitar 6 karakter, saya percaya, atau sesuatu di wilayah itu. Tali tidak diizinkan -
std::string
harus menyimpan memori yang berdekatan untukc_str()
fungsi tersebut. Secara teknis, Anda bisa mempertahankan string yang berdekatan dan tali di kelas yang sama, tetapi tidak ada yang pernah melakukannya. Selain itu, dari apa yang saya ketahui tentang tali, membuat mereka aman untuk dimanipulasi akan sangat lambat - mungkin sama buruk atau lebih buruk dari Kontrak Karya.Tidak ada wadah yang melakukan alokasi memori dengan dinyatakan dalam STL modern. Wadah berbasis node seperti daftar dan peta yang digunakan untuk melakukannya tetapi sekarang mereka memiliki optimasi akhir tertanam dan tidak membutuhkannya. Adalah umum untuk melakukan optimasi yang disebut "swaptimization" di mana Anda bertukar dengan wadah kosong. Mempertimbangkan:
Tentu saja, dalam C ++ 0x ini berlebihan, tetapi dalam C ++ 03 maka ketika ini biasa digunakan, jika MahVariable mengalokasikan memori pada deklarasi maka itu mengurangi efektivitasnya. Saya tahu fakta bahwa ini digunakan untuk realokasi kontainer yang lebih cepat seperti
vector
pada MSVC9 STL yang menghilangkan kebutuhan untuk menyalin elemen.deque
menggunakan sesuatu yang disebut sebagai daftar tertaut yang belum dibuka. Ini pada dasarnya daftar array, biasanya ukuran-in-node tetap. Dengan demikian, untuk sebagian besar penggunaan, ia mempertahankan manfaat dari kedua struktur data - akses yang berdampingan dan penghapusan O (1) yang diamortisasi dan mampu menambahkan ke depan dan belakang dan pembatalan iterator yang lebih baik daripadavector
.deque
tidak pernah dapat diimplementasikan oleh vektor karena kompleksitas algoritmiknya dan jaminan pembatalan iterator.Berapa banyak overhead memori yang terkait? Sejujurnya, itu adalah pertanyaan yang tidak perlu ditanyakan. Wadah STL dirancang agar efisien, dan jika Anda mereplikasi fungsinya, Anda akan berakhir dengan sesuatu yang berkinerja lebih buruk atau berada di tempat yang sama lagi. Dengan mengetahui struktur data yang mendasarinya, Anda dapat mengetahui overhead memori yang mereka gunakan, berikan atau terima, dan itu hanya akan lebih dari itu untuk alasan yang bagus, seperti optimasi string kecil.
sumber
std::string
saatnya. Anda tidak harus menggunakan implementasi STL terbaru dan terhebat untuk itu. msdn.microsoft.com/en-us/library/22a9t119.aspx mengatakan "Jika sebuah elemen dimasukkan di depan, semua referensi tetap valid". Tidak yakin bagaimana Anda bermaksud menerapkannya dengan buffer bundar, karena Anda perlu mengubah ukuran ketika sudah penuh.Jika itu benar-benar pertanyaan Anda (yang pastinya bukan apa yang Anda katakan dalam teks pertanyaan aktual Anda, yang berakhir dalam 4 pertanyaan, tidak ada yang menanyakan di mana Anda mungkin menemukan sumber daya), maka jawabannya hanyalah:
Tidak ada.
Mayoritas pemrogram C ++ tidak perlu terlalu peduli dengan overhead dari struktur pustaka standar, kinerja cache dari mereka (yang sangat tergantung pada kompiler), atau hal semacam itu. Belum lagi, Anda biasanya tidak bisa memilih implementasi perpustakaan standar Anda; Anda menggunakan apa yang datang dengan kompiler Anda. Jadi, bahkan jika itu melakukan beberapa hal yang tidak menyenangkan, pilihan untuk alternatif terbatas.
Tentu saja ada programmer yang peduli tentang hal semacam ini. Tapi mereka semua bersumpah menggunakan perpustakaan standar sejak lama.
Jadi, Anda memiliki satu kelompok programmer yang tidak peduli. Dan sekelompok programmer lain yang akan peduli jika mereka menggunakannya, tetapi karena mereka tidak menggunakannya, mereka tidak peduli. Karena tidak ada yang peduli tentang hal itu, tidak ada informasi nyata tentang hal semacam ini. Ada tambalan informal informasi di sana-sini (C ++ Efektif memiliki bagian tentang std :: string implementasi dan perbedaan besar di antara mereka), tetapi tidak ada yang komprehensif. Dan tentu saja tidak ada yang diperbarui.
sumber