Re: [boost] How to speed up the djikstra graph

Subject: Re: [boost] How to speed up the djikstra graph
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-05-22 11:02:39

Lennart Berg wrote:
> I have done some performance tests in debug mode, and there it seems
> add_edge is using up most of the time (51% of total calc time).
> It might be that this time is reduced considerably in release, that I
> haven't tested.

Don't do performance tests in debug mode.  In my experience compiler optimization speeds up heavily templated code by ~6X, versus about 20% speedup for heavily c-style code.  Your real performance break down in optimized build could be very different from what you measured.  In the extreme case add_edge may be inlined by the compiler and not even show up in your profiling.  There is a certain challenge in profiling heavily inlined code, though, since it becomes hard to know which inline functions are taking up the runtime because their time is attributed to the caller.  We had one standalone benchmark that heavily used templated code I had written that we eventually got the compiler to inline 100% of functions so that all runtime was attributed to main().  I have also compared two algorithms in debug build and found one to be faster than the other by 2X, but when compared in optimized algorithms the other was 4X faster than the first.  The point is, unoptimized build performance is not a reliable indication of real performance, particularly when code is heavily templated (like boost graph.)

Regards,
Luke