Re: [Boost-users] [Graph] On Dijkstra SSSP performance
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. 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. thx again, leo
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
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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Tue, 6 Mar 2012, Leo Hidd wrote:
Sorry Jeremiah, my bad, the #4 is with vecS instead of listS, my bad (bad copy-paste....), so the #3 plus optimizations.
Could you please also try compressed_sparse_row_graph (you can just build one from your adjacency list for testing purposes)? You might also want to try dijkstra_shortest_paths_no_color_map, but I'm not sure that will help your performance.
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)
Which compiler are you using? Do you have a small test program you can send, preferably with a synthetic data set (or a reference to one from the University of Florida sparse matrix collection or similar)? -- Jeremiah Willcock
On Tue, 6 Mar 2012, Leo Hidd wrote:
Sorry Jeremiah, my bad, the #4 is with vecS instead of listS, my bad (bad copy-paste....), so the #3 plus optimizations.
Could you please also try compressed_sparse_row_graph (you can just build one from your adjacency list for testing purposes)? You might also want to try dijkstra_shortest_paths_no_color_map, but I'm not sure that will help your performance. for the dijkstra_shortest_paths_no_color_map, it accelerate things a
Le 06/03/2012 21:56, Jeremiah Willcock a écrit : little. With config #4, for remind: 4- 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); with optimizations (option /Ox) - dijkstra_shortest_paths elapsed time: 5741ms it gives 4800ms. If I use directedS instead of undirectedS on the graph type (and I double the number of edges, to create both senses), it goes down to 4420ms. If I use bidirectionalS (not doubling the edges), results are weird (distances are wrong and the elapsed time is nonsense too fast, like 57ms). As for the compressed_sparse_row_graph, I can't get it working. I do the following: typedef std::pair<int, int> Edge; typedef property < edge_weight_t, double > Edge_Cost; typedef compressed_sparse_row_graph<directedS, no_property, // Vertex properties Edge_Cost // Edge properties
csr_graph_t; typedef boost::graph_traits < csr_graph_t >::vertex_descriptor vertex_descriptor;
Edge* edge_list = new Edge [2*NbOfEdges];//then I fill it Edge_Cost* edge_weight_list = new Edge_Cost[2*NbOfEdges];//then I fill it csr_graph_t Graph_Boost (edges_are_unsorted, edge_list, edge_list+2*NbOfEdges, edge_weight_list, NbOfVertices); vertex_descriptor* p = new vertex_descriptor[num_vertices(Graph_Boost)]; double* d = new Scalar[num_vertices(Graph_Boost)]; dijkstra_shortest_paths_no_color_map(Graph_Boost, 0, predecessor_map(p). distance_map(d)); but it gives me a compilation error (related to the use of the dijkstra function) saying that none of the 6 overloads of boost::get, including: boost::detail::csr_edge_index_map<Vertex,EdgeIndex> boost::get<boost::directedS,boost::no_property,Edge_Cost,boost::no_property,size_t,Vertex>(boost::edge_index_t,const boost::compressed_sparse_row_graph<Directed,VertexProperty,EdgeProperty> &) could convert all the argument types. What am I doing wrong? Additionally, how can I build a compressed_sparse_row_graph from an adjacency_list, as you suggest?
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)
Which compiler are you using? Do you have a small test program you can send, preferably with a synthetic data set (or a reference to one from the University of Florida sparse matrix collection or similar)?
-- Jeremiah Willcock
I'm using the c++ compiler embedded with Microsoft Visual Studio 2008 Pro. I can provide a test case, but I'd like first get it working with compressed_sparse_row_graph.
Le 09/03/2012 03:07, Leo Hidd a écrit :
As for the compressed_sparse_row_graph, I can't get it working. I do the following:
typedef std::pair<int, int> Edge; typedef property < edge_weight_t, double > Edge_Cost; typedef compressed_sparse_row_graph<directedS,
no_property, // Vertex properties
Edge_Cost // Edge properties
csr_graph_t; typedef boost::graph_traits < csr_graph_t >::vertex_descriptor vertex_descriptor;
Edge* edge_list = new Edge [2*NbOfEdges];//then I fill it Edge_Cost* edge_weight_list = new Edge_Cost[2*NbOfEdges];//then I fill it csr_graph_t Graph_Boost (edges_are_unsorted, edge_list, edge_list+2*NbOfEdges, edge_weight_list, NbOfVertices); vertex_descriptor* p = new vertex_descriptor[num_vertices(Graph_Boost)]; double* d = new Scalar[num_vertices(Graph_Boost)]; dijkstra_shortest_paths_no_color_map(Graph_Boost,
0,
predecessor_map(p).
distance_map(d));
but it gives me a compilation error (related to the use of the dijkstra function) saying that none of the 6 overloads of boost::get, including:
boost::detail::csr_edge_index_map<Vertex,EdgeIndex> boost::get<boost::directedS,boost::no_property,Edge_Cost,boost::no_property,size_t,Vertex>(boost::edge_index_t,const boost::compressed_sparse_row_graph<Directed,VertexProperty,EdgeProperty> &)
could anyone give me a hand on this here? Do any of you have an working example using compressed_sparse_row_graph graph type for SSSP with dijkstra_shortest_paths, for example?
On Mon, 12 Mar 2012, Leo Hidd wrote:
Le 09/03/2012 03:07, Leo Hidd a écrit :
As for the compressed_sparse_row_graph, I can't get it working. I do the following:
typedef std::pair<int, int> Edge; typedef property < edge_weight_t, double > Edge_Cost; typedef compressed_sparse_row_graph<directedS, no_property, // Vertex properties Edge_Cost // Edge properties
csr_graph_t; typedef boost::graph_traits < csr_graph_t >::vertex_descriptor vertex_descriptor;
Edge* edge_list = new Edge [2*NbOfEdges];//then I fill it Edge_Cost* edge_weight_list = new Edge_Cost[2*NbOfEdges];//then I fill it csr_graph_t Graph_Boost (edges_are_unsorted, edge_list, edge_list+2*NbOfEdges, edge_weight_list, NbOfVertices); vertex_descriptor* p = new vertex_descriptor[num_vertices(Graph_Boost)]; double* d = new Scalar[num_vertices(Graph_Boost)]; dijkstra_shortest_paths_no_color_map(Graph_Boost, 0, predecessor_map(p). distance_map(d));
but it gives me a compilation error (related to the use of the dijkstra function) saying that none of the 6 overloads of boost::get, including:
boost::detail::csr_edge_index_map<Vertex,EdgeIndex> boost::get<boost::directedS,boost::no_property,Edge_Cost,boost::no_property,size_t,Vertex>(boost::edge_index_t,const boost::compressed_sparse_row_graph<Directed,VertexProperty,EdgeProperty> &)
could anyone give me a hand on this here? Do any of you have an working example using compressed_sparse_row_graph graph type for SSSP with dijkstra_shortest_paths, for example?
It looks like you may not be passing your weight map into dijkstra_shortest_paths. If that isn't the problem, what are the exact types the compiler says that you are trying to pass to boost::get? Where is dijkstra_shortest_paths_no_color_map is it failing (which line, and which instantiation stack)? -- Jeremiah Willcock
It looks like you may not be passing your weight map into dijkstra_shortest_paths. If that isn't the problem, what are the exact types the compiler says that you are trying to pass to boost::get? Where is dijkstra_shortest_paths_no_color_map is it failing (which line, and which instantiation stack)?
-- Jeremiah Willcock
Jeremiah, here's a test case http://ge.tt/1CPQxuE/v/0 (the 3 million vertices mesh is the bimba6M.obj). There u will see the configuration number 4. In addition, I define a macro USE_BGL_CSR to using compressed sparse row instead of adjacency list. With adjacency list it works fine, but when using csr it fails to compile with the error I reported previously (by the way, it's the only error the compiler will print out). I don't feel like I'm missing the weight map, as I pass it on the graph construction. Please, if you can help me using csr it wold be nice, it should really accelerate SSSP search.
On Tue, 13 Mar 2012, Leo Hidd wrote:
It looks like you may not be passing your weight map into dijkstra_shortest_paths. If that isn't the problem, what are the exact types the compiler says that you are trying to pass to boost::get? Where is dijkstra_shortest_paths_no_color_map is it failing (which line, and which instantiation stack)?
-- Jeremiah Willcock
Jeremiah, here's a test case http://ge.tt/1CPQxuE/v/0 (the 3 million vertices mesh is the bimba6M.obj). There u will see the configuration number 4. In addition, I define a macro USE_BGL_CSR to using compressed sparse row instead of adjacency list. With adjacency list it works fine, but when using csr it fails to compile with the error I reported previously (by the way, it's the only error the compiler will print out). I don't feel like I'm missing the weight map, as I pass it on the graph construction. Please, if you can help me using csr it wold be nice, it should really accelerate SSSP search.
Here's what I get using CSR (GCC 4.7.0 20111231 on Mac OS X, -Ofast -DNDEBUG): reading bimba_6M.obj... boost graph test... boost graph SSSP: 1807567 ms my graph test... my graph SSSP: 2001208 ms dist difference between graphs: 0 The only things in your code I needed to change were to add #includes of <float.h> and <iostream> into MyGraph.h, and to change the edge weight to a bundled property (old-style properties are allowed in adjacency_list but not comparessed_sparse_row_graph). -- Jeremiah Willcock
Le 13/03/2012 03:12, Jeremiah Willcock a écrit :
On Tue, 13 Mar 2012, Leo Hidd wrote:
It looks like you may not be passing your weight map into dijkstra_shortest_paths. If that isn't the problem, what are the exact types the compiler says that you are trying to pass to boost::get? Where is dijkstra_shortest_paths_no_color_map is it failing (which line, and which instantiation stack)?
-- Jeremiah Willcock
Jeremiah, here's a test case http://ge.tt/1CPQxuE/v/0 (the 3 million vertices mesh is the bimba6M.obj). There u will see the configuration number 4. In addition, I define a macro USE_BGL_CSR to using compressed sparse row instead of adjacency list. With adjacency list it works fine, but when using csr it fails to compile with the error I reported previously (by the way, it's the only error the compiler will print out). I don't feel like I'm missing the weight map, as I pass it on the graph construction. Please, if you can help me using csr it wold be nice, it should really accelerate SSSP search.
Here's what I get using CSR (GCC 4.7.0 20111231 on Mac OS X, -Ofast -DNDEBUG):
reading bimba_6M.obj... boost graph test... boost graph SSSP: 1807567 ms my graph test... my graph SSSP: 2001208 ms dist difference between graphs: 0
The only things in your code I needed to change were to add #includes of <float.h> and <iostream> into MyGraph.h, and to change the edge weight to a bundled property (old-style properties are allowed in adjacency_list but not comparessed_sparse_row_graph).
-- Jeremiah Willcock it sounds really good! Do you mind to send me by e-mail the BoostGraph.h file with the modifications you made? Are you using 32 or 64bits OS version? Your processor is Intel, I presume. I changed Edge_Cost definition to: struct Edge_Cost{double weight;}; and now it compiles just fine! That's what supposed to do, that's what you did?
On Tue, 13 Mar 2012, Leo Hidd wrote:
Le 13/03/2012 03:12, Jeremiah Willcock a écrit :
On Tue, 13 Mar 2012, Leo Hidd wrote:
It looks like you may not be passing your weight map into dijkstra_shortest_paths. If that isn't the problem, what are the exact types the compiler says that you are trying to pass to boost::get? Where is dijkstra_shortest_paths_no_color_map is it failing (which line, and which instantiation stack)?
-- Jeremiah Willcock
Jeremiah, here's a test case http://ge.tt/1CPQxuE/v/0 (the 3 million vertices mesh is the bimba6M.obj). There u will see the configuration number 4. In addition, I define a macro USE_BGL_CSR to using compressed sparse row instead of adjacency list. With adjacency list it works fine, but when using csr it fails to compile with the error I reported previously (by the way, it's the only error the compiler will print out). I don't feel like I'm missing the weight map, as I pass it on the graph construction. Please, if you can help me using csr it wold be nice, it should really accelerate SSSP search.
Here's what I get using CSR (GCC 4.7.0 20111231 on Mac OS X, -Ofast -DNDEBUG):
reading bimba_6M.obj... boost graph test... boost graph SSSP: 1807567 ms my graph test... my graph SSSP: 2001208 ms dist difference between graphs: 0
The only things in your code I needed to change were to add #includes of <float.h> and <iostream> into MyGraph.h, and to change the edge weight to a bundled property (old-style properties are allowed in adjacency_list but not comparessed_sparse_row_graph).
-- Jeremiah Willcock
it sounds really good! Do you mind to send me by e-mail the BoostGraph.h file with the modifications you made? Are you using 32 or 64bits OS version? Your processor is Intel, I presume. I changed Edge_Cost definition to: struct Edge_Cost{double weight;}; and now it compiles just fine! That's what supposed to do, that's what you did?
I just added the two #includes that I mentioned. I'm pretty sure I'm running a 64-bit OS (on a Nehalem); I don't remember what the default compilation mode is, though. In regards to your final question, yes, that is the change that I made, plus adding the weight map parameter explicitly to the call to dijkstra_shortest_paths_no_color_map. -- Jeremiah Willcock
participants (2)
-
Jeremiah Willcock -
Leo Hidd