shared_ptr: velocità orribile

Quando ho confrontato due varianti di puntatori-classico vs. shared_ptr-Sono rimasto sorpreso da un significativo aumento della velocità di esecuzione del programma. Per testare l’algoritmo di inserimento incrementale 2D Delaunay è stato utilizzato.

Impostazioni del compilatore:

VS 2010 (versione) / O2 / MD / GL, W7 Prof, CPU 3.GHZ DualCore

risultati:

shared_ptr (C ++ 0x00):

N[points] t[sec] 100 000 6 200 000 11 300 000 16 900 000 36 

puntatori:

 N[points] t[sec] 100 000 0,5 200 000 1 300 000 2 900 000 4 

Il tempo di esecuzione delle versioni shared_ptr è circa 10 volte più lungo. Questo è causato dalle impostazioni del compilatore o l’implementazione shared_ptr di C ++ 0x00 è così lento?

VS2010 Profiler: per i puntatori grezzi, circa il 60% del tempo viene speso dalla ricerca euristica del triangolo contenente il punto inserito (è OK, è un fatto ben noto). Ma per la versione shared_ptr viene speso circa il 58% del tempo usando shared_ptr.reset () e solo il 10% viene utilizzato per la ricerca euristica.

Test del codice con puntatori grezzi:

 void DT2D::DT ( Node2DList *nl, HalfEdgesList *half_edges_dt, bool print ) { // Create 2D Delaunay triangulation using incremental insertion method unsigned int nodes_count_before = nl->size(); // Remove duplicit points nl->removeDuplicitPoints(); // Get nodes count after deletion of duplicated points unsigned int nodes_count_after = nl->size(); //Print info std::cout < Starting DT, please wait... "; std::cout << nodes_count_after << " points, " << ( nodes_count_before - nodes_count_after ) < 2 ) { // Create simplex triangle createSimplexTriangle ( nl, half_edges_dt ); // Increment nodes count nodes_count_after += 3; // Starting half edge using for searching HalfEdge *e_heuristic = ( *half_edges_dt ) [0]; // Insert all points into triangulation using incremental method for ( unsigned int i = 3; i < nodes_count_after; i++ ) // Jump over simplex { DTInsertPoint ( ( *nl ) [i], &e_heuristic, half_edges_dt ); } //Corect boundary triangles (swap edges in triangles adjacent to simplex triangles). //They are legal due to DT, but not creating the convex hull ) correctBoundaryTriangles ( nl, half_edges_dt ); // Remove triangles having simplex points removeSimplexTriangles ( nl, half_edges_dt ); } //Print results std::cout << " Completed." << std::endl; } 

Procedura del punto di inserimento:

 void DT2D::DTInsertPoint ( Point2D *p, HalfEdge **e1, HalfEdgesList *half_edges_dt ) { // One step of the Delaunay triangulation, incremental insertion by de Berg (2001) short status = -1; //Pointers HalfEdge *e31 = NULL; HalfEdge *e21 = NULL; HalfEdge *e12 = NULL; HalfEdge *e32 = NULL; HalfEdge *e23 = NULL; HalfEdge *e13 = NULL; HalfEdge *e53 = NULL; HalfEdge *e44 = NULL; HalfEdge *e63 = NULL; try { // Test, if point lies inside triangle *e1 = LawsonOrientedWalk::findTriangleWalk ( p, &status, *e1, 0 ); if ( e1 != NULL ) { // Edges inside triangle lies the point HalfEdge *e2 = ( *e1 )->getNextEdge(); HalfEdge *e3 = e2->getNextEdge(); // Point lies inside the triangle if ( status == 1 ) { // Create first new triangle T1, twin edges set after creation e31 = new HalfEdge ( p, *e1, NULL ); e21 = new HalfEdge ( e2->getPoint(), e31, NULL ); ( *e1 )->setNextEdge ( e21 ); // Create second new triangle T2, twin edges set after creation e12 = new HalfEdge ( p, e2, NULL ); e32 = new HalfEdge ( e3->getPoint(), e12, NULL ); e2->setNextEdge ( e32 ); // Create third new triangle T3, twin edges set after creation e23 = new HalfEdge ( p, e3, NULL ); e13 = new HalfEdge ( ( *e1 )->getPoint(), e23, NULL ); e3->setNextEdge ( e13 ); // Set twin edges in T1, T2, T3 e12->setTwinEdge ( e21 ); e21->setTwinEdge ( e12 ); e13->setTwinEdge ( e31 ); e31->setTwinEdge ( e13 ); e23->setTwinEdge ( e32 ); e32->setTwinEdge ( e23 ); // Add new edges into list half_edges_dt->push_back ( e21 ); half_edges_dt->push_back ( e12 ); half_edges_dt->push_back ( e31 ); half_edges_dt->push_back ( e13 ); half_edges_dt->push_back ( e32 ); half_edges_dt->push_back ( e23 ); // Legalize triangle T1 if ( ( *e1 )->getTwinEdge() != NULL ) { legalizeTriangle ( p, *e1 ); } // Legalize triangle T2 if ( e2->getTwinEdge() != NULL ) { legalizeTriangle ( p, e2 ); } // Legalize triangle T3 if ( e3->getTwinEdge() != NULL ) { legalizeTriangle ( p, e3 ); } } // Point lies on the edge of the triangle else if ( status == 2 ) { // Find adjacent triangle HalfEdge *e4 = ( *e1 )->getTwinEdge(); HalfEdge *e5 = e4->getNextEdge(); HalfEdge *e6 = e5->getNextEdge(); // Create first new triangle T1, twin edges set after creation e21 = new HalfEdge ( p, e3, NULL ); ( *e1 )->setNextEdge ( e21 ); // Create second new triangle T2, OK e12 = new HalfEdge ( p, e2, e4 ); e32 = new HalfEdge ( e3->getPoint(), e12, e21 ); e2->setNextEdge ( e32 ); // Create third new triangle T3, twin edges set after creation e53 = new HalfEdge ( p, e6, NULL ); e4->setNextEdge ( e53 ); // Create fourth new triangle T4, OK e44 = new HalfEdge ( p, e5, *e1 ); e63 = new HalfEdge ( e6->getPoint(), e44, e53 ); e5->setNextEdge ( e63 ); // Set twin edges in T1, T3 e21->setTwinEdge ( e32 ); ( *e1 )->setTwinEdge ( e44 ); e53->setTwinEdge ( e63 ); e4->setTwinEdge ( e12 ); // Add new edges into list half_edges_dt->push_back ( e21 ); half_edges_dt->push_back ( e12 ); half_edges_dt->push_back ( e32 ); half_edges_dt->push_back ( e53 ); half_edges_dt->push_back ( e63 ); half_edges_dt->push_back ( e44 ); // Legalize triangle T1 if ( e3->getTwinEdge() != NULL ) { legalizeTriangle ( p, e3 ); } // Legalize triangle T4 if ( e5->getTwinEdge() != NULL ) { legalizeTriangle ( p, e5 ); } // Legalize triangle T3 if ( e6->getTwinEdge() != NULL ) { legalizeTriangle ( p, e6 ); } // Legalize triangle T2 if ( e2->getTwinEdge() != NULL ) { legalizeTriangle ( p, e2 ); } } } } //Throw exception catch ( std::bad_alloc &e ) { //Free memory if ( e31 != NULL ) delete e31; if ( e21 != NULL ) delete e21; if ( e12 != NULL ) delete e12; if ( e32 != NULL ) delete e32; if ( e23 != NULL ) delete e23; if ( e13 != NULL ) delete e13; if ( e53 != NULL ) delete e53; if ( e44 != NULL ) delete e44; if ( e63 != NULL ) delete e63; //Throw exception throw ErrorBadAlloc ( "EErrorBadAlloc: ", "Delaunay triangulation: Can not create new triangles for inserted point p." ); } //Throw exception catch ( ErrorMathZeroDevision &e ) { //Free memory if ( e31 != NULL ) delete e31; if ( e21 != NULL ) delete e21; if ( e12 != NULL ) delete e12; if ( e32 != NULL ) delete e32; if ( e23 != NULL ) delete e23; if ( e13 != NULL ) delete e13; if ( e53 != NULL ) delete e53; if ( e44 != NULL ) delete e44; if ( e63 != NULL ) delete e63; //Throw exception throw ErrorBadAlloc ( "EErrorMathZeroDevision: ", "Delaunay triangulation: Can not create new triangles for inserted point p." ); } } 

Test del codice con shared_ptr:

Il codice è stato riscritto senza alcuna ottimizzazione …

 void DT2D::DTInsertPoint ( std::shared_ptr  p, std::shared_ptr  *e1, HalfEdgesList * half_edges_dt ) { // One step of the Delaunay triangulation, incremental insertion by de Berg (2001) short status = -1; //Pointers std::shared_ptr  e31; std::shared_ptr  e21; std::shared_ptr  e12; std::shared_ptr  e32; std::shared_ptr  e23; std::shared_ptr  e13; std::shared_ptr  e53; std::shared_ptr  e44; std::shared_ptr  e63; try { // Test, if point lies inside triangle *e1 = LawsonOrientedWalk::findTriangleWalk ( p, &status, *e1, 0 ); if ( e1 != NULL ) { // Edges inside triangle lies the point std::shared_ptr  e2((*e1 )->getNextEdge()); std::shared_ptr  e3(e2->getNextEdge()); // Point lies inside the triangle if ( status == 1 ) { // Create first new triangle T1, twin edges set after creation e31.reset( new HalfEdge ( p, *e1, NULL )); e21.reset( new HalfEdge ( e2->getPoint(), e31, NULL )); ( *e1 )->setNextEdge ( e21 ); // Create second new triangle T2, twin edges set after creation e12.reset( new HalfEdge ( p, e2, NULL )); e32.reset( new HalfEdge ( e3->getPoint(), e12, NULL )); e2->setNextEdge ( e32 ); // Create third new triangle T3, twin edges set after creation e23.reset( new HalfEdge ( p, e3, NULL )); e13.reset( new HalfEdge ( ( *e1 )->getPoint(), e23, NULL )); e3->setNextEdge ( e13 ); // Set twin edges in T1, T2, T3 e12->setTwinEdge ( e21 ); e21->setTwinEdge ( e12 ); e13->setTwinEdge ( e31 ); e31->setTwinEdge ( e13 ); e23->setTwinEdge ( e32 ); e32->setTwinEdge ( e23 ); // Add new edges into list half_edges_dt->push_back ( e21 ); half_edges_dt->push_back ( e12 ); half_edges_dt->push_back ( e31 ); half_edges_dt->push_back ( e13 ); half_edges_dt->push_back ( e32 ); half_edges_dt->push_back ( e23 ); // Legalize triangle T1 if ( ( *e1 )->getTwinEdge() != NULL ) { legalizeTriangle ( p, *e1 ); } // Legalize triangle T2 if ( e2->getTwinEdge() != NULL ) { legalizeTriangle ( p, e2 ); } // Legalize triangle T3 if ( e3->getTwinEdge() != NULL ) { legalizeTriangle ( p, e3 ); } } // Point lies on the edge of the triangle else if ( status == 2 ) { // Find adjacent triangle std::shared_ptr  e4 = ( *e1 )->getTwinEdge(); std::shared_ptr  e5 = e4->getNextEdge(); std::shared_ptr  e6 = e5->getNextEdge(); // Create first new triangle T1, twin edges set after creation e21.reset(new HalfEdge ( p, e3, NULL )); ( *e1 )->setNextEdge ( e21 ); // Create second new triangle T2, OK e12.reset(new HalfEdge ( p, e2, e4 )); e32.reset(new HalfEdge ( e3->getPoint(), e12, e21 )); e2->setNextEdge ( e32 ); // Create third new triangle T3, twin edges set after creation e53.reset(new HalfEdge ( p, e6, NULL )); e4->setNextEdge ( e53 ); // Create fourth new triangle T4, OK e44.reset(new HalfEdge ( p, e5, *e1 )); e63.reset(new HalfEdge ( e6->getPoint(), e44, e53 )); e5->setNextEdge ( e63 ); // Set twin edges in T1, T3 e21->setTwinEdge ( e32 ); ( *e1 )->setTwinEdge ( e44 ); e53->setTwinEdge ( e63 ); e4->setTwinEdge ( e12 ); // Add new edges into list half_edges_dt->push_back ( e21 ); half_edges_dt->push_back ( e12 ); half_edges_dt->push_back ( e32 ); half_edges_dt->push_back ( e53 ); half_edges_dt->push_back ( e63 ); half_edges_dt->push_back ( e44 ); // Legalize triangle T1 if ( e3->getTwinEdge() != NULL ) { legalizeTriangle ( p, e3 ); } // Legalize triangle T4 if ( e5->getTwinEdge() != NULL ) { legalizeTriangle ( p, e5 ); } // Legalize triangle T3 if ( e6->getTwinEdge() != NULL ) { legalizeTriangle ( p, e6 ); } // Legalize triangle T2 if ( e2->getTwinEdge() != NULL ) { legalizeTriangle ( p, e2 ); } } } } //Throw exception catch ( std::bad_alloc &e ) { /* //Free memory if ( e31 != NULL ) delete e31; if ( e21 != NULL ) delete e21; if ( e12 != NULL ) delete e12; if ( e32 != NULL ) delete e32; if ( e23 != NULL ) delete e23; if ( e13 != NULL ) delete e13; if ( e53 != NULL ) delete e53; if ( e44 != NULL ) delete e44; if ( e63 != NULL ) delete e63; */ //Throw exception throw ErrorBadAlloc ( "EErrorBadAlloc: ", "Delaunay triangulation: Can not create new triangles for inserted point p." ); } //Throw exception catch ( ErrorMathZeroDevision &e ) { /* //Free memory if ( e31 != NULL ) delete e31; if ( e21 != NULL ) delete e21; if ( e12 != NULL ) delete e12; if ( e32 != NULL ) delete e32; if ( e23 != NULL ) delete e23; if ( e13 != NULL ) delete e13; if ( e53 != NULL ) delete e53; if ( e44 != NULL ) delete e44; if ( e63 != NULL ) delete e63; */ //Throw exception throw ErrorBadAlloc ( "EErrorMathZeroDevision: ", "Delaunay triangulation: Can not create new triangles for inserted point p." ); } } 

Grazie per l’aiuto…

modificare

Ho sostituito il passaggio diretto di tutti gli oggetti con l’alias che passa &. I costruttori di copia vengono utilizzati meno frequentemente di prima.

Tabelle aggiornate per shared_ptr

shared_ptr (C ++ 0x00) vecchio:

 N[points] t[sec] 100 000 6 200 000 11 300 000 16 900 000 36 

shared_ptr (C ++ 0x00) nuova versione:

 N[points] t[sec] 100 000 2 200 000 5 300 000 9 900 000 24 

C’è un notevole miglioramento, ma la versione shared_ptr è ancora 4 volte più lenta del puntatore raw uno. Temo che la velocità di esecuzione del programma non possa essere aumentata in modo significativo.

shared_ptr è il tipo di puntatore più complicato di sempre:

  • Il conteggio dei riferimenti richiede tempo
  • Assegnazione multipla (ci sono 3 parti: l’object, il contatore, il deleter)
  • Un certo numero di metodi virtuali (nel contatore e deleter) per la cancellazione dei tipi
  • Funziona tra più thread (quindi sincronizzazione)

Ci sono 2 modi per renderli più veloci:

  • usa make_shared per allocarli , perché (sfortunatamente) il costruttore normale assegna due blocchi diversi: uno per l’object e uno per il contatore e il deleter.
  • non copiarli se non è necessario: i metodi devono accettare shared_ptr const&

Ma ci sono anche molti modi per NON usarli.

Guardando il tuo codice sembra che tu stia facendo un sacco di allocazione di memoria, e non posso fare a meno di chiedermi se non potresti trovare una strategia migliore. Devo ammettere che non ho ottenuto la cifra completa, quindi potrei essere diretto verso un muro ma …

Di solito il codice è molto più semplice se si dispone di un proprietario per ciascuno degli oggetti. Pertanto, shared_ptr dovrebbe essere una misura di ultima istanza, utilizzata quando non è ansible ottenere un singolo proprietario.

In ogni caso, stiamo confrontando mele e arance qui, il codice originale è bacato. Ti occupi di deleting la memoria (buona) ma hai dimenticato che questi oggetti sono stati referenziati anche da altri punti del programma e1->setNextEdge(e21) che ora contiene puntatori agli oggetti destrutturati (in una zona di memoria libera). Quindi suppongo che in caso di eccezione si cancelli l’intero elenco? (O in qualche modo scommetti su un comportamento indefinito per giocare bene)

Quindi è difficile giudicare le prestazioni dal momento che il primo non si riprende bene dalle eccezioni, mentre il secondo lo fa.

Finalmente: hai pensato di usare intrusive_ptr ? Potrebbe darti un po ‘di spinta (hehe) se non li sincronizzi (thread singolo) e eviterai un sacco di cose eseguite da shared_ptr così come guadagni sulla località di riferimento.

Raccomando sempre l’uso di std :: shared_ptr <> invece di affidarsi alla gestione manuale della durata della memoria. Tuttavia, la gestione automatica a vita costa qualcosa ma solitamente non è significativa.

Nel tuo caso hai notato che shared_ptr <> è significativo e come alcuni hanno detto che dovresti assicurarti di non copiare inutilmente un puntatore condiviso come forzare un addref / release.

Ma c’è un’altra domanda sullo sfondo: hai davvero bisogno di fare affidamento su new / delete in primo luogo? new / delete usa malloc / free che non sono ottimizzati per allocazioni di piccoli oggetti.

Una libreria che mi ha aiutato molto prima è boost :: object_pool .

Ad un certo punto volevo creare grafici molto velocemente. Nodi e spigoli sono allocati dynamicmente in modo naturale e ottengo due costi dal farlo.

  1. malloc / gratuito
  2. Gestione della memoria

boost: object_pool aiuta a ridurre entrambi questi costi a spese di non essere generale come malloc / free.

Quindi, ad esempio, diciamo che abbiamo un nodo semplice come questo:

  struct node { node * left; node * right; }; 

Quindi, al posto del nodo di allocazione con new, utilizzo boost :: object_pool. Ma boost :: object_pool tiene traccia di tutte le istanze allocate con esso così alla fine del mio calcolo ho distrutto object_pool e non ho bisogno di tracciare ogni nodo, semplificando così il mio codice e migliorando le prestazioni.

Ho fatto alcuni test delle prestazioni (ho scritto la mia class di piscina solo per divertimento ma bool :: object_pool dovrebbe dare la stessa performance o meglio).

10.000.000 nodes creati e distrutti

  1. Plain new / delete: 2.5secs
  2. shared_ptr: 5secs
  3. boost :: object_pool: 0.15secs

Quindi, se boost :: object_pool funziona per te, potrebbe aiutare a ridurre in modo significativo l’overhead di allocazione della memoria.

Per impostazione predefinita, se si creano i puntatori condivisi in modo ingenuo (ad esempio shared_ptr p( new type ) ) si incorre in due allocazioni di memoria, una per l’object effettivo e un’allocazione aggiuntiva per il conteggio dei riferimenti. È ansible evitare l’allocazione extra facendo uso del modello make_shared che eseguirà una singola istanziazione per l’object e il conteggio dei riferimenti e quindi costruirà l’object sul posto.

Il resto dei costi aggiuntivi è piuttosto ridotto rispetto al raddoppio delle chiamate a malloc, come l’incremento e la diminuzione del conteggio (entrambe le operazioni atomiche) e il test per la cancellazione. Se puoi fornire del codice su come stai usando i puntatori / i puntatori condivisi, potresti ottenere una visione migliore di ciò che sta effettivamente accadendo nel codice.

Provalo in modalità “rilascio” e verifica se ottieni parametri di riferimento più ravvicinati. La modalità di debug tende ad triggersre molte asserzioni nell’STL che rallentano molte cose.

shared_ptr sono notevolmente più lenti dei puntatori grezzi. Ecco perché dovrebbero essere usati solo se hai effettivamente bisogno di semantica della proprietà condivisa.

In caso contrario, sono disponibili altri tipi di puntatori intelligenti. scoped_ptr e auto_ptr (C ++ 03) o unique_ptr (C ++ 0x) hanno entrambi i loro usi. E spesso, la soluzione migliore è non usare un puntatore di alcun tipo, e invece scrivere semplicemente la tua class RAII.

A shared_ptr deve incrementare / decrementare / leggere il contatore di riferimento e, a seconda dell’implementazione e del modo in cui viene istanziato, il contatore ref può essere assegnato separatamente, causando potenziali errori di cache. E deve accedere al contatore ref atomicamente, che aggiunge ulteriore overhead.

È imansible rispondere a questo senza più dati. Hai profilato il codice per identificare con precisione l’origine del rallentamento nella versione shared_ptr? L’utilizzo del contenitore aggiungerà sicuramente un sovraccarico, ma sarei sorpreso se lo rende 10 volte più lento.

VSTS ha degli strumenti perf perfetti che attribuiscono l’utilizzo della CPU esattamente se è ansible eseguirlo per 30 secondi circa. Se non si ha accesso a VS Performance Tools o ad altri strumenti di profiling, quindi eseguire il codice shared_ptr nel debugger e interromperlo 10 o 15 volte per ottenere un campione di forza bruta su dove sta spendendo tutto il suo tempo. Questo è sorprendentemente e intuitivamente efficace, ho trovato.

[EDIT] Non passare il tuo shared_ptr di valore in quella variante del codice – usa ref to const. Se questa funzione viene chiamata molto, questo avrà un impatto misurabile.

È lento perché usa le istruzioni atomiche di riferimento per operazioni inc / dec, quindi è molto lento. Se hai davvero bisogno di GC in C ++, non utilizzare il GC RF ingenuo e utilizzare una strategia RC più sviluppata o tracciare GC. http://www.hboehm.info/gc/ è utile per non velocizzare le attività critiche (ma molto meglio dei “puntatori intelligenti” naive RC).