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

From: Leandro Melo (ltcmelo_at_[hidden])
Date: 2006-10-03 13:56:26

Ok David, I get your point.

On 10/2/06, David Abrahams <dave_at_[hidden]> wrote:
> "Leandro Melo" <ltcmelo_at_[hidden]> writes:
>
> > 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.
> >
> > 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.
>
> I never claimed that.  I said "fast with a wide variety of graph
> structures."
>
> > 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'.
>
> The point is flexibility without loss of efficiency.  Non-generic
> solutions would cost efficiency to, say, allow you to choose between
> two O(1) lookup structures such as a hashtable and an array.
>
> > Aspects related to 'performance' are intrinsically related to 'how'
> > the algorithms are implemented (either in a generic or specialized
> > version).
>
> I don't understand the significance of the quotation marks above.
>
>
> --
> 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