ti-enxame.com

shared_ptr: velocidade horrível

Ao comparar duas variantes de ponteiros - classic vs. shared_ptr - fiquei surpreso com um aumento significativo da velocidade de execução do programa. Para testar o algoritmo de inserção incremental 2D Delaunay, foi utilizado.

Configurações do compilador:

VS 2010 (versão)/O2/MD/GL, Prof W7, CPU 3.GHZ DualCore

Resultados:

shared_ptr (C++ 0x00):

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

Ponteiros:

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

O tempo de execução das versões shared_ptr é aproximadamente 10 vezes maior. Isso é causado pelas configurações do compilador ou a implementação do C++ 0x00 shared_ptr é tão lenta?

Profiler VS2010: Para ponteiros brutos, cerca de 60% do tempo é gasto pela pesquisa heurística do triângulo que contém o ponto inserido (tudo bem, é um fato bem conhecido). Mas para a versão shared_ptr, aproximadamente 58% do tempo é gasto usando shared_ptr.reset () e apenas 10% é usado para pesquisa heurística.

Teste de código com ponteiros brutos:

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

Inserir procedimento de ponto:

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

Testando código com shared_ptr:

O código foi reescrito sem qualquer otimização ...

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

Obrigado pela ajuda...

Editar

Substituí a passagem direta de todos os objetos por alias passando &. Os construtores de cópia são usados ​​com menos frequência do que antes.

Tabelas atualizadas para shared_ptr

shared_ptr (C++ 0x00) antigo:

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

shared_ptr (C++ 0x00) nova versão:

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

Há uma melhoria considerável, mas a versão shared_ptr ainda é 4 vezes mais lenta que a do ponteiro bruto. Receio que a velocidade de execução do programa não possa ser significativamente aumentada.

48
Ian

shared_ptr É o tipo de ponteiro mais complicado que nunca:

  • A contagem de referências leva tempo
  • Alocação múltipla (existem três partes: o objeto, o contador, o deleter)
  • Vários métodos virtuais (no contador e no deleter) para apagamento de tipo
  • Funciona entre vários threads (portanto, sincronização)

Existem 2 maneiras de torná-los mais rápidos:

  • use make_shared para alocá-los , porque (infelizmente ) o construtor normal aloca dois blocos diferentes: um para o objeto e outro para o contador e o deleter.
  • não os copie se você não precisar: os métodos devem aceitar shared_ptr<T> const&

Mas também existem muitas maneiras de NÃO usá-las.

Olhando para o seu código, parece que você está fazendo muita alocação de memória, e não posso deixar de pensar se você não conseguiu encontrar uma estratégia melhor. Devo admitir que não entendi tudo, então posso estar indo direto para uma parede, mas ...

Normalmente, o código é muito mais simples se você tiver um proprietário para cada um dos objetos. Portanto, shared_ptr Deve ser uma medida de último recurso, usada quando você não pode obter um único proprietário.

Enfim, estamos comparando maçãs e laranjas aqui, o código original é de buggy. Você cuida de deleting a memória (boa), mas esqueceu que esses objetos também foram referenciados de outros pontos do programa e1->setNextEdge(e21) que agora contém ponteiros para objetos destruídos (de forma livre) zona de memória). Portanto, acho que, em caso de exceção, você acaba com a lista inteira? (Ou de alguma forma, aposte em um comportamento indefinido para jogar no Nice)

Portanto, é difícil julgar as performances, já que o primeiro não se recupera bem das exceções, enquanto o segundo o faz.

Finalmente: Você já pensou em usar intrusive_ptr ? Isso poderia lhe dar algum impulso (hehe) se você não os sincronizar (thread único) e evitasse muitas coisas executadas pelo shared_ptr, Além de obter ganhos na localidade de referência.

75
Matthieu M.

Eu sempre recomendo usar std :: shared_ptr <> em vez de confiar no gerenciamento manual da vida útil da memória. No entanto, o gerenciamento automático da vida útil custa algo, mas geralmente não é significativo.

No seu caso, você percebeu que shared_ptr <> é significativo e, como alguns disseram, deve-se garantir que não copie desnecessariamente um ponteiro compartilhado, pois isso força um addref/release.

Mas há outra questão em segundo plano: você realmente precisa confiar em novo/excluir em primeiro lugar? new/delete usa malloc/free que não são ajustados para alocações de objetos pequenos.

