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

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 wrote:

"Leandro Melo" 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

-- Leandro Terra C. Melo