[Freeciv-Dev] Re: Path finding: to cache or not to cache.

[rf13@xxxxxxxxxxxxxxxxx]

On Sun, Oct 06, 2002 at 07:59:28PM +0100, Gregory Berkolaiko wrote:
> Hi,
> 
> I did some experimenting with caching of various values.
> Here are some basic observations:
> 
> * Caching leads to increase in the size of the basic node struct which 
> results in a slow down.
> 
> * Caching is done to optional values, like extra_cost and is_my_zoc.  Even 
> if the corresponding call-back or option is not enable, the memory 
> allocation is performed.
> 
> I did the following experiment: 
> code version 1: extra cost of the tile is cached in the struct node
> code version 2: extra cost of the tile is computed each time it is needed
> 
> setup a: no get_ECOT call-back is supplied
> setup b: a get_ECOT callback static to path_finding.c and rather slim is 
> supplied
> 
> Results (average time over about 8 runs):
> 1a  0.94 sec
> 2a  0.91 sec
> 
> 1b  0.99 sec
> 2b  0.99 sec
> 
> 
> I tend to make following conclusions: if get_ECOT call-back is a little 
> more substantial, the caching will give speed.  But how often a call-back 
> would be supplied?  Probably often enough.  But it's worth thinking about 
> zoc-related cached values (2 bools).  AI largely ignores ZOC in it's 
> distance-estimations and AI is the biggest customer for path-finding, at 
> least now.

First I want to know how much on average the get_ECOT callback is
called multiple times. Can you measure this? If this number is low for
different styles of path finding tasks (plain land, land with
railroads, sea) there is no point in caching them.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx