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

"Leandro Melo" writes:

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.

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