shared_ptr: horrible speed
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.
Solution 1:
shared_ptr are the most complicated type of pointer ever:
- Ref counting takes time
- Multiple allocation (there are 3 parts: the object, the counter, the deleter)
- A number of virtual methods (in the counter and the deleter) for type erasure
- Works among multiple threads (thus synchronization)
There are 2 ways to make them faster:
-
use
make_sharedto allocate them, because (unfortunately) the normal constructor allocates two different blocks: one for the object and one for the counter and deleter. -
don't copy them if you don't need to: methods should accept
shared_ptr<T> const&
But there are also many ways NOT to use them.
Looking at your code it looks like your doing a LOT of memory allocation, and I can't help but wonder if you couldn't find a better strategy. I must admit I didn't got the full figure, so I may be heading straight into a wall but...
Usually code is much simpler if you have an owner for each of the objects. Therefore, shared_ptr should be a last resort measure, employed when you can't get a single owner.
Anyway, we're comparing apples and oranges here, the original code is buggy. You take care of deleting the memory (good) but you forgot that these objects were also referenced from other points in the program e1->setNextEdge(e21) which now holds pointers to destructed objects (in a free'd memory zone). Therefore I guess that in case of exception you just wipe out the entire list ? (Or somehow bet on undefined behavior to play nice)
So it's hard to judge on performances since the former doesn't recover well from exceptions while the latter does.
Finally: Have you thought about using intrusive_ptr ? It could give you some boost (hehe) if you don't synchronize them (single thread) and you would avoid a lot of stuff performed by the shared_ptr as well as gain on locality of reference.
Solution 2:
I always recommend using std::shared_ptr<> instead of relying on manual memory life-time management. However, automatic lifetime management costs something but usually not significant.
In your case you noticed shared_ptr<> is significant and as some said you should make sure that you don't unnecessarily copies a shared pointer as that force an addref/release.
But there's another question in the background: Do you really need to rely on new/delete in the first place? new/delete uses malloc/free which are not tuned for allocations of small objects.
A library that helped me alot before is boost::object_pool.
At some stage I wanted to create graphs very fast. Nodes and edges are naturally dynamically allocated and I get two costs from doing that.
- malloc/free
- Memory lifetime management
boost:object_pool helps reduce both these costs at the costs of not being as general as malloc/free.
So as an example let's say we have a simple node like this:
struct node
{
node * left;
node * right;
};
So instead of allocation node with new I use boost::object_pool. But boost::object_pool also tracks all instance allocated with it so at the end of my calculation I destroyed object_pool and didn't need to track each node thus simplifying my code and improving the performance.
I did some performance testing (I wrote my own pool class just for fun but bool::object_pool should give the same performance or better).
10,000,000 nodes created and destroyed
- Plain new/delete: 2.5secs
- shared_ptr: 5secs
- boost::object_pool: 0.15secs
So if boost::object_pool works for you it might help reduce the memory allocation overhead significantly.