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 10:34:09

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