Boost logo

Boost Users :

Subject: Re: [Boost-users] boost::graph, ref vs. copy during relaxation
From: Tristram Gräbener (tristramg_at_[hidden])
Date: 2012-08-27 14:44:08


On Mon, Aug 27, 2012 at 7:51 PM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net