Mungkin bermanfaat untuk menyimpan hanya satu std::string untuk menggabungkan semua data Anda, dan gunakan std::string_view di peta. Ini menghilangkan pertikaian mutex karena hanya ada satu alokasi memori yang diperlukan. string_view memiliki destruktor sepele sehingga Anda tidak memerlukan utas untuk itu.
Saya telah berhasil menggunakan teknik ini sebelumnya untuk mempercepat program hingga 2500%, tetapi itu juga karena teknik ini mengurangi penggunaan memori total.
Anda dapat mencoba menggunakan std::vector untuk menyimpan memori. std::vector elemen disimpan secara berdekatan, sehingga akan mengurangi cache miss (lihat Apa yang dimaksud dengan kode "ramah-cache"?)
Jadi Anda akan memiliki map<???,size_t> bukannya map<???,std::string> Anda akan memiliki satu tipuan lagi untuk mendapatkan string Anda (yang berarti biaya waktu proses tambahan) tetapi ini memungkinkan Anda untuk mengulang semua string dengan lebih sedikit cache-miss.
Alangkah baiknya jika Anda membuat ulang masalah yang Anda hadapi dengan MVCE dan menunjukkannya:Anda tahu, berkali-kali masalah yang Anda pikirkan adalah masalah Anda... bukan masalahnya.
Bagaimana saya bisa memastikan bahwa 2 masalah memori di atas adalah penyebabnya (alat apa saja/metrik?)
Mengingat informasi di sini saya akan menyarankan untuk menggunakan profiler - gprof (kompilasi dengan -g -pg) menjadi dasar. Jika Anda memiliki kompiler Intel, Anda dapat menggunakan vtune.
Ada versi gratis vtune tetapi saya pribadi hanya menggunakan versi komersial.
Selain itu, Anda dapat memasukkan pengaturan waktu dalam kode Anda:dari deskripsi tekstual, tidak jelas apakah waktu untuk mengisi peta sebanding dengan waktu yang dibutuhkan untuk menghapusnya, atau tumbuh secara konsisten saat dijalankan secara bersamaan. Saya akan mulai dengan jika. Perhatikan bahwa versi malloc() saat ini juga sangat dioptimalkan untuk konkurensi (apakah ini Linux? - tolong tambahkan tag ke pertanyaan).
Yang pasti ketika Anda menghapus peta ada jutaan free() dipanggil oleh std::~string() - tetapi Anda harus yakin apakah ini masalahnya atau tidak:Anda dapat menggunakan pendekatan yang lebih baik (banyak disebutkan dalam jawaban/komentar) atau pengalokasi khusus yang didukung oleh blok memori besar yang Anda buat/hancurkan sebagai satu unit.
Jika Anda memberikan MVCE sebagai titik awal, saya atau orang lain akan dapat memberikan jawaban yang konsisten (ini belum merupakan jawaban - tetapi terlalu panjang untuk menjadi komentar)
Hanya untuk memperjelas, program sengaja tidak pernah mengalokasikan barang dan membebaskan orang lain pada saat yang sama, dan hanya memiliki 2 utas, satu didedikasikan untuk penghapusan saja.
Ingatlah bahwa setiap string di peta membutuhkan satu (atau lebih) new dan satu delete (berdasarkan malloc() dan free() masing-masing), menjadi string baik di kunci atau di nilai.
Apa yang Anda miliki dalam "nilai" peta?
Karena Anda memiliki map<string,<set<int>> Anda memiliki banyak alokasi:Setiap kali Anda melakukan map[string].insert(val) kunci baru, kode Anda secara implisit memanggil malloc() untuk kedua string dan set. Bahkan jika kunci sudah ada di peta, int baru di set memerlukan node baru di set untuk dialokasikan.
Jadi, Anda memiliki banyak alokasi saat membangun struktur:memori Anda sangat terfragmentasi di satu sisi, dan kode Anda tampaknya sangat "intensif malloc", yang pada prinsipnya dapat menyebabkan panggilan memori menjadi kelaparan.
Alokasi/dealokasi memori multithreaded
Satu kekhasan subsistem memori modern, adalah bahwa mereka dioptimalkan untuk sistem multi-inti:ketika satu utas mengalokasikan memori pada satu inti, tidak ada kunci global, tetapi kunci utas-lokal atau inti-lokal untuk kumpulan utas-lokal .
Artinya, saat satu utas perlu membebaskan memori yang dialokasikan oleh utas lain, ada kunci non-lokal (lebih lambat) yang terlibat.
Ini berarti bahwa pendekatan terbaik adalah bahwa setiap utas mengalokasikan/membatalkan alokasi memorinya sendiri. Mengatakan bahwa pada prinsipnya Anda dapat mengoptimalkan banyak kode Anda dengan struktur data yang memerlukan lebih sedikit interaksi malloc/bebas, kode Anda akan lebih lokal, berkenaan dengan alokasi memori, jika Anda mengizinkan setiap utas:
- dapatkan satu blok data
- buat
map<string,<set<int>> - bebaskan
Dan Anda memiliki dua utas yang berulang kali melakukan tugas ini.
CATATAN:Anda memerlukan RAM yang cukup untuk menangani evaluator bersamaan, tetapi sekarang Anda sudah menggunakan 2 di antaranya yang dimuat secara bersamaan dengan skema buffering ganda (satu pengisian, satu pembersihan). Apakah Anda yakin sistem Anda tidak bertukar karena kehabisan RAM?
Selain itu, pendekatan ini dapat diskalakan:Anda dapat menggunakan utas sebanyak yang Anda inginkan. Dalam pendekatan Anda, Anda dibatasi pada 2 utas - satu membangun struktur, satu menghancurkannya.
Mengoptimalkan
Tanpa MVCE, memberikan arahan merupakan tugas yang sulit. Hanya ide yang hanya Anda ketahui yang dapat diterapkan saat ini:
- ganti set dengan vektor yang diurutkan, dicadangkan pada waktu pembuatan
- ganti kunci peta dengan vektor datar dari string yang diurutkan dengan jarak yang sama
- simpan kunci string secara berurutan dalam vektor datar, tambahkan hash untuk melacak kunci peta. Tambahkan peta hash untuk melacak urutan string dalam vektor.