std :: vector vs normal array

Question

Sto creando un programma che deve essere ultraveloce. Sta eseguendo alcune cose sulla GPU usando CUDA e successivamente esegue alcuni calcoli sulla CPU. Per questo, ho bisogno di convertire la struttura della GPU altamente ottimizzata in qualcosa che posso facilmente utilizzare sulla CPU. I miei dati sono fondamentalmente un grafico disposto in una griglia. Attualmente sto usando std :: vector per la parte CPU. Perché so che c'è piuttosto un overhead se faccio un sacco di push_back() s ed io almeno so perché so quanti vertici ho nel mio grafico, io uso il seguente codice per questo:

new_graph.resize(blockSize * blockSize); 
for (unsigned long long y = 0; y < blockSize; y++) { 
    for (unsigned long long x = 0; x < blockSize; x++) { 
     int idx = y * blockSize + x; 
     new_graph[idx] = Vertex(x, y); 
    } 
} 

Successivamente Aggiungo i bordi Purtroppo non so quanti spigoli per vertice ho, ma so che non sarà mai più grande di 8. Pertanto I reserve() 8 in ogni std :: vector che uso per i bordi.

Tuttavia, entrambi sembrano essere estremamente lenti. Se io uso un array normale per il grafico stesso (in pratica sostituendo lo std :: vector esterno), il miglioramento della velocità in quella parte è enorme (come 10x circa).

Per il grafico questo è fattibile, ma per i bordi non proprio, perché faccio alcuni post-procesing su questi bordi e per questo ho davvero bisogno di qualcosa come std :: vector che è un pò dinamico (aggiungo alcuni bordi) .

Attualmente la conversione dei dati in std :: vector è qualcosa come 10 volte più lento di eseguire il mio algoritmo sulla GPU (che è un algoritmo MST intelligente). Questo non è proprio quello che voglio, perché ora il sovraccarico è troppo grande.

Qualcuno sa cosa sta succedendo o come posso risolvere questo problema?

p.s. Compilo con -O2, perché ho già scoperto che ciò può fare una grande differenza. Anche provato con -O3, nessuna vera differenza.

Vertex è definito come segue:

struct Pos { 
    int x, y; 
    Pos() { 
     x = 0; 
     y = 0; 
    } 

    Pos(int x, int y) { 
     this->x = x; 
     this->y = y; 
    } 
}; 

struct Vertex { 
    Pos pos; 
    bool hidden; 
    unsigned long long newIdx; 
    Vertex() { 
     this->pos = Pos(); 
     this->hidden = false; 
     this->numEdges = 0; 
     this->numRemovedEdges = 0; 
    } 

    Vertex(Pos &pos) { 
     this->pos = pos; 
     this->hidden = false; 
     this->numEdges = 0; 
     this->numRemovedEdges = 0; 
    } 

    Vertex(int x, int y) { 
     this->pos = Pos(x, y); 
     this->hidden = false; 
     this->numEdges = 0; 
     this->numRemovedEdges = 0; 
    } 
    int numEdges; 
    int numRemovedEdges; 
    std::vector<Edge> edges; 
    std::vector<bool> removed; 
    std::vector<bool> doNotWrite; 
}; 

Answer 1

Forse stai pagando per un'allocazione di memoria dinamica che lo vector riserva lo spazio per i suoi elementi?

Anche se si reserve in modo ottimale, avrete almeno 3 allocazioni di memoria per ogni Vertex (uno per edges, uno per removed e uno per doNotWrite). L'allocazione dinamica della memoria è potenzialmente costosa rispetto alle cose ad alte prestazioni che stai cercando di fare qui.

O utilizzare semplici vecchi array che sono garantiti per essere sufficientemente grandi (spazio potenzialmente inutile) o un allocatore di memoria specializzato insieme a vector, adattato alle proprie esigenze specifiche.

---

Inoltre, si accede agli elementi nell'ordine di memoria? Il tuo esempio sembra suggerire di sì, ma lo fai in tutti i casi?

---

Inoltre, hai bisogno anche di Vertex.pos? Non può essere dedotto dalla posizione di Vertex nella griglia?

Answer 2

Non riesci a creare un oggetto Vertex, memcpy i valori X e Y in esso (in modo che non si deve chiamare il costruttore per ogni ciclo) , quindi memcpy l'intero vertice nel tuo std :: vector? La memoria del vettore è garantita come un normale array, quindi puoi bypassare tutta l'astrazione e manipolare direttamente la memoria. Non c'è bisogno di cose complicate. Inoltre, forse puoi impaginare i dati che torni dalla GPU in modo da poter memcpare interi blocchi in una sola volta, facendoti risparmiare ancora di più.

Answer 3

C'è un'altra soluzione che ho usato di recente in una situazione simile. Nel pacchetto llvm c'è la classe SmallVector. Fornisce un'interfaccia abbastanza simile a std :: vector, ma consente di mantenere in linea alcuni numeri fissi di elementi (quindi, a meno che il vettore non superi il limite iniziale, non si verificano ulteriori allocazioni di memoria). Se SmallVector prova a crescere oltre le dimensioni iniziali, viene assegnato un blocco di memoria e tutti gli elementi vengono spostati lì, il tutto in un unico passaggio trasparente.

Poche cose che ho dovuto risolvere il problema in questo SmallVector:

1. minor numero di elementi che potrebbe essere messo sul posto è 2, in modo che quando 1 articolo è utilizzato in es 99,99% dei casi v'è un bel testa
2. uso abituale di swap() per liberare memoria (SmallVector(). Swap (vec)) non memoria libera, così ho dovuto implementare io stesso

Basta guardare per l'ultima versione di llvm per il codice sorgente della classe SmallVector

Answer 4

La struttura dati della CPU è estremamente inefficiente a causa del numero di allocazioni di memoria dinamica, operazioni di assegnazione non necessarie e dimensione complessiva di ciascun vertice. Prima di considerare l'ottimizzazione di questa struttura, sarebbe opportuno comprendere il flusso di dati tra le strutture di dati della CPU e le strutture dati della GPU poiché la conversione tra i due formati richiederà molto tempo. Questo fa sorgere la domanda, perché la struttura della GPU non è utilizzata dal lato CPU?

Se si guardava solo dal lato CPU e si desidera mantenere una struttura dati AoS, quindi 1. Semplificare la struttura dei dati Vertex. 2. Rimuovere tutta l'allocazione della memoria dinamica. Ogni vettore std :: fa un dinamo 3. Sostituisci rimosso e doNotWrite a std :: bitset < 8>. 4. Rimuovere numRemoveEdges. Questo è removed.count(). 5. Se Edge è piccolo, è possibile trovarlo più velocemente per dichiarare i bordi del bordo [8]. 6. Se si decide di rimanere con il vettore, prendere in considerazione l'utilizzo di un allocatore di pool. 7. Riordinare gli elementi di dati in Vertice per dimensione per ridurre la dimensione di Vertice.

Tutte queste raccomandazioni non sono probabilmente la soluzione migliore per condividere i dati con una GPU. Se si utilizza un pool allocator e si utilizza UVA (CUDA Linux), è sufficiente copiare i dati nella GPU con una singola copia di memoria.