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

From: David Abrahams (dave_at_[hidden])
Date: 2006-10-02 22:56:51

"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