Misterioso puntatore legati multithreading rallentamento

Question

Background: Così sto lavorando su un raytracer .. per la mia costruzione del schema di partizionamento spaziale, inizialmente ho avuto qualche codice come questo:

if (msize <= 2) { // create a leaf node 
    Model **models = new Model*[msize]; 
    for (uint i=0; i<msize; ++i) 
     models[i] = &mlist[i]; 
    *arrayPtr = Node(models, msize); // class Node contains a copy of models 
    ... increment arrayPtr ... 
    return; 
} 

In sostanza, dopo questo spaziale l'albero di partizionamento è costruito, i raggi attraversano l'albero alla ricerca di modelli, che sono tutti memorizzati in un unico grande array. I nodi foglia contengono i puntatori in una serie di puntatori di Modelli.

Poi ho capito che hey, non c'è motivo per me di aggiungere quel livello extra di indirezione; se sistemo correttamente i miei modelli, posso ottenere i nodi foglia per puntare direttamente alla grande serie di modelli. I modelli adiacenti tra loro nel grande array appartengono tutti a un determinato nodo foglia, quindi le foglie conterrebbero i puntatori ai Modelli. Così ho fatto questo e l'ho testato con tutto il resto tenuto costante.

Ora si potrebbe pensare che questo ovviamente accelererebbe il programma. Bene, velocizza la versione single-threaded (di circa il 10%), ma rallenta quella multithreaded (di circa il 15%! Che è abbastanza significativo se stai facendo pesanti ottimizzazioni.) Sono abbastanza ad un perdita su come affrontare questo problema - pensavo che l'indirezione fosse negativa, pensavo che ridurre l'utilizzo della memoria fosse buono, in particolare per il multithreading .. non c'è nessuna scrittura sul nodo foglia o sul modello, tutta la scrittura viene eseguita su una struttura dati separata .

Qualsiasi suggerimento/suggerimento su come analizzare il problema sarebbe ottimo.

Alcune statistiche varie: cachegrind mi dice che ci sono meno errori di istruzioni/errori di cache per l'approccio a doppio-indiretto, ma più errori di dati/errori di cache. La differenza non è poi così grande, per entrambi.

Edit: Come richiesto, la struttura dei dati che mi riguarda con:

class Node { 
    ushort type; 
    union { 
     ushort axisID; 
     ushort childrenSize; 
    }; 
    union { 
     Model **models; 
     Node *rightChild; 
    }; 
    float leftPlane, rightPlane; 
    ... public methods and stuff ... 
} 

Io fondamentalmente cambia Model **models-Model *models, in tanto sono il tuffo velocità. La classe Model contiene un puntatore a due classi astratte, Shape e Material. Tutte le classi menzionate qui sono allocate in blocco, con l'eccezione di Material poiché al momento ne sto usando solo una.

Answer 1

La mia prima ipotesi è che si stia incontrando false-sharing. Se si hanno più thread sia la modifica della memoria nella stessa linea di cache, l'hardware passerà molto tempo a passare la proprietà della linea di cache tra i processori.

Answer 2

La cosa più importante che cerco è un'inizializzazione non corretta che rende i dati duplicati o ha dati condivisi impropri. Non è evidente nel codice ma è l'errore ovvio da fare quando si va da ** a *.

Answer 3

Un altro ha messo in dubbio se il rallentamento deriva dall'aggiunta indiretta aggiunta, o il cambiamento nel modo in cui si assegna lo struct Model. Poiché ora si assegnano le strutture Model come un'area di memoria contigua, è possibile che le strutture adiacenti possano condividere la stessa riga di cache. Se i tuoi thread stanno contemporaneamente accedendo alle strutture adiacenti, si contenderanno l'accesso. Un accesso in lettura si bloccherà per un ciclo di bus mentre si attende l'altro.

Che cos'è lo sizeof(class Model)? Potresti provare ad espanderlo con variabili dummy finché la classe non sarà la dimensione della tua linea cache.

Un'altra possibilità è che è stato modificato l'allineamento delle variabili membro a cui si sta accedendo. Se il tuo sizeof(class Model) non è un multiplo della dimensione della parola della tua macchina (ad es. 8-byte), allora una matrice di tali oggetti avrà alcuni membri allineati alla dimensione della parola e altri no. Il disallineamento causa il doppio recupero sul bus di memoria, poiché l'unità di lettura legge le parole della macchina da posizioni di memoria allineate e compone il valore indirizzato da questi due recuperi.