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

Subject: Re: [boost] How to speed up the djikstra graph
From: Lennart Berg (LB_at_[hidden])
Date: 2009-05-23 18:04:21

Sadly due to the restriction of the engine I have to stick with the now
dated Visual C++ 6.

I am running with boost 1.35.

I have tried the last couple of hours to port the boost trunk to VC6 but it
seems more or less hopeless for me.
So unless the 25% speedup is a small patch that can be implemented, I dont
see any change in the current setup. (The sparsed graph is calling out for a
newer compiler)

I am currently looking into the parallel boost project and will try to get a
previus trunk version to work with the 1.35.

-----Original Message-----
From: boost-bounces_at_[hidden] [mailto:boost-bounces_at_[hidden]]
On Behalf Of Jeremiah Willcock
Sent: 22. maj 2009 16:50
To: boost_at_[hidden]
Subject: Re: [boost] How to speed up the djikstra graph

On Fri, 22 May 2009, Lennart Berg wrote:

> Thanks for the reply, I am not sure yet how to use adjancy list
effectively
> to improve the speed... I am looking for some inspiration on google now..
> If you could provide me with some short pseudo code or an example, that
> would be grat

(snip)

One potential issue is that BGL performance in debug mode is not 
representative of what will happen in release mode.  Also, it appears that 
you are completely rebuilding the graph in every round of your game.  If 
that is true, you might want to use the compressed_sparse_row_graph and 
its sorted add_edge operation in all versions of the CSR graph; or 
pre-build a sequence of pairs and corresponding distances (possibly 
unsorted) using the constructors coming out in 1.40 and that are currently 
in the trunk.  The CSR graph type tends to be faster for read-only access, 
and its sorted add_edge function is also fast.  It is only for directed 
graphs, but you should be able to insert each distance twice (once for 
each direction) if your distances are all positive.  Also, x86 performance 
of Dijkstra is ~25% better on the trunk than in 1.38 (and probably 1.39) 
so you might want to benchmark against that; again, release mode is 
important to get accurate performance information.

-- Jeremiah Willcock
_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost