shared_ptr:可怕的速度

Question

shared_ptr:可怕的速度

Ian*_*Ian 49 c++ compiler-construction performance shared-ptr

当比较两个指针变体 - 经典与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

Run Code Online (Sandbox Code Playgroud)

指针:

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

Run Code Online (Sandbox Code Playgroud)

shared_ptr版本的运行时间大约是其10倍.这是由编译器设置引起的还是C++ 0x00 shared_ptr实现那么慢？

VS2010 Profiler:对于原始指针,大约60%的时间花费在启发式搜索包含插入点的三角形上(这是一个众所周知的事实).但是对于shared_ptr版本,大约58%的时间花在使用shared_ptr.reset()上,只有10%用于启发式搜索.

使用原始指针测试代码:

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;
    }

Run Code Online (Sandbox Code Playgroud)

插入点程序:

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." );
    }
}

Run Code Online (Sandbox Code Playgroud)

使用shared_ptr测试代码:

代码被重写而没有任何优化......

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." );
    }
}

Run Code Online (Sandbox Code Playgroud)

谢谢你的帮助...

编辑

我用别名传递&替换了所有对象的直接传递.复制构造函数的使用频率低于之前.

已更新shared_ptr的表

shared_ptr(C++ 0x00)old:

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

Run Code Online (Sandbox Code Playgroud)

shared_ptr(C++ 0x00)新版本:

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

Run Code Online (Sandbox Code Playgroud)

有一个相当大的改进,但shared_ptr版本仍然比原始指针1慢4倍.我担心程序的运行速度不能显着提高.

Answer 1

Mat*_* M. 75

shared_ptr 是有史以来最复杂的指针类型:

引用计数需要时间
多次分配(有3个部分:对象,计数器,删除器)
用于类型擦除的许多虚拟方法(在计数器和删除器中)
在多个线程之间工作(因此同步)

有两种方法可以让它们更快:

用于 make_shared 分配它们,因为(不幸的是)普通构造函数分配了两个不同的块:一个用于对象,一个用于计数器和删除器.
如果您不需要,请不要复制它们:方法应该接受shared_ptr<T> const&

但是也有很多方法不使用它们.

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

如果您拥有每个对象的所有者,通常代码会更简单.因此,shared_ptr应该是最后的手段,当你无法获得单一所有者时使用.

无论如何,我们在这里比较苹果和橘子,原始代码是错误的.你需要处理deleting内存(好),但是你忘了这些对象也是从程序中的其他点引用的,这些点e1->setNextEdge(e21)现在保存了对被破坏对象的指针(在free'd内存区域中).因此,我想如果出现异常,你只需要清除整个列表？(或以某种方式押注未定义的行为以发挥不错)

所以很难判断表现,因为前者不能从异常中恢复,而后者则是如此.

最后:您是否考虑过使用intrusive_ptr？它可以给你一些提升(呵呵),如果你不同步它们(单线程),你会避免很多东西执行,shared_ptr以及获得引用的位置.

Answer 2

Jus*_*mer 21

我总是建议使用std :: shared_ptr <>而不是依赖于手动内存生命周期管理.但是,自动终身管理会花费一些成本,但通常并不重要

在您的情况下,您注意到shared_ptr <>是重要的,并且正如一些人所说,您应该确保不会不必要地复制共享指针,因为强制addref/release.

但是在后台还有另一个问题:你真的需要首先依赖新/删除吗？new/delete使用malloc/free,它们没有针对小对象的分配进行调整.

之前帮助过我的库是boost :: object_pool.

在某些阶段,我想快速创建图表.节点和边缘自然是动态分配的,我这样做会产生两个成本.

的malloc /免费
内存生存期管理

boost:object_pool有助于降低这些成本,但代价是不像malloc/free那样通用.

举个例子,假设我们有一个这样的简单节点:

   struct node
   {
      node * left;
      node * right;
   };

Run Code Online (Sandbox Code Playgroud)

因此,使用boost :: object_pool代替使用new的分配节点.但是boost :: object_pool也会跟踪用它分配的所有实例,所以在计算结束时我销毁了object_pool,不需要跟踪每个节点,从而简化了我的代码并提高了性能.

我做了一些性能测试(我编写自己的池类只是为了好玩,但bool :: object_pool应该提供相同的性能或更好).

创建和销毁10,000,000个节点

普通新/删除:2.5秒
shared_ptr:5secs
boost :: object_pool:0.15secs

因此,如果boost :: object_pool适用于您,则可能有助于显着降低内存分配开销.

Answer 3

Dav*_*eas 12

默认情况下,如果以天真的方式创建共享指针(即shared_ptr<type> p( new type )),则会产生两个内存分配,一个用于实际对象,另一个用于引用计数.您可以通过使用make_shared将对对象和引用计数执行单个实例化的模板来避免额外分配,然后就地构造对象.

与对malloc的调用加倍相比,其余的额外成本非常小,例如递增和递减计数(两个原子操作)和测试删除.如果您可以提供有关如何使用指针/共享指针的一些代码,那么您可以更好地了解代码中实际发生的情况.

Answer 4

Ken*_*mon 8

在"发布"模式下尝试它,看看你是否接近基准测试.调试模式倾向于在STL中打开许多断言,这会使许多事情变慢.

@dirkgently - 迭代器调试帮助我捕获了很多错误.我喜欢.如果性能太差,你可以随时关闭它! (4认同)
/ MD暗示这已经是发布模式./ MDd将是Debug.我同意在Debug中进行分析会浪费时间,但这似乎并非如此.http://msdn.microsoft.com/en-us/library/2kzt1wy3(VS.80).aspx (2认同)

Answer 5

jal*_*alf 6

shared_ptr 是明显比原始指针慢.这就是为什么只有在你真正需要共享所有权语义时才应该使用它们.

否则,还有其他几种智能指针类型可用.scoped_ptr和auto_ptr(C++ 03)或unique_ptr(C++ 0x)都有它们的用途.通常,最好的解决方案是不使用任何类型的指针,而只是编写自己的RAII类.

A shared_ptr必须递增/递减/读取参考计数器,并且取决于实现以及如何实例化,ref计数器可以被单独分配,从而导致潜在的高速缓存未命中.它必须以原子方式访问ref计数器,这会增加额外的开销.

归档时间：	15 年前
查看次数：	32454 次
最近记录：	9 年，8 月前