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

Subject: Re: [Boost-users] [Graph] On Dijkstra SSSP performance
From: Leo Hidd (leohidd_at_[hidden])
Date: 2012-03-06 12:06:32

Sorry Jeremiah, my bad, the #4 is with vecS instead of listS, my bad 
(bad copy-paste....), so the #3 plus optimizations.

As for the vector vs array new, yes, I know, but since it has some 
overhead when accessing elements, it makes it slower (comparing #1 to #2 
makes it very explicit)

leo

Le 06/03/2012 17:30, Jeremiah Willcock a écrit :
> 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 mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users