Boost logo

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