|
Boost Users : |
Subject: [Boost-users] [BGL] Very slow adjacency_list deallocation/reallocation for debug builds
From: T MacAdam (nsdevelop12_at_[hidden])
Date: 2010-02-23 14:27:27
Does anyone know a way to speed up adjacency_list deallocation for debug builds? I've done some timing tests (see code below - should build as-is in VC9) and found the adjacency_list creates quite quickly, but is terrible during deallocation (actually, it can be as bad on creation of the graph, too, if you are building up the graph incrementally using a vecS for your vertex storage that requires reallocation as the size grows). In a release build, everything is blazing fast, but it's so slow when linked against the debug CRT that I essentially cannot debug my app. And the graph doesn't have to be too big (see code below, 50K results in a deallocation time of 171 sec if I use vecS and 268 sec if I use listS, and that's on a quite good workstation; my production graphs are > 100K vertices). BTW, I'm building with Visual C++ 9 (2008).
#include <time.h>
#include <iostream>
#include <algorithm>
#include <boost/graph/adjacency_list.hpp>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
const int size = 50000;
//typedef boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS > MyGraphType; // try storing vertices in vector<>
typedef boost::adjacency_list< boost::listS, boost::listS, boost::bidirectionalS > MyGraphType; // try storing vertices in list<>
typedef boost::graph_traits< MyGraphType >::vertex_descriptor MyVertexDescriptor;
typedef boost::graph_traits< MyGraphType >::edge_descriptor MyEdgeDescriptor;
MyGraphType *myGraph = new MyGraphType();
vector<MyVertexDescriptor> vertices(size);
{
cout << "Adding vertices...Started:" << endl;
clock_t m_clockStart = ::clock();
for( int i = 0; i < size; ++i )
vertices[i] = boost::add_vertex(*myGraph);
cout << "Adding vertices...Done: " << (double)((::clock()-m_clockStart)/CLOCKS_PER_SEC) << " seconds" << endl;
}
{
cout << "Adding edges...Started:" << endl;
clock_t m_clockStart = ::clock();
for( int i = 0; i < size-1; ++i )
boost::add_edge( vertices[i+1], vertices[i], *myGraph );
cout << "Adding edges...Done: " << (double)((::clock()-m_clockStart)/CLOCKS_PER_SEC) << " seconds" << endl;
}
{
cout << "Deallocating graph...Started:" << endl;
clock_t m_clockStart = ::clock();
delete myGraph;
cout << "Deallocating graph...Done: " << (double)((::clock()-m_clockStart)/CLOCKS_PER_SEC) << " seconds" << endl;
}
return 0;
}
__________________________________________________________________
Looking for the perfect gift? Give the gift of Flickr!
http://www.flickr.com/gift/
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net