c++ - shared_ptr: velocidad horrible
performance compiler-construction (7)
Al comparar dos variantes de punteros, clásico vs. shared_ptr, me sorprendió un aumento significativo de la velocidad de ejecución del programa. Para probar el algoritmo de inserción incremental 2D Delaunay se ha utilizado.
Configuración del compilador:
VS 2010 (versión) / O2 / MD / GL, W7 Prof, CPU 3.GHZ DualCore
Resultados:
shared_ptr (C ++ 0x00):
N[points] t[sec]
100 000 6
200 000 11
300 000 16
900 000 36
Punteros:
N[points] t[sec]
100 000 0,5
200 000 1
300 000 2
900 000 4
El tiempo de ejecución de las versiones shared_ptr es aproximadamente 10 veces más largo. ¿Esto es causado por la configuración del compilador o la implementación de shared_ptr en C ++ 0x00 es tan lenta?
Perfilador VS2010: para los punteros sin procesar, aproximadamente el 60% del tiempo se invierte en la búsqueda heurística del triángulo que contiene el punto insertado (está bien, es un hecho bien conocido). Pero para la versión shared_ptr, aproximadamente el 58% del tiempo se invierte en shared_ptr.reset () y solo el 10% se usa para búsquedas heurísticas.
Código de prueba con punteros en bruto:
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 ) << " removed.";
// Are in triangulation more than three points
try
{
//There are at least 3 points
if ( 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;
}
Insertar procedimiento de punto:
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." );
}
}
Código de prueba con shared_ptr:
El código fue reescrito sin ninguna optimización ...
void DT2D::DTInsertPoint ( std::shared_ptr <Point2D> p, std::shared_ptr <HalfEdge> *e1, HalfEdgesList * half_edges_dt )
{
// One step of the Delaunay triangulation, incremental insertion by de Berg (2001)
short status = -1;
//Pointers
std::shared_ptr <HalfEdge> e31;
std::shared_ptr <HalfEdge> e21;
std::shared_ptr <HalfEdge> e12;
std::shared_ptr <HalfEdge> e32;
std::shared_ptr <HalfEdge> e23;
std::shared_ptr <HalfEdge> e13;
std::shared_ptr <HalfEdge> e53;
std::shared_ptr <HalfEdge> e44;
std::shared_ptr <HalfEdge> 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 <HalfEdge> e2((*e1 )->getNextEdge());
std::shared_ptr <HalfEdge> 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 <HalfEdge> e4 = ( *e1 )->getTwinEdge();
std::shared_ptr <HalfEdge> e5 = e4->getNextEdge();
std::shared_ptr <HalfEdge> 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." );
}
}
Gracias por tu ayuda...
Editar
Reemplazé el paso directo de todos los objetos con alias pasando &. Copia constructores se utilizan menos frecuentes que antes.
Tablas actualizadas para shared_ptr
shared_ptr (C ++ 0x00) antiguo:
N[points] t[sec]
100 000 6
200 000 11
300 000 16
900 000 36
shared_ptr (C ++ 0x00) nueva versión:
N[points] t[sec]
100 000 2
200 000 5
300 000 9
900 000 24
Hay una mejora considerable, pero la versión shared_ptr sigue siendo 4 veces más lenta que la del puntero en bruto. Me temo que la velocidad de ejecución del programa no se puede aumentar significativamente.
De forma predeterminada, si crea sus punteros compartidos de forma ingenua (es decir, shared_ptr<type> p( new type ) ) incurrirá en dos asignaciones de memoria, una para el objeto real y una asignación adicional para el recuento de referencia. Puede evitar la asignación adicional haciendo uso de la plantilla make_shared que realizará una única instanciación tanto para el objeto como para el recuento de referencia y luego construirá el objeto en el lugar.
El resto de los costos adicionales son bastante pequeños en comparación con duplicar las llamadas a malloc, como aumentar y disminuir el conteo (ambas operaciones atómicas) y probar la eliminación. Si puede proporcionar algún código sobre cómo está utilizando los punteros / punteros compartidos, puede obtener una mejor idea de lo que realmente está sucediendo en el código.
Es imposible responder a esto sin más datos. ¿Ha perfilado el código para identificar con precisión la fuente de la desaceleración en la versión shared_ptr? El uso del contenedor ciertamente agregará gastos generales, pero me sorprendería si lo hace 10 veces más lento.
VSTS tiene buenas herramientas de rendimiento que le atribuirán el uso de la CPU exactamente si puede ejecutar esto durante 30 segundos aproximadamente. Si no tiene acceso a VS Performance Tools u otro conjunto de herramientas de creación de perfiles, ejecute el código shared_ptr en el depurador y divídalo 10 o 15 veces para obtener una muestra de fuerza bruta de dónde está gastando todo su tiempo. Esto es sorprendente y contra intuitivamente efectivo, he encontrado.
[EDITAR] No pase su valor de shared_ptr en esa variante del código - use ref para const. Si esta función se llama mucho, esto tendrá un impacto medible.
Es lento porque usa instrucciones atómicas para operaciones de referencia inc / dec, por lo que es demasiado lento. Si realmente necesita GC en C ++, no use un RF RF ingenuo y use una estrategia RC más desarrollada, o rastree GC. http://www.hboehm.info/gc/ es bueno para no acelerar tareas críticas (pero mucho mejor que "punteros inteligentes" ingenuos RC).
Pruébelo en modo "liberar" y vea si obtiene puntos de referencia más cercanos. El modo de depuración tiende a activar muchas aserciones en el STL que ralentiza muchas cosas.
Siempre recomiendo usar std :: shared_ptr <> en lugar de confiar en la administración manual de la vida útil de la memoria. Sin embargo, la gestión automática de por vida cuesta algo, pero por lo general no es significativa.
En su caso, notó que shared_ptr <> es significativo y, como algunos dijeron, debería asegurarse de no copiar innecesariamente un puntero compartido, ya que eso fuerza una dirección / liberación.
Pero hay otra pregunta en segundo plano: ¿Realmente necesitas confiar en nuevo / eliminar en primer lugar? new / delete usa malloc / free, que no está optimizado para asignaciones de objetos pequeños.
Una biblioteca que me ayudó mucho antes es boost::object_pool .
En algún momento quise crear gráficos muy rápido. Los nodos y los bordes son naturalmente asignados dinámicamente y obtengo dos costos por hacer eso.
- malloc / libre
- Gestión de la duración de la memoria
boost: object_pool ayuda a reducir estos costos a costa de no ser tan general como malloc / free.
Entonces, como ejemplo, digamos que tenemos un nodo simple como este:
struct node
{
node * left;
node * right;
};
Así que en lugar de un nodo de asignación con el nuevo uso boost :: object_pool. Pero boost :: object_pool también rastrea todas las instancias asignadas con él, así que al final de mi cálculo destruí object_pool y no tuve que rastrear cada nodo, simplificando así mi código y mejorando el rendimiento.
Hice algunas pruebas de rendimiento (escribí mi propia clase de grupo solo por diversión, pero bool :: object_pool debería dar el mismo rendimiento o mejor).
10,000,000 nodos creados y destruidos
- Nuevo llano / borrar: 2.5secs
- shared_ptr: 5secs
- boost :: object_pool: 0.15secs
Por lo tanto, si boost :: object_pool funciona para usted, podría ayudar a reducir significativamente la sobrecarga de asignación de memoria.
shared_ptr es notablemente más lento que los punteros en bruto. Es por eso que solo deben usarse si realmente necesita semántica de propiedad compartida.
De lo contrario, hay varios otros tipos de punteros inteligentes disponibles. scoped_ptr y auto_ptr (C ++ 03) o unique_ptr (C ++ 0x) tienen sus usos. Y a menudo, la mejor solución es no usar un puntero de ningún tipo, y simplemente escribir su propia clase RAII.
Un shared_ptr tiene que shared_ptr / disminuir / leer el contador de referencia y, dependiendo de la implementación y la forma en que se ejemplifique, el contador de referencia puede asignarse por separado, lo que provoca posibles fallas en la memoria caché. Y tiene que acceder al contador de referencia atómicamente, lo que agrega una sobrecarga adicional.
shared_ptr es el tipo de puntero más complicado de todos:
- El conteo de ref lleva tiempo
- Asignación múltiple (hay 3 partes: el objeto, el contador, el eliminador)
- Un número de métodos virtuales (en el contador y el eliminador) para el borrado de tipo
- Funciona entre múltiples hilos (por lo tanto sincronización)
Hay 2 formas de hacerlos más rápidos:
- use
make_sharedpara asignarlos , porque (desafortunadamente) el constructor normal asigna dos bloques diferentes: uno para el objeto y otro para el contador y el borrado. - no los copie si no necesita: los métodos deben aceptar
shared_ptr<T> const&
Pero también hay muchas maneras de NO usarlos.
Mirando tu código parece que estás haciendo MUCHA asignación de memoria, y no puedo evitar preguntarme si no podrías encontrar una mejor estrategia. Debo admitir que no tengo la figura completa, por lo que puedo estar dirigiéndome directamente a una pared, pero ...
Por lo general, el código es mucho más simple si tiene un propietario para cada uno de los objetos. Por lo tanto, shared_ptr debe ser una medida de último recurso, utilizada cuando no puede obtener un único propietario.
De todos modos, aquí estamos comparando manzanas y naranjas, el código original tiene errores. Se encarga de deleting la memoria (buena) pero olvidó que también se hizo referencia a estos objetos desde otros puntos en el programa e1->setNextEdge(e21) que ahora contiene punteros a objetos destruidos (en una zona de memoria libre). Por lo tanto, supongo que en caso de excepción, ¿acaba de borrar toda la lista? (O de alguna manera apostar en un comportamiento indefinido para jugar bien)
Por lo tanto, es difícil juzgar las actuaciones, ya que las primeras no se recuperan bien de las excepciones, mientras que las últimas sí lo hacen.
Finalmente: ¿Has pensado en usar intrusive_ptr ? Podría darle algo de impulso (jeje) si no los sincroniza (subproceso único) y evitaría muchas cosas realizadas por el shared_ptr , así como la ganancia en la localidad de referencia.