Re: [Boost-users] [Graph] On Dijkstra SSSP performance

Subject: Re: [Boost-users] [Graph] On Dijkstra SSSP performance
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-03-06 11:30:31

On Tue, 6 Mar 2012, Leo Hidd wrote:

> sry, I could not make a reply in the post through 
> http://thread.gmane.org/gmane.comp.lib.boost.user/73084/focus=73086 If i use 
> the "Follow up" action and post it I have this message: "You seem to be 
> top-posting. Don't do that." That's why I'm doing this now. Hope it works. 
> Anyways...
>
> thx Jeremiah for the inputs. I tested what you said for a mesh of 3 million 
> vertices (then, 9 million edges), and here is a summary of the different 
> configs:
>
> 1- graph type: out-edge as listS;
>   predecessors: vector<vertex_descriptor> p(num_vertices(g));
>   distances: vector<double> d(num_vertices(g));
>   NDEBUG defined (release configuration);
>   no optimizations:
>   - dijkstra_shortest_paths elapsed time: 11970ms
>
> 2- graph type: out-edge as listS;
>   predecessors: vertex_descriptor* p = new 
> vertex_descriptor[num_vertices(g)];
>   distances:  double* d = new double[num_vertices(g)];
>   NDEBUG defined (release configuration);
>   no optimizations:
>   - dijkstra_shortest_paths elapsed time:  9446ms
>
> 3- graph type: out-edge as vecS;
>   predecessors: vertex_descriptor* p = new 
> vertex_descriptor[num_vertices(g)];
>   distances:  double* d = new double[num_vertices(g)];
>   NDEBUG defined (release configuration);
>   no optimizations:
>   - dijkstra_shortest_paths elapsed time:  8436ms
>
> 4- graph type: out-edge as listS;
>   predecessors: vertex_descriptor* p = new 
> vertex_descriptor[num_vertices(g)];
>   distances:  double* d = new double[num_vertices(g)];
>   NDEBUG defined (release configuration);
>   with optimizations (option /Ox)
>   - dijkstra_shortest_paths elapsed time:  5741ms
>
> 5- my implementation without optimizations takes 3289ms and with 
> optimizations takes 2860ms.

Could you please try #3 with optimizations?  Function inlining, in 
particular, is likely to be important.

> Using predecessors and distances storage as simple arrays instead of 
> std::vector have a real gain (although optimization does even more). Is it 
> possible to use arrays (maybe array of arrays) instead of vecS for 
> OutEdgeList and VertexList? Or put arrays inside some kind of class with 
> functions allowing compatibility/interfacing with the Dijkstra algorithm 
> (like insert, sort, remove, or whatever it needs)? Since the Dijkstra 
> algorithm does more read access to the edge list than the distance or path 
> arrays, it could really accelerate things.

That is basically what an std::vector is -- a dynamically-allocated array; 
when its size isn't being changed, it basically acts like a normal 
new[]-created array.

-- Jeremiah Willcock