Menu
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.
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;
}
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." );
}
}
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...
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.
787
shared_ptr are noticeably slower than raw pointers. That's why they should only be used if you actually need shared ownership semantics. Otherwise, there are several other smart pointer types available. scoped_ptr and auto_ptr (C++03) or unique_ptr (C++0x) both have their uses.
In short: Use unique_ptr when you want a single pointer to an object that will be reclaimed when that single pointer is destroyed. Use shared_ptr when you want multiple pointers to the same resource.
An object referenced by the contained raw pointer will not be destroyed until reference count is greater than zero i.e. until all copies of shared_ptr have been deleted. So, we should use shared_ptr when we want to assign one raw pointer to multiple owners. // referring to the same managed object.
this function is deprecated as of C++17 because use_count is only an approximation in multi-threaded environment.
shared_ptr are the most complicated type of pointer ever:
There are 2 ways to make them faster:
make_shared to allocate them, because (unfortunately) the normal constructor allocates two different blocks: one for the object and one for the counter and deleter.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.
134
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.
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
So if boost::object_pool works for you it might help reduce the memory allocation overhead significantly.
31
By default, if you create your shared pointers the naïve way (i.e. shared_ptr<type> p( new type )) you incur two memory allocations, one for the actual object and an extra allocation for the reference count. You can avoid the extra allocation by making use of the make_shared template that will perform a single instantiation for both the object and the reference count and then in-place construct the object.
The rest of the extra costs are quite small compared with doubling the calls to malloc, like incrementing and decrementing the count (both atomic operations) and testing for deletion. If you can provide some code in how you are using the pointers/shared pointers you might get a better insight as to what is actually going on in the code.
35
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
