Re: [Boost-users] [BGL]: Highest performance graph-type available?

From: David Abrahams (dave_at_[hidden])
Date: 2006-05-11 08:45:54

Greg Link <link_at_[hidden]> writes:

> I'm using BGL for the johnson_all_pairs_shortest_path algorithm, and  
> spending about 98% of my runtime in that algorithm. Breaking it down,  
> the BFS_visit itself is consuming some 85% of my total runtime.  
> Hence, any and every improvement I can get in my BGL performance will  
> make my app much much snappier.
>
> Currently, my graph type is a
>
> adjacency_list <vecS, vecS, undirectedS, no_property, property  
> <edge_weight_t, double> >
>
> and I'm wondering if that's the best choice. My graph has (E=2*V),  
> and all nodes are of constant degree, with 4 edges incident on them.  
> V is usually in the range of 150-500.

Oh, it sounds to me like you could probably eke some mileage out
of a custom graph data structure.  There's no need to use the supplied
adjacency_list; you can just build something that meets all the
appropriate graph concept requirements and minimally satisfies your
needs.  For example, you could think about using a vector of these:

struct node
{
   node* neighbors[4];
};

That will save a bunch of allocations in constructing the graph (you
probably don't care about these much) and a bunch of indirections in
traversing it, which could affect speed.

You might also think about

struct node
{
   unsigned short neighbor_indices[4];
};

which might buy you some speed through improved cache locality if a
short is smaller than a pointer on your system.

> Would one of the other types (such as listS) perhaps be faster, and  
> still work? 

Unlikely.

> I know some BGL algorithms require certain graph storage  
> types, 

Not really.  If you look at the requirements of the algorithms, you
won't see anything mentioned about storage.  

> Any thoughts on what might make things faster? Additionally, are  
> there any compiler flags I should consider other than the 'vanilla'  
> ones? (-O3). I'm using GCC 4.0.1 currently, if it matters.

 -O3 -funroll-loops -finline-functions

HTH,

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com