[Freeciv-Dev] Re: inlining functions

[Markus Linnala <maage@xxxxxxxxx>]

Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx> writes:

> This is all nice. I hope however that we can beat most of the things
> by smarter planning of data structures/data handling and not macros
> and inlining. So it like your spotting of get_player and also the
> ongoing discussion about the map normalization. All this will just
> elimate the calls and not make them faster.

If you want to profile them, you can with my proposal. Yes, but
you reall can't make these kind of functions lot faster.

------------------------------------------------------------------------
struct player *get_player(int player_id)
{
    return &game.players[player_id];
}
int tech_exists(Tech_Type_id id)
{
  if (id<0 || id>=game.num_tech_types)
    return 0;
  else 
    return advances[id].req[0]!=A_LAST && advances[id].req[1]!=A_LAST;
}
------------------------------------------------------------------------

I once made patch that tried to cache map_get_tile and
calculation. Well, stupid idea. But I noticed, you could
sometimes call map_get_tile with same arguments over 100 times
in a row. Why? There is big room for improvement.

And yes you can optimize map_get_tile, by makeing it like this:
------------------------------------------------------------------------
struct tile *map_get_tile_opt(int x, int y)
{
  assert(y>=0 && y<map.ysize);
  assert(x>=0 && x<map.xsize);
  return map.tiles+map_adjust_x(x)+y*map.xsize;
}
------------------------------------------------------------------------

And make your iterators smarter. It is more effective to iterate:
------------------------------------------------------------------------
int min_y = MAX(0, y);
int max_y = MIN(map.ysize, y);
int min_x = MAX(0, x);
int max_x = MIN(map.xsize, x);
for (y = min_y; y <= max_y; y++) {
  for (x = min_x; y <= max_x; x++) {
    struct tile *ptile = map_get_tile_opt(x, y);
  }
}
------------------------------------------------------------------------

And at many places this is situation. First we check that we
have correct area, then we get tile and make calculations. So we
check/normalize x and y twice.


If you want to optimize usage. You can for example here, aiunit.c
------------------------------------------------------------------------
    whole_map_iterate(x1, y1) {
      struct tile *ptile = map_get_tile(x1, y1);
      unknown = 0;
      if (ptile->continent == con
          && !is_non_allied_unit_tile(ptile, punit->owner)
          && !is_non_allied_city_tile(ptile, punit->owner)
          && tile_is_accessible(punit, x1, y1)) {
        square_iterate(x1, y1, range, x2, y2) {
          if (!map_get_known(x2, y2, pplayer))
            unknown++;
        } square_iterate_end;
        if (unknown) {
          if (is_sailing_unit(punit))
            unknown += 9 * (threshold - warmap.seacost[x1][y1]);
          else
            unknown += 9 * (threshold - warmap.cost[x1][y1]);
          if ((unknown > most_unknown || (unknown == most_unknown && 
myrand(2)))              && !(is_barbarian(pplayer) && ptile->special & S_HUT)) 
{
            best_x = x1;
            best_y = y1;
            most_unknown = unknown;
          }
        }
      }
    } whole_map_iterate_end;
------------------------------------------------------------------------

We iterate over whole map, but only make something when we are
at same continent.

Continents are numbered. Make array size of continents. Save
tiles at continent to the array. Iterate over them. Tiles can
for a continent only finite (known) places. We update this array
accordingly. If map has several islands, this usually saves 

Old:
map_get_tile called max.xsize * map.ysize times

New:
map_get_tile called: (average size of island)

And if change struct tile as:
------------------------------------------------------------------------
struct tile {
  enum tile_terrain_type terrain;
  enum tile_special_type special;
  struct city *city;
  struct unit_list units;
  unsigned int known;   /* A bitvector on the server side, an
                           enum known_type on the client side.
                           Player_no is index */
  unsigned int sent;    /* Indicates if  the client know the tile
                           as TILE_KNOWN_NODRAW. A bitvector like known.
                           Not used on the client side. */
  int assigned; /* these can save a lot of CPU usage -- Syela */
  struct city *worked;      /* city working tile, or NULL if none */
  signed short continent;
  signed char move_cost[8]; /* don't know if this helps! */

  /* Addition */
  int x; /* x-coordinate */
  int y; /* y-coordinate */
};
------------------------------------------------------------------------

We have have new and improved:
map_get_tile called: 0 times before if.

We should also split big functions apart. ai_manage_explorer has
4 different, distinct parts. But now we can't find out what part
makes biggest impact in general, ie. what part we should
especially optimize. Another good example is
find_something_to_kill 1463-1151, only 312 lines.
ai_manage_explorer has big impact when you play game like 30
players 15 explorers each. find_something_to_kill is always big
at late part of game. Both use about 3-10% of server processing
power.

-- 
//Markus