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