boost::graph, ref vs. copy during relaxation
Hello, I use boost::graph and the Dijkstra algorithm. My edge property is rather big (I store public transport timetables on them). In the file boost/graph/relax.hpp, the property of an edge is copied : W w_e = get(w, e); As my properties are large, it yields some overhead. I changed that line to const W & w_e = get(w, e); My benchmarks (on 1000 runs) went from 101 secs down to 87 (using GCC 4.6 -O3) So my question is : – would it hurt if it used const& instead of copy? – am I not correctly using the lib? Maybe should I use an index on the edge property and use a functor to get the data in the different operations (edge_less, combine); but wouldn't it mean re-implementing the properties? Thank you for your help
On Mon, 27 Aug 2012, Tristram Gräbener wrote:
Hello,
I use boost::graph and the Dijkstra algorithm.
My edge property is rather big (I store public transport timetables on them).
In the file boost/graph/relax.hpp, the property of an edge is copied : W w_e = get(w, e);
As my properties are large, it yields some overhead.
I changed that line to const W & w_e = get(w, e);
My benchmarks (on 1000 runs) went from 101 secs down to 87 (using GCC 4.6 -O3)
So my question is : – would it hurt if it used const& instead of copy?
I forgot if the graph library actually returns a reference rather than a copy, but it shouldn't hurt if it returns a reference (as long as you don't modify the graph structure while you're holding that reference).
– am I not correctly using the lib? Maybe should I use an index on the edge property and use a functor to get the data in the different operations (edge_less, combine); but wouldn't it mean re-implementing the properties?
Are your weights used for Dijkstra (not your whole edge property) the full timetables? If so, aren't you using custom compare and combine functions already? In any case, rather than using an index value, you can try using a shared_ptr; with that, copying will work quickly and dereferencing will be easier. -- Jeremiah Willcock
Thank you for the reply
I use boost::graph and the Dijkstra algorithm.
My edge property is rather big (I store public transport timetables on them).
In the file boost/graph/relax.hpp, the property of an edge is copied : W w_e = get(w, e);
As my properties are large, it yields some overhead.
I changed that line to const W & w_e = get(w, e);
My benchmarks (on 1000 runs) went from 101 secs down to 87 (using GCC 4.6 -O3)
So my question is : – would it hurt if it used const& instead of copy?
I forgot if the graph library actually returns a reference rather than a copy, but it shouldn't hurt if it returns a reference (as long as you don't modify the graph structure while you're holding that reference).
It returns a reference, otherwise I wouldn't get such a speed-up. Would it be appropriate to submit a patch?
– am I not correctly using the lib? Maybe should I use an index on the edge property and use a functor to get the data in the different operations (edge_less, combine); but wouldn't it mean re-implementing the properties?
Are your weights used for Dijkstra (not your whole edge property) the full timetables? If so, aren't you using custom compare and combine functions already? In any case, rather than using an index value, you can try using a shared_ptr; with that, copying will work quickly and dereferencing will be easier.
Indeed I have custom compare and combine, and this will be probably be the final solution. Having to manually patch the boost installation is not the most industrial approach ;)
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mon, 27 Aug 2012, Tristram Gräbener wrote:
Thank you for the reply
I use boost::graph and the Dijkstra algorithm.
My edge property is rather big (I store public transport timetables on them).
In the file boost/graph/relax.hpp, the property of an edge is copied : W w_e = get(w, e);
As my properties are large, it yields some overhead.
I changed that line to const W & w_e = get(w, e);
My benchmarks (on 1000 runs) went from 101 secs down to 87 (using GCC 4.6 -O3)
So my question is : – would it hurt if it used const& instead of copy?
I forgot if the graph library actually returns a reference rather than a copy, but it shouldn't hurt if it returns a reference (as long as you don't modify the graph structure while you're holding that reference).
It returns a reference, otherwise I wouldn't get such a speed-up. Would it be appropriate to submit a patch?
To do what?
– am I not correctly using the lib? Maybe should I use an index on the edge property and use a functor to get the data in the different operations (edge_less, combine); but wouldn't it mean re-implementing the properties?
Are your weights used for Dijkstra (not your whole edge property) the full timetables? If so, aren't you using custom compare and combine functions already? In any case, rather than using an index value, you can try using a shared_ptr; with that, copying will work quickly and dereferencing will be easier.
Indeed I have custom compare and combine, and this will be probably be the final solution. Having to manually patch the boost installation is not the most industrial approach ;)
What are you patching in Boost? Using a shared_ptr and custom compare and combine doesn't require any changes to Boost.Graph as far as I know. -- Jeremiah Willcock
On Mon, Aug 27, 2012 at 7:51 PM, Jeremiah Willcock
On Mon, 27 Aug 2012, Tristram Gräbener wrote:
Thank you for the reply
I use boost::graph and the Dijkstra algorithm.
My edge property is rather big (I store public transport timetables on them).
In the file boost/graph/relax.hpp, the property of an edge is copied : W w_e = get(w, e);
As my properties are large, it yields some overhead.
I changed that line to const W & w_e = get(w, e);
My benchmarks (on 1000 runs) went from 101 secs down to 87 (using GCC 4.6 -O3)
So my question is : – would it hurt if it used const& instead of copy?
I forgot if the graph library actually returns a reference rather than a copy, but it shouldn't hurt if it returns a reference (as long as you don't modify the graph structure while you're holding that reference).
It returns a reference, otherwise I wouldn't get such a speed-up. Would it be appropriate to submit a patch?
To do what?
– am I not correctly using the lib? Maybe should I use an index on the edge property and use a functor to get the data in the different operations (edge_less, combine); but wouldn't it mean re-implementing the properties?
Are your weights used for Dijkstra (not your whole edge property) the full timetables? If so, aren't you using custom compare and combine functions already? In any case, rather than using an index value, you can try using a shared_ptr; with that, copying will work quickly and dereferencing will be easier.
Indeed I have custom compare and combine, and this will be probably be the final solution. Having to manually patch the boost installation is not the most industrial approach ;)
What are you patching in Boost? Using a shared_ptr and custom compare and combine doesn't require any changes to Boost.Graph as far as I know.
I believe that if the relaxation would use a reference instead of a copy, there would be no consequence for the library. It would allow to use the properties in a straightfoward and more homogenous way to use the properties (not having to use them differently when having small properties or large ones). However, if there is an actual reason (other than : “properties should be small”) to use copy instead of a const reference during the relaxation I'd eager to learn (I'm no C++ guru)
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mon, 27 Aug 2012, Tristram Gräbener wrote: (snip)
What are you patching in Boost? Using a shared_ptr and custom compare and combine doesn't require any changes to Boost.Graph as far as I know.
I believe that if the relaxation would use a reference instead of a copy, there would be no consequence for the library.
It would allow to use the properties in a straightfoward and more homogenous way to use the properties (not having to use them differently when having small properties or large ones).
However, if there is an actual reason (other than : “properties should be small”) to use copy instead of a const reference during the relaxation I'd eager to learn (I'm no C++ guru)
Please see if what's in the trunk now (r80264 or above) satisfies your requirements. -- Jeremiah Willcock
What are you patching in Boost? Using a shared_ptr and custom compare and combine doesn't require any changes to Boost.Graph as far as I know.
I believe that if the relaxation would use a reference instead of a copy, there would be no consequence for the library.
It would allow to use the properties in a straightfoward and more homogenous way to use the properties (not having to use them differently when having small properties or large ones).
However, if there is an actual reason (other than : “properties should be small”) to use copy instead of a const reference during the relaxation I'd eager to learn (I'm no C++ guru)
Please see if what's in the trunk now (r80264 or above) satisfies your requirements.
It does. Thanks a lot!
participants (2)
-
Jeremiah Willcock -
Tristram Gräbener