Potrebbe essere utile memorizzare un solo std::string per tutti i tuoi dati combinati e usa std::string_view nella mappa. Ciò elimina la contesa mutex poiché è necessaria solo un'allocazione di memoria. string_view ha un banale distruttore quindi non hai bisogno di un thread per quello.
Ho già utilizzato con successo questa tecnica per velocizzare un programma del 2500%, ma anche perché questa tecnica ha ridotto l'utilizzo totale della memoria.
Puoi provare a usare un std::vector per conservare la memoria. std::vector gli elementi sono memorizzati in modo contiguo, quindi ridurrà la mancanza di cache (vedi Cos'è un codice "cache-friendly"?)
Quindi avrai un map<???,size_t> invece di map<???,std::string> avrai un'ulteriore indiretta per ottenere la tua stringa (il che significa un costo di esecuzione extra) ma ti permetterà di iterare su tutte le stringhe con molto meno cache-miss.
Sarebbe bello se ricreassi il problema che stai riscontrando con un MVCE e lo mostrassi:sai, molte volte il problema che stai pensando è il tuo problema... non è il problema.
Come posso trovare con certezza che i 2 problemi di memoria di cui sopra sono la causa (qualsiasi strumento/metrica?)
Date le informazioni qui, suggerirei di utilizzare un profiler - gprof (compilare con -g -pg) è quello di base. Se hai a disposizione il compilatore Intel puoi usare vtune.
Esiste una versione gratuita di vtune ma personalmente ho utilizzato solo la versione commerciale.
Oltre a questo puoi inserire i tempi nel tuo codice:dalla descrizione testuale, non è chiaro se il tempo per popolare la mappa sia paragonabile al tempo necessario per cancellarla, o se cresce costantemente quando viene eseguito contemporaneamente. Inizierei con se. Si noti che l'attuale versione di malloc() è notevolmente ottimizzata anche per la concorrenza (è questo Linux? - aggiungere un tag alla domanda per favore).
Di sicuro quando cancelli la mappa ci sono milioni di free() è chiamato da std::~string() - ma devi essere sicuro che questo sia il problema o meno:puoi utilizzare un approccio migliore (molti citati nelle risposte/commenti) o un allocatore personalizzato supportato da un enorme blocco di memoria che crei/distruggi come una singola unità.
Se fornisci un MVCE come punto di partenza, io o altri saremo in grado di fornire una risposta coerente (questa non è ancora una risposta, ma è troppo lunga per essere un commento)
Giusto per chiarire, il programma deliberatamente non alloca mai cose e ne libera altre allo stesso tempo, e ha solo 2 thread, uno dedicato solo alla cancellazione.
Tieni presente che ogni stringa nella mappa necessita di uno (o più) new e un delete (basato su malloc() e free() rispettivamente), essendo le stringhe nelle chiavi o nei valori.
Cosa hai nei "valori" della mappa?
Dato che hai un map<string,<set<int>> hai molte allocazioni:ogni volta che esegui un map[string].insert(val) di una nuova chiave, il tuo codice chiama implicitamente malloc() sia per la corda che per l'insieme. Anche se la chiave è già nella mappa, un nuovo int nel set richiede l'allocazione di un nuovo nodo nel set.
Quindi hai davvero molte allocazioni mentre costruisci la struttura:la tua memoria è molto frammentata su un lato, e il tuo codice sembra davvero "malloc intensive", il che potrebbe in linea di principio portare le chiamate di memoria a morire di fame.
Allocazioni/deallocazioni di memoria multithread
Una particolarità dei moderni sottosistemi di memoria è che sono ottimizzati per sistemi multi-core:quando un thread alloca memoria su un core, non c'è un blocco globale, ma un blocco thread-local o core-local per un pool thread-local .
Ciò significa che quando un thread deve liberare la memoria allocata da un altro, è coinvolto un blocco non locale (più lento).
Ciò significa che l'approccio migliore è che ogni thread allochi/dealloca la propria memoria. Detto che in linea di principio puoi ottimizzare molto il tuo codice con strutture di dati che richiedono meno interazioni malloc/libere, il tuo codice sarà più locale, rispetto alle allocazioni di memoria, se lasci che ogni thread:
- ottieni un blocco di dati
- crea il
map<string,<set<int>> - liberalo
E hai due thread che eseguono ripetutamente questa operazione.
NOTA:hai bisogno di abbastanza RAM per gestire i valutatori simultanei, ma ora ne stai già utilizzando 2 caricati contemporaneamente con uno schema di doppio buffering (un riempimento, una pulizia). Sei sicuro che il tuo sistema non stia effettuando lo swapping a causa dell'esaurimento della RAM?
Inoltre, questo approccio è scalabile:puoi usare tutti i thread che vuoi. Nel tuo approccio eri limitato a 2 thread:uno che costruisce la struttura, l'altro che la distrugge.
Ottimizzazione
Senza un MVCE è un compito difficile dare indicazioni. Solo idee che sai solo se possono essere applicate ora:
- sostituisci l'insieme con il vettore ordinato, riservato al momento della creazione
- sostituisci le chiavi della mappa con un vettore piatto di stringhe ordinate equidistanti
- memorizza le chiavi della stringa in sequenza in un vettore piatto, aggiungi hash per tenere traccia delle chiavi della mappa. Aggiungi una hash-map per tenere traccia dell'ordine delle stringhe nel vettore.