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

[Gaute B Strokkenes <gs234@xxxxxxxxx>]

On Sat, 29 Jun 2002, rf13@xxxxxxxxxxxxxxxxx wrote:
> On Fri, Jun 28, 2002 at 10:28:49PM +0100, Gregory Berkolaiko wrote:
>> 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.
> 
> I have also restarted working on this. I also introduced a heap
> now. I'm currently fighting with a nice effect: the algo finds a
> shorter path to a tile. But this tile is in the heap and so the heap
> may become invalid. It has to be rebuilt. Took me quite some time to
> catch this.
> 
>> 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 ??

You mean "x & 127".

> gcc -S is your friend. But I'm sure that it does.

Only if x is an unsigned type, remember.

-- 
Big Gaute                               http://www.srcf.ucam.org/~gs234/
UH-OH!!  I put on ``GREAT HEAD-ON TRAIN COLLISIONS of the 50's''
 by mistake!!!