title: shared_ptr: horrible speed
body: <p>When comparing two variants of pointers&mdash;classic vs. shared_ptr&mdash;I was surprised by a significant increase of the running speed of the program. For testing 2D Delaunay incremental Insertion algorithm has been used. </p>
  
  <p>Compiler settings:</p>
  
  <blockquote>
    <p>VS 2010 (release) /O2 /MD /GL, W7 Prof, CPU 3.GHZ DualCore</p>
  </blockquote>
  
  <p>Results: </p>
  
  <p>shared_ptr (C++ 0x00):</p>
  
  <pre><code>N[points]         t[sec]  
  100 000                6  
  200 000               11  
  300 000               16  
  900 000               36  
  </code></pre>
  
  <p>Pointers:</p>
  
  <pre><code>N[points]         t[sec]  
  100 000              0,5  
  200 000               1  
  300 000               2  
  900 000               4   
  </code></pre>
  
  <p>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?</p>
  
  <p>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.</p>
  
  <h3>Testing code with raw pointers:</h3>
  
  <pre><code>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-&gt;size();
  
      // Remove duplicit points
      nl-&gt;removeDuplicitPoints();
  
      // Get nodes count after deletion of duplicated points
      unsigned int nodes_count_after = nl-&gt;size();
  
      //Print info
      std::cout &lt;&lt; "&gt; Starting DT, please wait... ";
      std::cout &lt;&lt; nodes_count_after &lt;&lt; " points, " &lt;&lt; ( nodes_count_before - nodes_count_after ) &lt;&lt; " removed.";
  
      // Are in triangulation more than three points
      try
      {
              //There are at least 3 points
              if ( nodes_count_after &gt; 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 &lt; nodes_count_after; i++ )  // Jump over simplex
                      {
                              DTInsertPoint ( ( *nl ) [i], &amp;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 &lt;&lt; " Completed." &lt;&lt; std::endl;
      }
  </code></pre>
  
  <h3>Insert point procedure:</h3>
  
  <pre><code>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, &amp;status, *e1, 0 );
  
              if ( e1 != NULL )
              {
                      // Edges inside triangle lies the point
                      HalfEdge *e2 = ( *e1 )-&gt;getNextEdge();
                      HalfEdge *e3 = e2-&gt;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-&gt;getPoint(), e31, NULL );
                              ( *e1 )-&gt;setNextEdge ( e21 );
  
                              // Create second new triangle T2, twin edges set after creation
                              e12 = new HalfEdge ( p, e2, NULL );
                              e32 = new HalfEdge ( e3-&gt;getPoint(), e12, NULL );
                              e2-&gt;setNextEdge ( e32 );
  
                              // Create third new triangle T3, twin edges set after creation
                              e23 = new HalfEdge ( p, e3, NULL );
                              e13 = new HalfEdge ( ( *e1 )-&gt;getPoint(), e23, NULL );
                              e3-&gt;setNextEdge ( e13 );
  
                              // Set twin edges in T1, T2, T3
                              e12-&gt;setTwinEdge ( e21 );
                              e21-&gt;setTwinEdge ( e12 );
                              e13-&gt;setTwinEdge ( e31 );
                              e31-&gt;setTwinEdge ( e13 );
                              e23-&gt;setTwinEdge ( e32 );
                              e32-&gt;setTwinEdge ( e23 );
  
                              // Add new edges into list
                              half_edges_dt-&gt;push_back ( e21 );
                              half_edges_dt-&gt;push_back ( e12 );
                              half_edges_dt-&gt;push_back ( e31 );
                              half_edges_dt-&gt;push_back ( e13 );
                              half_edges_dt-&gt;push_back ( e32 );
                              half_edges_dt-&gt;push_back ( e23 );
  
                              // Legalize triangle T1
                              if ( ( *e1 )-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, *e1 );
                              }
  
                              // Legalize triangle T2
                              if ( e2-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e2 );
                              }
  
                              // Legalize triangle T3
                              if ( e3-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e3 );
                              }
                      }
  
                      // Point lies on the edge of the triangle
                      else if ( status == 2 )
                      {
                              // Find adjacent triangle
                              HalfEdge *e4 = ( *e1 )-&gt;getTwinEdge();
                              HalfEdge *e5 = e4-&gt;getNextEdge();
                              HalfEdge *e6 = e5-&gt;getNextEdge();
  
                              // Create first new triangle T1, twin edges set after creation
                              e21 = new HalfEdge ( p, e3, NULL );
                              ( *e1 )-&gt;setNextEdge ( e21 );
  
                              // Create second new triangle T2, OK
                              e12 = new HalfEdge ( p, e2, e4 );
                              e32 = new HalfEdge ( e3-&gt;getPoint(), e12, e21 );
                              e2-&gt;setNextEdge ( e32 );
  
                              // Create third new triangle T3, twin edges set after creation
                              e53 = new HalfEdge ( p, e6, NULL );
                              e4-&gt;setNextEdge ( e53 );
  
                              // Create fourth new triangle T4, OK
                              e44 = new HalfEdge ( p, e5, *e1 );
                              e63 = new HalfEdge ( e6-&gt;getPoint(), e44, e53 );
                              e5-&gt;setNextEdge ( e63 );
  
                              // Set twin edges in T1, T3
                              e21-&gt;setTwinEdge ( e32 );
                              ( *e1 )-&gt;setTwinEdge ( e44 );
                              e53-&gt;setTwinEdge ( e63 );
                              e4-&gt;setTwinEdge ( e12 );
  
                              // Add new edges into list
                              half_edges_dt-&gt;push_back ( e21 );
                              half_edges_dt-&gt;push_back ( e12 );
                              half_edges_dt-&gt;push_back ( e32 );
                              half_edges_dt-&gt;push_back ( e53 );
                              half_edges_dt-&gt;push_back ( e63 );
                              half_edges_dt-&gt;push_back ( e44 );
  
                              // Legalize triangle T1
                              if ( e3-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e3 );
                              }
  
                              // Legalize triangle T4
                              if ( e5-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e5 );
                              }
  
                              // Legalize triangle T3
                              if ( e6-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e6 );
                              }
  
                              // Legalize triangle T2
                              if ( e2-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e2 );
                              }
                      }
              }
      }
      //Throw exception
      catch ( std::bad_alloc &amp;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 &amp;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></pre>
  
  <h3>Testing code with shared_ptr:</h3>
  
  <p>Code was rewritten without any optimization...</p>
  
  <pre><code>void DT2D::DTInsertPoint ( std::shared_ptr &lt;Point2D&gt; p, std::shared_ptr &lt;HalfEdge&gt; *e1, HalfEdgesList * half_edges_dt )
  {
      // One step of the Delaunay triangulation, incremental insertion by de Berg (2001)
      short   status = -1;
  
      //Pointers
      std::shared_ptr &lt;HalfEdge&gt; e31;
      std::shared_ptr &lt;HalfEdge&gt; e21;
      std::shared_ptr &lt;HalfEdge&gt; e12;
      std::shared_ptr &lt;HalfEdge&gt; e32;
      std::shared_ptr &lt;HalfEdge&gt; e23;
      std::shared_ptr &lt;HalfEdge&gt; e13;
      std::shared_ptr &lt;HalfEdge&gt; e53;
      std::shared_ptr &lt;HalfEdge&gt; e44;
      std::shared_ptr &lt;HalfEdge&gt; e63;
  
      try
      {
              // Test, if point lies inside triangle
              *e1 = LawsonOrientedWalk::findTriangleWalk ( p, &amp;status, *e1, 0 );
  
              if ( e1 != NULL )
              {
                      // Edges inside triangle lies the point
                      std::shared_ptr &lt;HalfEdge&gt; e2((*e1 )-&gt;getNextEdge());
                      std::shared_ptr &lt;HalfEdge&gt; e3(e2-&gt;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-&gt;getPoint(), e31, NULL ));
                              ( *e1 )-&gt;setNextEdge ( e21 );
  
                              // Create second new triangle T2, twin edges set after creation
                              e12.reset( new HalfEdge ( p, e2, NULL ));
                              e32.reset( new HalfEdge ( e3-&gt;getPoint(), e12, NULL ));
                              e2-&gt;setNextEdge ( e32 );
  
                              // Create third new triangle T3, twin edges set after creation
                              e23.reset( new HalfEdge ( p, e3, NULL ));
                              e13.reset( new HalfEdge ( ( *e1 )-&gt;getPoint(), e23, NULL ));
                              e3-&gt;setNextEdge ( e13 );
  
                              // Set twin edges in T1, T2, T3
                              e12-&gt;setTwinEdge ( e21 );
                              e21-&gt;setTwinEdge ( e12 );
                              e13-&gt;setTwinEdge ( e31 );
                              e31-&gt;setTwinEdge ( e13 );
                              e23-&gt;setTwinEdge ( e32 );
                              e32-&gt;setTwinEdge ( e23 );
  
                              // Add new edges into list
                              half_edges_dt-&gt;push_back ( e21 );
                              half_edges_dt-&gt;push_back ( e12 );
                              half_edges_dt-&gt;push_back ( e31 );
                              half_edges_dt-&gt;push_back ( e13 );
                              half_edges_dt-&gt;push_back ( e32 );
                              half_edges_dt-&gt;push_back ( e23 );
  
                              // Legalize triangle T1
                              if ( ( *e1 )-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, *e1 );
                              }
  
                              // Legalize triangle T2
                              if ( e2-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e2 );
                              }
  
                              // Legalize triangle T3
                              if ( e3-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e3 );
                              }
                      }
  
                      // Point lies on the edge of the triangle
                      else if ( status == 2 )
                      {
                              // Find adjacent triangle
                              std::shared_ptr &lt;HalfEdge&gt; e4 = ( *e1 )-&gt;getTwinEdge();
                              std::shared_ptr &lt;HalfEdge&gt; e5 = e4-&gt;getNextEdge();
                              std::shared_ptr &lt;HalfEdge&gt; e6 = e5-&gt;getNextEdge();
  
                              // Create first new triangle T1, twin edges set after creation
                              e21.reset(new HalfEdge ( p, e3, NULL ));
                              ( *e1 )-&gt;setNextEdge ( e21 );
  
                              // Create second new triangle T2, OK
                              e12.reset(new HalfEdge ( p, e2, e4 ));
                              e32.reset(new HalfEdge ( e3-&gt;getPoint(), e12, e21 ));
                              e2-&gt;setNextEdge ( e32 );
  
                              // Create third new triangle T3, twin edges set after creation
                              e53.reset(new HalfEdge ( p, e6, NULL ));
                              e4-&gt;setNextEdge ( e53 );
  
                              // Create fourth new triangle T4, OK
                              e44.reset(new HalfEdge ( p, e5, *e1 ));
                              e63.reset(new HalfEdge ( e6-&gt;getPoint(), e44, e53 ));
                              e5-&gt;setNextEdge ( e63 );
  
                              // Set twin edges in T1, T3
                              e21-&gt;setTwinEdge ( e32 );
                              ( *e1 )-&gt;setTwinEdge ( e44 );
                              e53-&gt;setTwinEdge ( e63 );
                              e4-&gt;setTwinEdge ( e12 );
  
                              // Add new edges into list
                              half_edges_dt-&gt;push_back ( e21 );
                              half_edges_dt-&gt;push_back ( e12 );
                              half_edges_dt-&gt;push_back ( e32 );
                              half_edges_dt-&gt;push_back ( e53 );
                              half_edges_dt-&gt;push_back ( e63 );
                              half_edges_dt-&gt;push_back ( e44 );
  
                              // Legalize triangle T1
                              if ( e3-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e3 );
                              }
  
                              // Legalize triangle T4
                              if ( e5-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e5 );
                              }
  
                              // Legalize triangle T3
                              if ( e6-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e6 );
                              }
  
                              // Legalize triangle T2
                              if ( e2-&gt;getTwinEdge() != NULL )
                              {
                                      legalizeTriangle ( p, e2 );
                              }
                      }
              }
      }
      //Throw exception
      catch ( std::bad_alloc &amp;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 &amp;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></pre>
  
  <p>Thanks for your help...</p>
  
  <h3>Edit</h3>
  
  <p>I replaced direct passing of all objects with alias passing &amp;. Copy constructors are used less frequent then before.</p>
  
  <p>Updated tables for shared_ptr  </p>
  
  <p>shared_ptr (C++ 0x00) old:</p>
  
  <pre><code>N[points]         t[sec]     
  100 000                6   
  200 000               11   
  300 000               16    
  900 000               36   
  </code></pre>
  
  <p>shared_ptr (C++ 0x00) new version:</p>
  
  <pre><code>N[points]         t[sec]      
  100 000                2  
  200 000                5  
  300 000                9  
  900 000               24  
  </code></pre>
  
  <p>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.</p>