[Boost-users] [BGL] Very slow adjacency_list deallocation/reallocation for debug builds

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/