Prestazioni di Malloc in un ambiente con multithreading

Question

Ho eseguito alcuni esperimenti con il framework openmp e ho trovato alcuni risultati strani che non sono sicuro di sapere come spiegare.

Il mio obiettivo è creare questa enorme matrice e quindi riempirla di valori. Ho realizzato alcune parti del mio codice come loop paralleli per ottenere prestazioni dal mio ambiente multithread. Sto eseguendo questo in una macchina con 2 processori xeon quad-core, quindi posso tranquillamente mettere fino a 8 thread simultanei in là.

Tutto funziona come previsto, ma per qualche motivo il ciclo for che alloca effettivamente le righe della mia matrice ha una prestazione di picco dispari quando si esegue con solo 3 thread. Da lì in poi, l'aggiunta di alcuni thread rende il mio ciclo più lungo. Con 8 thread richiede più tempo che sarebbe necessario con uno solo.

Questo è il mio circuito parallelo:

int width = 11; 
int height = 39916800; 
vector<vector<int> > matrix; 
matrix.resize(height);  
#pragma omp parallel shared(matrix,width,height) private(i) num_threads(3) 
{ 
    #pragma omp for schedule(dynamic,chunk) 
    for(i = 0; i < height; i++){ 
    matrix[i].resize(width); 
    } 
} /* End of parallel block */ 

Questo mi ha fatto pensare: c'è un problema di prestazioni noto al momento della chiamata malloc (che suppongo sia quello che il metodo di ridimensionamento della classe template è effettivamente chiamando) in un ambiente multithreaded? Ho trovato alcuni articoli che dicevano qualcosa sulla perdita di prestazioni nella liberazione dello spazio heap in un ambiente sottoposto a modifica, ma nulla di specifico sull'allocazione di nuovi spazi come in questo caso.

Solo per darvi un esempio, sto posizionando sotto un grafico del tempo impiegato dal ciclo per terminare in funzione del numero di thread per il ciclo di allocazione e di un ciclo normale che legge solo i dati da questa enorme matrice in seguito.

Entrambe le volte in cui misurate utilizzando la funzione gettimeofday e sembrano restituire risultati molto simili e precisi attraverso diverse istanze di esecuzione. Quindi, qualcuno ha una buona spiegazione?

Answer 1

Hai ragione riguardo a vector :: resize() internamente chiamando malloc. Malloc di implementazione-saggio è abbastanza complicato. Riesco a vedere più posti in cui malloc può portare alla contesa in un ambiente multi-thread.

1. malloc probabilmente mantiene una struttura di dati globale nello userspace per gestire lo spazio di indirizzamento dell'heap dell'utente. Questa struttura di dati globale dovrebbe essere protetta da accessi e modifiche simultanei. Alcuni allocatori hanno ottimizzazioni per alleviare il numero di accessi a questa struttura di dati globali ... Non so quanto sia arrivato lontano Ubuntu.

2. malloc alloca lo spazio indirizzo. Quindi, quando in realtà inizi a toccare la memoria allocata, passerai attraverso un "errore di pagina soft" che è un errore di pagina che consente al kernel del sistema operativo di allocare la RAM di supporto per lo spazio di indirizzi allocato. Questo può essere costoso a causa del viaggio nel kernel e richiederebbe al kernel di prendere alcuni blocchi globali per accedere alle proprie strutture di dati delle risorse RAM globali.

3. lo spazio utente allocatore probabilmente conserva uno spazio allocato per distribuire nuove allocazioni. Tuttavia, una volta esaurite le allocazioni, l'allocatore dovrebbe tornare al kernel e allocare altro spazio di indirizzamento dal kernel. Anche questo è costoso e richiederebbe un passaggio al kernel e al kernel prendendo alcuni blocchi globali per accedere alle strutture di dati relative alla gestione dello spazio degli indirizzi globali.

Bottomline, queste interazioni potrebbero essere abbastanza complicate. Se ti imbatti in questi colli di bottiglia, ti suggerirei di "pre-allocare" la tua memoria. Ciò comporterebbe allocarlo e quindi toccarlo tutto (tutto da un singolo thread) in modo da poter utilizzare quella memoria in seguito da tutti i thread senza eseguire conflitti contenti a livello di utente o kernel.

Answer 2

Gli allocatori di memoria sono sicuramente un possibile punto di contesa per più thread.

Fondamentalmente, l'heap è una struttura di dati condivisa, poiché è possibile allocare memoria su un thread e deselezionarlo su un altro. In effetti, il tuo esempio fa esattamente questo: il "ridimensionamento" libererà la memoria su ciascuno dei thread di lavoro, che inizialmente è stato assegnato altrove.

Le tipiche implementazioni di malloc incluse in gcc e altri compilatori utilizzano un blocco globale condiviso e funzionano ragionevolmente bene sui thread se la pressione di allocazione della memoria è relativamente bassa. Al di sopra di un determinato livello di allocazione, tuttavia, i thread inizieranno a serializzare sul blocco, si verificherà un eccessivo cambio di contesto e caching della cache e le prestazioni si ridurranno. Il tuo programma è un esempio di qualcosa che è pesante in allocazione, con un alloc + dealloc nel loop interno.

Sono sorpreso che un compilatore compatibile con OpenMP non abbia un'implementazione malloc con thread migliore? Esiste sicuramente - dai un'occhiata a this question per un elenco.

Answer 3

Tecnicamente, lo STL vector utilizza lo std::allocator che alla fine chiama new. new a sua volta chiama libag's malloc (per il proprio sistema Linux).

Questa implementazione di malloc è abbastanza efficiente come allocatore generale, è thread-safe, tuttavia non è scalabile (il malloc di GNU libc deriva da dlmalloc di Doug Lea). Esistono numerosi allocatori e documenti che migliorano con dlmalloc per fornire un'assegnazione scalabile.

Suggerisco di dare un'occhiata a Hoard da Dr. Emery Berger, tcmalloc da Google e Intel Threading Building Blocks allocatore scalabile.