[Freeciv-Dev] Re: [RFC] Path finding implementation.

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

I put in priority queue instead of bucket list and got a very significant 
improvement, from around 11sec to 7.9sec.  I think it is mostly because of 
huge memory allocations that were necessary to do bucket list.

Also, much to my surprise, when I put the lattice sizes to be the exact 
map sizes, as opposed to some power of 2, I also get good speed 
improvement.  Strange, I thought it is much faster to do x % 128 than to 
do x % 60...  Maybe my compiler does not optimize x % 128 to x | 127 ??
Or the memory allocation is that expensive??

All in all, I am able to bring time down to 7sec, so it doesn't look that 
critically bad.

G.

On Wed, 26 Jun 2002, Raimar Falke wrote:

> On Wed, Jun 26, 2002 at 08:01:11PM +0100, Gregory Berkolaiko wrote:
> > On Wed, 26 Jun 2002, Raimar Falke wrote:
> > > > So to minimize memory usage it would be better to use map.xsize and 
> > > > map.ysize, but for speed it's better to use some predefined powers of 2 
> > > > I 
> > > > think.
> > > 
> > > So you just have to choose two constants and ensure that
> > > PRIVATE_[XY]SIZE >= MAX_[XY]SIZE.
> > 
> > Yep.  It wastes memory unfortunately :(
> 
> You can avoid the multiplication by using a 2D array.
> 
>       Raimar
> 
>