Boost logo

Boost Users :

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?


> 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


Dave Abrahams
Boost Consulting

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at