Re: [Boost-users] [BGL] Boost poor performance (against LEDA)

From: Leandro Melo (ltcmelo_at_[hidden])
Date: 2006-10-02 16:05:19

Hi David.
I think there's a misunderstanding here. I believe that I know many of
the benefits of Generic Programming. But my poiny is that I don't
agree that algorithms implemented generically can be considered to be
faster just because of that.
What I was trying to say is that. When you build a DFS algorithm for
example (either generically or a very specialized version), the
implementation has its lower bounds. And when I say that, I suppose
I'm using a nice graph structure. Suppose I have a graph structure and
I'm not able to provide an implementaiton of the Property Map
interface that achieves constant time access. If I run Dijkstra
algorithm with this structures, I will not get the best bound for the
algorithm.
In other words, in the case of Boost I believe that the fact
algorithms are implement in a generic way contributes more to aspects
related to 'flexibility'. Aspects related to 'performance' are
intrinsically related to 'how' the algorithms are implemented (either
in a generic or specialized version).

On 10/2/06, David Abrahams <dave_at_[hidden]> wrote:
> "Leandro Melo" <ltcmelo_at_[hidden]> writes:
>
> > Hi David.
> > I understand that Boost's architecture (taking into account the
> > template stuff, the fact all algorithms are implemented as functions
> > and the layering of the algorithms implementations) favors a nice
> > performance of the library. However, I can't get how algorithms can be
> > implemented in a manner to be fast with a wide variety of graph
> > structures.
>
> That's the magic of generic programming.
>
> > To make my point clear, I mean that a DFS is always a DFS, the
> > algorithm is the same. So, how could one implement a 'optimized' DFS
> > for a wide variety a graph structures.
>
> You create abstractions ("concepts") that handle all the various
> structures without adding any performance penalty.  For example, all
> of the algorithms use property maps to access properties associated
> with edges and vertices.  That allows them to run fast whether the
> properties are stored internally or externally.
>
> I suggest reading the BGL book; it has a pretty good introduction to
> generic programming.
>
> --
> Dave Abrahams
> Boost Consulting
> www.boost-consulting.com
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>

-- 
Leandro Terra C. Melo