[Freeciv-Dev] Re: Profiling Civserver again

[Trent Piepho <xyzzy@xxxxxxxxxxxxx>]

On Wed, 25 Jul 2001, Jason Dorje Short wrote:
> Well, for now the patch just changes this one loop.  However, it looks
> like there are dozens of other loops that can also use the macro -
> making the code both cleaner and faster.

This is what I was talking about when I said there are lots of places that
iterate around a tile, normalizing map coordinates more often than necessary.

If you think about, there are 9 possible patterns when iterating around a
tile.  One is that a tile isn't on the boundary of the map, and no adjustment
is necessary at all.  Another is that the tile is on the top edge of the map,
in which case the three neighbors above it get skipped.  Or it's on the right
edge of the map, in which case the three neighbors to the right need to have
their x coordinates wrapped around from map.xsize to 0.  And so on.

If you number each tile in the map, based on what needs to be done to iterate
around its neighbors, you get something like this:
---------------
|0|1|1|1|1|1|2|
|-+-+-+-+-+-+-|
|3|8|8|8|8|8|4|
|-+-+-+-+-+-+-|
|3|8|8|8|8|8|4|
|-+-+-+-+-+-+-|
|5|6|6|6|6|6|7|
---------------

Now, take the DIR_DX and DIR_DY arrays that give the offsets for the 8
neighbors and make them into 9 by 8 arrays.  DIR_DX[0][] would give the eight
offsets for a "type 0" tile, one which is in the upper left corner. 
DIR_DX[8][] would give offsets for a "type 8" tile, which is in the interior
of the map.  The DIR_DX and DIR_DY arrays would look something like this.

#define XX      MAX_INT         /* XX is a marker that means skip */
#define WR      (-map.xsize)    /* wrap off the right edge */
#define WL      (map.size)      /* wrap off the left edge */
/* NW corner tile */
DIR_DX[0][] = { XX, XX, XX, WL,  1, WL,  0,  1};
DIR_DY[0][] = { XX, XX, XX,  0,  0, -1, -1, -1};
/* interior tile */
DIR_DX[8][] = { -1,  0,  1, -1,  1, -1,  0,  1};
DIR_DY[8][] = { -1, -1, -1,  0,  0,  1,  1,  1};


The current iterate code looks like this:

#define adjc_dir_iterate(x, y, x1, y1, dir)     \
for (dir = 0; dir < 8; dir++) {                 \
  x1 = x + DIR_DX[dir];                         \
  y1 = y + DIR_DY[dir];                         \
  if (normalize_map_pos(&x1, &y1)) {            \

#define adjc_dir_iterate_end \
  } \
}   \

Unfortunately it wasn't placed inside an iterator macro, but if it had been,
that's what the macro would be.

This is my new iterator macro.  It doesn't perform any adjustments on the
coordinates, those are already build into the DIR_DX and DIR_DY arrays.

#define adjc_dir_iterate(x, y, x1, y1, dir)     \
{ int type = map_tile_boundary_type(x,y);       \
  for (dir = 0; dir < 8; dir++) {               \
    if(DIR_DX[type][dir] == MAX_INT) continue;  \
    x1 = x + DIR_DX[type][dir];                 \
    y1 = y + DIR_DY[type][dir];                 \

#define adjc_dir_iterate_end \
  } \
}   \

It also needs a new function to get a tile's type:

int map_tile_boundary_type(int x, int y)
{
  if(y==0) {                                    /* +---+---+---+ */
    return x==0? 0 :(x==map.xsize? 2 : 1 );     /* | 0 | 1 | 2 | */
  } else if(y==map.ysize) {                     /* +---+---+---+ */
    return x==0? 3 :(x==map.xsize? 4 : 8 );     /* | 3 | 8 | 4 | */
  } else {                                      /* +---+---+---+ */
    return x==0? 5 :(x==map.xsize? 7 : 6 );     /* | 5 | 6 | 7 | */
  }                                             /* +---+---+---+ */
}

I think this is going to be a pretty fast way to iterate around adjacent
tiles.  A similar technique can be used to speed up some of the other iterator
macros, like cartesian_adjacent_iterate, which is quite crude.  I also wonder
why adjc_iterate is abbreviated and cartesian_adjacent_iterate is not.  Who
wrote that code, anyway?