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

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

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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users