Shared_ptr: ужасная скорость ⇐ C++

Программы на C++. Форум разработчиков
Anonymous
Shared_ptr: ужасная скорость

Сообщение Anonymous »

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

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


VS 2010 (выпуск) /O2 /MD / GL, W7 Prof, процессор DualCore 3,ГГц


Результаты:

общий_ptr (С++ 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 раз дольше. Это вызвано настройками компилятора или реализация общего_ptr C++ 0x00 такая медленная?

Профилировщик VS2010: для необработанных указателей около 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 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 
 p, std::shared_ptr  *e1, HalfEdgesList * half_edges_dt )
{
// One step of the Delaunay triangulation, incremental insertion by de Berg (2001)
short   status = -1;

//Pointers
std::shared_ptr  e31;
std::shared_ptr  e21;
std::shared_ptr  e12;
std::shared_ptr  e32;
std::shared_ptr  e23;
std::shared_ptr  e13;
std::shared_ptr  e53;
std::shared_ptr  e44;
std::shared_ptr   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  e2((*e1 )->getNextEdge());
std::shared_ptr  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  e4 = ( *e1 )->getTwinEdge();
std::shared_ptr  e5 = e4->getNextEdge();
std::shared_ptr   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) старая версия:

Код: Выделить всё

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

Подробнее здесь: https://stackoverflow.com/questions/362 ... ible-speed
Вернуться к началу

Вернуться в «C++»