shared_ptr：可怕的速度 [英] shared_ptr: horrible speed

问题描述

当比较指针的两个变体时— classic和shared_ptr—我感到惊讶的是程序的运行速度的显着增加。为了测试，使用了2D Delaunay增量插入算法。

编译器设置：

VS 2010（发布版）/ O2 / MD / GL，W7 Prof，CPU 3.GHZ DualCore

结果：

shared_ptr（C ++ 0x00）：

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

指针：

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

shared_ptr版本的运行时间约为10倍。这是由于编译器设置还是由于C ++ 0x00 shared_ptr的实现是如此慢？

VS2010 Profiler：对于原始指针，大约60％的时间是通过启发式搜索三角形包含插入点（它是OK，这是一个众所周知的事实）。但对于shared_ptr版本，大约58％的时间花费在使用shared_ptr.reset（），只有10％用于启发式搜索。

用原始指针测试代码：

  void DT2D :: DT（Node2DList * nl，HalfEdgesList * half_edges_dt，bool print）
 {
 //使用增量插入方法创建2D Delaunay三角剖分
 unsigned int nodes_count_before = nl-> size（）; 
 
 //删除重复点
 nl-> removeDuplicitPoints（）; 
 
 //删除重复点后获取节点数
 unsigned int nodes_count_after = nl-> size（）; 
 
 //打印信息
 std :: cout< >启动DT，请稍候...; 
 std :: cout<< nodes_count_after<< 点，< （nodes_count_before  -  nodes_count_after）<< removed。 
 
 //三角化三点以上
 try 
 {
 //至少有3分
 if（nodes_count_after> 2） 
 {
 //创建单纯形三角形
 createSimplexTriangle（nl，half_edges_dt）; 
 
 //增量节点数
 nodes_count_after + = 3; 
 
 //用于搜索的起始半边
 HalfEdge * e_heuristic =（* half_edges_dt）[0]; 
 
 //使用增量方法将所有点插入三角形
 for（unsigned int i = 3; i  {
 DTInsertPoint（（* nl）[i]，&e_euristic，half_edges_dt）; 
} 
 
 // Corect边界三角形（与单纯形三角形相邻的三角形中的交换边）。 
 //它们是合法的，因为DT，但不创建凸包）
 correctBoundaryTriangles（nl，half_edges_dt）; 
 
 //删除具有单点的三角形
 removeSimplexTriangles（nl，half_edges_dt）; 
} 
 
 //打印结果
 std :: cout< 完成。 << std :: endl; 
} 
  

插入点程序：

  void DT2D :: DTInsertPoint（Point2D * p，HalfEdge ** e1，HalfEdgesList * half_edges_dt）
 {
 // Delaunay三角剖分的一步插入by de Berg（2001）
 short status = -1; 
 
 //指针
 HalfEdge * e31 = NULL; 
 HalfEdge * e21 = NULL; 
 HalfEdge * e12 = NULL; 
 HalfEdge * e32 = NULL; 
 HalfEdge * e23 = NULL; 
 HalfEdge * e13 = NULL; 
 HalfEdge * e53 = NULL; 
 HalfEdge * e44 = NULL; 
 HalfEedge * e63 = NULL; 
 
 try 
 {
 //测试，如果点在三角形内
 * e1 = LawsonOrientedWalk :: findTriangleWalk（p，& status，* e1，0） ; 
 
 if（e1！= NULL）
 {
 //三角形内的边为点
 HalfEdge * e2 =（* e1） - > getNextEdge ; 
 HalfEdge * e3 = e2-> getNextEdge（）; 
 
 //点在三角形内
 if（status == 1）
 {
 //创建第一个新的三角形T1，创建后设置双边缘
 e31 = new HalfEdge（p，* e1，NULL）; 
 e21 = new HalfEdge（e2-> getPoint（），e31，NULL）; 
（* e1） - > setNextEdge（e21）; 
 
 //创建第二个新的三角形T2，创建后的双边集
 e12 = new HalfEdge（p，e2，NULL）; 
 e32 = new HalfEdge（e3-> getPoint（），e12，NULL）; 
 e2-> setNextEdge（e32）; 
 
 //创建第三个新三角形T3，创建后创建双边缘
 e23 = new HalfEdge（p，e3，NULL）; 
 e13 = new HalfEdge（（* e1） - > getPoint（），e23，NULL）; 
 e3-> setNextEdge（e13）; 
 
 //在T1，T2，T3中设置双边缘
 e12-> setTwinEdge（e21）; 
 e21-> setTwinEdge（e12）; 
 e13-> setTwinEdge（e31）; 
 e31-> setTwinEdge（e13）; 
 e23-> setTwinEdge（e32）; 
 e32-> setTwinEdge（e23）; 
 
 //将新的边添加到列表
 half_edges_dt-> push_back（e21）; 
 half_edges_dt-> push_back（e12）; 
 half_edges_dt-> push_back（e31）; 
 half_edges_dt->推回（e13）; 
 half_edges_dt-> push_back（e32）; 
 half_edges_dt-> push_back（e23）; 
 
 //合法化三角形T1 
 if（（* e1） - > getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，* e1）; 
} 
 
 //合法化三角形T2 
 if（e2-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e2） ; 
} 
 
 //合法化三角形T3 
 if（e3-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e3） ; 
} 
} 
 
 //点位于三角形的边缘
 else if（status == 2）
 {
 / /找到相邻的三角形
 HalfEdge * e4 =（* e1） - > getTwinEdge（）; 
 HalfEdge * e5 = e4-> getNextEdge（）; 
 HalfEdge * e6 = e5-> getNextEdge（）; 
 
 //创建第一个新的三角形T1，创建后双边集合
 e21 = new HalfEdge（p，e3，NULL）; 
（* e1） - > setNextEdge（e21）; 
 
 //创建第二个新的三角形T2，OK 
 e12 = new HalfEdge（p，e2，e4）; 
 e32 = new HalfEdge（e3-> getPoint（），e12，e21）; 
 e2-> setNextEdge（e32）; 
 
 //创建第三个新的三角形T3，创建后的双边集
 e53 = new HalfEdge（p，e6，NULL）; 
 e4-> setNextEdge（e53）; 
 
 //创建第四个新三角形T4，OK 
 e44 = new HalfEdge（p，e5，* e1）; 
 e63 = new HalfEdge（e6-> getPoint（），e44，e53）; 
 e5-> setNextEdge（e63）; 
 
 //在T1，T3中设置双边缘
 e21-> setTwinEdge（e32）; 
（* e1） - > setTwinEdge（e44）; 
 e53-> setTwinEdge（e63）; 
 e4-> setTwinEdge（e12）; 
 
 //将新边添加到列表
 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）; 
 
 //合法化三角形T1 
 if（e3-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e3）; 
} 
 
 //合法化三角形T4 
 if（e5-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e5） ; 
} 
 
 //合法化三角形T3 
 if（e6-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e6） ; 
} 
 
 //合法化三角形T2 
 if（e2-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e2） ; 
} 
} 
} 
} 
 //抛出异常
 catch（std :: bad_alloc& e）
 {
 //可用内存
 if（e31！= NULL）delete e31; 
 if（e21！= NULL）remove 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 ErrorBadAlloc（EErrorBadAlloc：，Delaunay triangulation：无法为插入的点p创建新的三角形。 
} 
 
 //抛出异常
 catch（ErrorMathZeroDevision& e）
 {
 //可用内存
 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 ErrorBadAlloc（EErrorMathZeroDevision：，Delaunay triangulation：无法为插入的点p创建新的三角形。 
} 
} 
  

