Boost logo

Boost Users :

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


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