When comparing two variants of pointers—classic vs. shared_ptr—I was surprised by a significant increase of the running speed of the program. For testing 2D Delaunay incremental Insertion algorithm has been used.
Compiler settings:
VS 2010 (release) /O2 /MD /GL, W7 Prof, CPU 3.GHZ DualCore
Results:
shared_ptr (C++ 0x00):
N[points] t[sec]
100 000 6
200 000 11
300 000 16
900 000 36
Pointers:
N[points] t[sec]
100 000 0,5
200 000 1
300 000 2
900 000 4
Running time of the shared_ptr versions is approximately 10 times longer. Is this caused by the compiler settings or C++ 0x00 shared_ptr implementation is so slow?
VS2010 Profiler: For raw pointers about 60% of the time is spent by heuristic searching of the triangle containing inserted point (it is OK, it is a well-known fact). But for the shared_ptr version approx 58% of the time is spent using shared_ptr.reset() and only 10% is used for heuristic searching.
Testing code with raw pointers:
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;
}
Insert point procedure:
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." );
}
}
Testing code with shared_ptr:
Code was rewritten without any optimization...
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." );
}
}
Thanks for your help...
Edit
I replaced direct passing of all objects with alias passing &. Copy constructors are used less frequent then before.
Updated tables for shared_ptr
shared_ptr (C++ 0x00) old:
N[points] t[sec]
100 000 6
200 000 11
300 000 16
900 000 36
shared_ptr (C++ 0x00) new version:
N[points] t[sec]
100 000 2
200 000 5
300 000 9
900 000 24
There is a considerable improvement, but the shared_ptr version is still 4 times slower than raw pointer one. I am afraid that running speed of the program can not be significantly increased.