shared_ptr: ужасная скорость

Question

При сравнении двух вариантов указателей - классический и shared_ptr - я был удивлен значительным увеличением скорости работы программы.Для тестирования 2D был использован алгоритм инкрементной вставки Делоне.

Настройки компилятора:

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% времени тратится на эвристический поиск треугольника, содержащего вставленную точку (это нормально,это общеизвестный факт).Но для версии 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;
    }

Процедура вставки точки:

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

Тестирование кода с 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." );
    }
}

Спасибо за вашу помощь ...

Редактировать

Я заменил прямое прохождение всех объектов псевдонимом прохождения &.Конструкторы копирования используются реже, чем раньше.

Обновлены таблицы для 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 раза медленнее, чем версия с указателем raw.Боюсь, что скорость работы программы не может быть существенно увеличена.

Answer 1

shared_ptr - самый сложный тип указателя за всю историю:

• Подсчет ссылок занимает время
• Многократное выделение (есть 3 части: объект, счетчик, средство удаления)
• Количество виртуальных методов (в счетчике и в средствах удаления) для стирания типа
• Работает между несколькими потоками (таким образом, синхронизация)

Существует 2 способачтобы сделать их быстрее:

• используйте make_shared для их выделения , потому что (к сожалению) нормальный конструктор выделяет два разных блока: один для объектаи один для счетчика и удалителя.
• не копируйте их , если вам не нужно: методы должны принимать shared_ptr<T> const&

Но естьЕсть также много способов НЕ использовать их.

Глядя на ваш код, вы выглядите так, как будто вы делаете МНОГО выделения памяти, и я не могу не задаться вопросом, не смогли ли вы найти лучшую стратегию.Я должен признать, что я не получил полную цифру, поэтому я могу идти прямо к стене, но ...

Обычно код гораздо проще, если у вас есть владелец для каждого из объектов.Поэтому shared_ptr должен быть последним средством, используемым, когда вы не можете найти единственного владельца.

В любом случае, мы сравниваем яблоки и апельсины здесь, оригинальный код содержит ошибки.Вы позаботились о deleting памяти (хорошо), но вы забыли, что на эти объекты также ссылались из других точек программы e1->setNextEdge(e21), которая теперь содержит указатели на разрушенные объекты (в зоне свободной памяти).Поэтому я предполагаю, что в случае исключения вы просто уничтожите весь список?(Или как-то сделать ставку на неопределенное поведение, чтобы хорошо играть)

Так что трудно судить по выступлениям, так как первое плохо восстанавливается после исключений, а второе -

Наконец: Вы подумалипо поводу использования intrusive_ptr ?Это может дать вам некоторый прирост (хе-хе), если вы не синхронизируете их (однопотоковый), и вы избежите большого количества вещей, выполняемых shared_ptr, а также выиграете в ссылочной локации.

Answer 2

Я всегда рекомендую использовать std :: shared_ptr <> вместо того, чтобы полагаться на ручное управление временем жизни памяти.Однако автоматическое управление временем жизни стоит чего-то, но, как правило, незначительно.

В вашем случае вы заметили, что shared_ptr <> имеет значение, и, как некоторые говорили, вы должны убедиться, что вы не копируете общий указатель без необходимости, так как это вызываетaddref / release.

Но есть еще один вопрос на заднем плане: вам действительно нужно полагаться на new / delete в первую очередь?new / delete использует malloc / free, которые не настроены для размещения небольших объектов.

Библиотека, которая мне очень помогла раньше, это boost :: object_pool .

На каком-то этапе я хотел очень быстро создавать графики.Узлы и ребра распределяются естественным образом динамически, и я получаю за это две затраты.

1. malloc / free
2. Управление временем жизни памяти

boost: object_pool помогаетсократить обе эти затраты за счет того, что они не будут такими общими, как malloc / free.

Итак, в качестве примера, скажем, у нас есть простой узел, подобный этому:

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

Таким образом, вместо выделенияузел с новым я использую boost :: object_pool.Но boost :: object_pool также отслеживает все экземпляры, выделенные для него, поэтому в конце своих вычислений я уничтожил object_pool и мне не нужно было отслеживать каждый узел, упрощая мой код и повышая производительность.

Я немного повысил производительностьтестирование (я написал свой собственный класс пула просто для удовольствия, но bool :: object_pool должен дать ту же производительность или лучше).

10 000 000 созданных и уничтоженных узлов

1. Plain new / delete:2.5secs
2. shared_ptr: 5secs
3. boost :: object_pool: 0.15secs

Так что, если boost :: object_pool работает для вас, это может помочь уменьшить накладные расходы на выделение памятизначительно.

Answer 3

По умолчанию, если вы создаете ваши общие указатели наивным способом (то есть shared_ptr<type> p( new type )), вы получаете два выделения памяти, одно для реального объекта и дополнительное выделение для счетчика ссылок.Вы можете избежать дополнительного выделения, воспользовавшись шаблоном make_shared, который будет выполнять единую реализацию как для объекта, так и для счетчика ссылок, а затем создавать объект на месте.

Остальные дополнительные расходыдовольно малы по сравнению с удвоением количества вызовов malloc, таких как увеличение и уменьшение количества (как атомарных операций), так и тестирование на удаление.Если вы можете предоставить некоторый код того, как вы используете указатели / общие указатели, вы можете лучше понять, что на самом деле происходит в коде.

Answer 4

Попробуйте в режиме «релиз» и посмотрите, приблизитесь ли вы к тестам.Режим отладки имеет тенденцию включать множество утверждений в STL, что замедляет многие вещи.

Answer 5

shared_ptr заметно медленнее, чем необработанные указатели.Вот почему их следует использовать только в том случае, если вам действительно нужна семантика совместного владения.

В противном случае доступно несколько других типов интеллектуальных указателей.scoped_ptr и auto_ptr (C ++ 03) или unique_ptr (C ++ 0x) оба имеют свое применение.И часто лучшее решение - не использовать какой-либо указатель, а вместо этого просто написать собственный класс RAII.Реализация и способ ее создания, счетчик ссылок может быть выделен отдельно, что может привести к потенциальным потерям кэша.И он должен обращаться к счетчику ссылок атомарно, что добавляет дополнительные издержки.

Answer 6

Невозможно ответить на это без дополнительных данных.Вы профилировали код, чтобы точно определить источник замедления в версии shared_ptr?Использование контейнера, безусловно, увеличит накладные расходы, но я был бы удивлен, если он сделает его в 10 раз медленнее

В VSTS есть отличные инструменты для перфорирования, которые точно приписывают использование процессора, если вы можете запустить его в течение 30 секунд или около того.Если у вас нет доступа к VS Performance Tools или другому набору инструментов профилирования, запустите код shared_ptr в отладчике и разбейте его 10 или 15 раз, чтобы получить пример грубой силы, где он все время проводит.Я обнаружил, что это удивительно и нелогично.

[EDIT] Не передавайте ваш shared_ptr по значению в этом варианте кода - используйте ref для const.Если эта функция будет вызываться много раз, это будет иметь измеримое влияние.

Answer 7

Это медленно, потому что он использует для справочных операций inc / dec атомарные инструкции, таким образом, это очень медленно.Если вам действительно нужен GC в C ++, не используйте наивный RF GC и используйте более развитую стратегию RC или отслеживание GC.http://www.hboehm.info/gc/ хорош для задач, не критичных к скорости (но намного лучше, чем наивные умные указатели).