Uma biblioteca que me ajudou muito antes é boost :: object_pool .

Em algum momento, eu queria criar gráficos muito rapidamente. Nós e arestas são naturalmente alocados dinamicamente e eu recebo dois custos disso.

  1. malloc/grátis
  2. Gerenciamento da vida útil da memória

boost: object_pool ajuda a reduzir esses dois custos com o custo de não ser tão geral quanto o malloc/free.

Então, como exemplo, digamos que temos um nó simples como este:

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

Então, em vez de nó de alocação com o novo eu uso boost :: object_pool. Mas o boost :: object_pool também rastreia todas as instâncias alocadas com ele, portanto, no final do meu cálculo, destruí object_pool e não precisava rastrear cada nó, simplificando meu código e melhorando o desempenho.

Fiz alguns testes de desempenho (escrevi minha própria classe de pool apenas por diversão, mas bool :: object_pool deve fornecer o mesmo desempenho ou melhor).

10.000.000 de nós criados e destruídos

  1. Nova planície/exclusão: 2,5 segundos
  2. shared_ptr: 5seg
  3. boost :: object_pool: 0.15secs

Portanto, se boost :: object_pool funcionar para você, isso poderá ajudar a reduzir significativamente a sobrecarga da alocação de memória.

21

Por padrão, se você criar seus ponteiros compartilhados da maneira ingênua (ou seja, shared_ptr<type> p( new type )), ocorrerá duas alocações de memória, uma para o objeto real e uma alocação extra para a contagem de referência. Você pode evitar a alocação extra usando o make_shared modelo que executará uma única instanciação para o objeto e a contagem de referência e depois construirá o objeto no local.

O restante dos custos extras é bem pequeno comparado à duplicação das chamadas para malloc, como aumentar e diminuir a contagem (ambas as operações atômicas) e testar a exclusão. Se você puder fornecer algum código sobre como usar os ponteiros/ponteiros compartilhados, poderá ter uma ideia melhor do que realmente está acontecendo no código.

12

Experimente no modo "release" e veja se você se aproxima dos benchmarks. O modo de depuração tende a ativar muitas asserções no STL, o que atrasa muitas coisas.

7
Ken Simon

shared_ptrsão notavelmente mais lentos que os ponteiros brutos. É por isso que eles só devem ser usados ​​se você realmente precisar semântica de propriedade compartilhada.

Caso contrário, existem vários outros tipos de ponteiros inteligentes disponíveis. scoped_ptr e auto_ptr (C++ 03) ou unique_ptr (C++ 0x) ambos têm seus usos. E, freqüentemente, a melhor solução é não usar um ponteiro de nenhum tipo e apenas escrever sua própria classe RAII.

UMA shared_ptr precisa incrementar/diminuir/ler o contador de referência e, dependendo da implementação e de como é instanciado, o contador ref pode ser alocado separadamente, causando possíveis falhas de cache. E ele precisa acessar o contador ref atomicamente, o que adiciona sobrecarga adicional.

6
jalf

É impossível responder a isso sem mais dados. Você definiu o perfil do código para identificar com precisão a origem da desaceleração na versão shared_ptr? Usar o contêiner certamente aumentará a sobrecarga, mas eu ficaria surpreso se o tornasse 10x mais lento.

O VSTS possui boas ferramentas de desempenho que atribuirão o uso da CPU exatamente se você puder executar isso por 30 segundos ou mais. Se você não tiver acesso ao VS Performance Tools ou a outro conjunto de ferramentas de criação de perfil, execute o código shared_ptr no depurador e o penetre 10 ou 15 vezes para obter uma amostra de força bruta de onde está gastando todo o tempo. Isso é surpreendentemente e contra-intuitivamente eficaz, eu descobri.

[EDIT] Não passe seu shared_ptr por valor nessa variante do código - use ref para const. Se essa função for chamada muito, isso terá um impacto mensurável.

2
Steve Townsend

É lento porque usa como referência as instruções atômicas das operações inc/dec, portanto, é lento na hora. Se você realmente precisa de GC em C++, não use GC ingênuo RF GC e use alguma estratégia de RC mais desenvolvida ou rastreamento de GC. http://www.hboehm.info/ gc / é bom por não acelerar tarefas críticas (mas muito melhor que o RC ingênuo de "ponteiros inteligentes").

1
dev1223