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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Mon, Jul 22, 2002 at 12:25:17AM +0200, Gaute B Strokkenes wrote:
> 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.

$ cat a.c
int f(int x) { return x%128;}
$ gcc -O2 -S a.c
$ cat a.s
        .file   "a.c"
        .text
        .align 16
.globl f
        .type   f,@function
f:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %eax
        testl   %eax, %eax
        movl    %eax, %edx
        js      .L3
.L2:
        popl    %ebp
        andl    $-128, %edx
        subl    %edx, %eax
        ret
        .p2align 4,,7
.L3:
        leal    127(%eax), %edx
        jmp     .L2
.Lfe1:
        .size   f,.Lfe1-f
        .ident  "GCC: (GNU) 3.0.3"

Please people try this before you say anything.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  Microsoft does have a year 2000 problem. I'm part of it. I'm running Linux.