Re: [Boost-users] boost::graph, ref vs. copy during relaxation

Subject: Re: [Boost-users] boost::graph, ref vs. copy during relaxation
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-08-27 13:51:46

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