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:
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
unsigned short neighbor_indices;
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
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 www.boost-consulting.com
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