使用shared_ptr测试代码：

无需任何优化即可重写代码

  void DT2D :: DTInsertPoint（std： ：shared_ptr< Point2D> p，std :: shared_ptr< HalfEdge> * e1，HalfEdgesList * half_edges_dt）
 {
 // Delaunay三角剖分的一步，de Berg b $ b short status = -1; 
 
 //指针
 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 
 {
 //测试，如果点在三角形内
 * e1 = LawsonOrientedWalk :: findTriangleWalk（p，& status，* e1，0） ; 
 
 if（e1！= NULL）
 {
 //三角形内的边为点
 std :: shared_ptr< HalfEdge> e2（（* e1） - > getNextEdge（））; 
 std :: shared_ptr< HalfEdge> e3（e2-> getNextEdge（））; 
 
 //点在三角形内
 if（status == 1）
 {
 //创建第一个新的三角形T1，创建后设置双边缘
 e31.reset（new HalfEdge（p，* e1，NULL））; 
 e21.reset（new HalfEdge（e2-> getPoint（），e31，NULL））; 
（* e1） - > setNextEdge（e21）; 
 
 //创建第二个新的三角形T2，创建后创建双边缘
 e12.reset（new HalfEdge（p，e2，NULL））; 
 e32.reset（new HalfEdge（e3-> getPoint（），e12，NULL））; 
 e2-> setNextEdge（e32）; 
 
 //创建第三个新的三角形T3，创建后的双边集合
 e23.reset（new HalfEdge（p，e3，NULL））; 
 e13.reset（new HalfEdge（（* e1） - > getPoint（），e23，NULL））; 
 e3-> setNextEdge（e13）; 
 
 //在T1，T2，T3中设置双边缘
 e12-> setTwinEdge（e21）; 
 e21-> setTwinEdge（e12）; 
 e13-> setTwinEdge（e31）; 
 e31-> setTwinEdge（e13）; 
 e23-> setTwinEdge（e32）; 
 e32-> setTwinEdge（e23）; 
 
 //将新边添加到列表
 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）; 
 
 //合法化三角形T1 
 if（（* e1） - > getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，* e1）; 
} 
 
 //合法化三角形T2 
 if（e2-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e2） ; 
} 
 
 //合法化三角形T3 
 if（e3-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p， ; 
} 
} 
 
 //点位于三角形的边缘
 else if（status == 2）
 {
 / /找到相邻的三角形
 std :: shared_ptr< HalfEdge> e4 =（* e1） - > getTwinEdge（）; 
 std :: shared_ptr< HalfEdge> e5 = e4-> getNextEdge（）; 
 std :: shared_ptr< HalfEdge> e6 = e5-> getNextEdge（）; 
 
 //创建第一个新的三角形T1，创建后的双边集合
 e21.reset（new HalfEdge（p，e3，NULL））; 
（* e1） - > setNextEdge（e21）; 
 
 //创建第二个新的三角形T2，OK 
 e12.reset（new HalfEdge（p，e2，e4））; 
 e32.reset（new HalfEdge（e3-> getPoint（），e12，e21））; 
 e2-> setNextEdge（e32）; 
 
 //创建第三个新三角形T3，创建后创建双边缘
 e53.reset（new HalfEdge（p，e6，NULL））; 
 e4-> setNextEdge（e53）; 
 
 //创建第四个新三角形T4，OK 
 e44.reset（new HalfEdge（p，e5，* e1））; 
 e63.reset（new HalfEdge（e6-> getPoint（），e44，e53））; 
 e5-> setNextEdge（e63）; 
 
 //在T1，T3中设置双边缘
 e21-> setTwinEdge（e32）; 
（* e1） - > setTwinEdge（e44）; 
 e53-> setTwinEdge（e63）; 
 e4-> setTwinEdge（e12）; 
 
 //将新边添加到列表
 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）; 
 
 //合法化三角形T1 
 if（e3-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e3）; 
} 
 
 //合法化三角形T4 
 if（e5-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e5） ; 
} 
 
 //合法化三角形T3 
 if（e6-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e6） ; 
} 
 
 //合法化三角形T2 
 if（e2-> getTwinEdge（）！= NULL）
 {
 legalizeTriangle（p，e2） ; 
} 
} 
} 
} 
 //抛出异常
 catch（std :: bad_alloc& e）
 {
 / * 
 //可用内存
 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）删除e53; 
 if（e44！= NULL）delete e44; 
 if（e63！= NULL）delete e63; 
 * / 
 //抛出异常
 throw ErrorBadAlloc（EErrorBadAlloc：，Delaunay triangulation：无法为插入的点p创建新的三角形。 
} 
 
 //抛出异常
 catch（ErrorMathZeroDevision& e）
 {
 / * 
 //可用内存
 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 ErrorBadAlloc（EErrorMathZeroDevision：，Delaunay triangulation：无法为插入的点p创建新的三角形。 
} 
} 
  

