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

["Gregory Berkolaiko via RT" <rt@xxxxxxxxxxxxxx>]

On Sun, 24 Nov 2002, Raimar Falke via RT wrote:

> On Sun, Nov 24, 2002 at 06:35:02AM -0800, Gregory Berkolaiko via RT wrote:
> > 
> 
> I also haven't done any work about the two dangerous
> implementations. I want to get something finished and into the
> tree. Even if this means that we have to change the dangerous
> implementation later.

Ok.

> 
> > > 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))
> > 
> > The above are true macros, should be left alone IMO.
> 
> "true macros"?

as in shorthand for one-line arithmetic experssion.

> > The example below is really a function converted to a macro for 
> > performance.  Inlining would be more elegant in this case.
> 
> > Note that it is possible to write this function in about 10 lines rather 
> > then 23, if needed.
> 
> Will it than conform to the style guide?

Yes, of course.

> > > 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?
> > 
> > I think we should cache it for now, and later, when the user base for the 
> > path finding is more defined, experiment with it some more.  It's easier 
> > to remove caching than to add it.  And using defines makes code 
> > less readable.
> 
> And for the experiment we should readd the defines?

"Readd" is not well defined here.
We will add them in our private copies of the tree and run some 
simulations.

> > > 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.
> > 
> > I don't believe memory use by queue is significant.  There is also another 
> > customer for this queue, airgoto.c, but it also uses ints (can be shorts) 
> > right now.
> 
> Inlining of queue functions?

Yes, it introduces speedup, about 5%

> I think that you loose some speed with your cost functions. All should
> be inlined. BUT if you inline you seperate function it should look
> like:

yes, I think you are right.

> ...inline normal_move_unit(...) {
> ....
> }
> 
> ...get_cost(...)
> {
>   switch(type) {
>   case NORMAL_MOVE:
>     return normal_move_unit(...);
>   case ....
> ....
> }

I will experiment with it.

G.