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

Greg Link 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 >

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