感谢您的帮助...

编辑

我替换了直接传递所有对象的别名传递&

更新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）新版本：

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

有相当大的改进，但shared_ptr版本仍然是4倍慢于原始指针一。恐怕程序的运行速度不能显着提高。

解决方案

shared_ptr 是最复杂的指针类型：

• 参考计数需要时间


• 多个分配（有3个部分：对象，计数器，删除者）


• 类型擦除的多个虚拟方法（在计数器和删除器中）


• 在多个主题之间同步（因此同步）

有两种方法可以使它们更快：

• 使用 make_shared 因为（不幸的是）正常构造函数分配了两个不同的块：一个用于对象，一个用于计数器和删除器。


• 't需要：方法应该接受 shared_ptr< T> const&

但也有许多方法不能使用它们。

看看你的代码看起来像你做了大量的内存分配，我不禁想知道你是否找不到一个更好的策略。我必须承认我没有得到完整的数字，所以我可能直接进入墙，但...

通常代码是更简单，如果你有一个所有者为每个对象。因此， shared_ptr 应该是最后的措施，当您无法获得单个所有者时。

，我们在这里比较苹果和橘子，原来的代码是buggy。你注意删除内存（好），但你忘了这些对象也被引用从程序中的其他点 e1-> setNextEdge e21），它现在包含指向被破坏对象的指针（在一个空闲的内存区域）。因此，我想在例外情况下，你只是擦掉整个列表？ （或以某种方式打赌未定义的行为玩得不错）

因此，很难判断性能，因为前者不能从异常恢复良好，而后者。 p>

最后：您是否想过使用 intrusive_ptr ？如果你不同步它们（单线程），它可以给你一些提升（hehe），你会避免很多由 shared_ptr 执行的东西，以及获得参考地点。

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.

解决方案

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_shared to 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.

这篇关于shared_ptr：可怕的速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！