[Freeciv-Dev] Re: (PR#2370) Path finding

["Raimar Falke via RT" <rt@xxxxxxxxxxxxxx>]

On Fri, Nov 22, 2002 at 11:37:10AM -0800, Gregory Berkolaiko via RT wrote:
> 
> On Wed, 20 Nov 2002, Raimar Falke via RT wrote:
> 
> > This is an update of path_x4. Changes:
> >  - make RF code faster by reducing the memory footprint
> 
> Changes: 
>    - updated GB code, reduced memory footprint.

The code versions Gregory and I have a now very similar in what they
do. They however differ in the detail. To get to a version which can
be put into CVS we have to decide which kind of flexibility we want
and what kind of techniques we use.

First: inlining. It is critical that this is done. Gregory uses macros
like

#define get_turn(map, cost) \
  ((cost) / (map)->params->move_rate)

#define get_moves_left(map, cost) \
  ((map)->params->move_rate \
   - ((cost) % (map)->params->move_rate))

#define adjust_cost(map, cost) \
  if (cost < PF_MAXCOST) { \
    switch (map->params->turn_mode) { \
    case TM_NONE: \
      break; \
    case TM_AVERAGE: \
      cost = MIN(cost, map->params->move_rate); \
      break; \
    case TM_SAFE: \
      { \
        int moves_left = get_moves_left(map, map->lattice[map->xy].cost); \
        \
        cost = (cost > moves_left ? moves_left + cost : cost); \
        break; \
      } \
    case TM_LUCK: \
      { \
        int moves_left = get_moves_left(map, map->lattice[map->xy].cost); \
        \
        cost = (cost > moves_left ? moves_left : cost); \
        break; \
      } \
    } \
  }

while I use the inline keyword. Both can provide the same results.

Second: the speed depends strongly on the size of the node/cell. It is
currently about 20 bytes. It is possible to cache certain data but
this make the node/cell larger. I'm using defines:

  #define CACHE_TILE
  #define CACHE_ECOT
  #define CACHE_COP

to control what is cached. However what should be cached depends on
how expensive the functions are (we can't tell this for ECOT) and how
this related to the memory system of the computer. So while currently
caching the tile is good it may not if we inline the map_get_tile
function at some point. Should we decide for one? Should we use
something like the defines above? Any other way?

Third: while not related to size of the node/cell it is similar to the
second point: use of a 1D array or use of a 2D array. I also have a
USE_2D define for this and _at my computer_ the 2D array is faster by
4%.

Fourth: how general/special do we want the queue implementation. If we
for example typedef that the queue works on shorts (16bit, less
memory) instead of void pointers or int we can get some speed. However
this makes the queue not general. Also critical (see point 1) is the
inlining of the queue functions.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Make it idiot-proof and someone will make a better idiot."