[Freeciv-Dev] Re: [RFC] Caching AI values

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, Mar 22, 2002 at 08:20:40PM -0500, Ross W. Wetmore wrote:
> At 06:02 PM 02/03/21 +0100, Raimar Falke wrote:
> >On Thu, Mar 21, 2002 at 04:31:43PM +0000, Gregory Berkolaiko wrote:
> >> On Thu, 21 Mar 2002, Raimar Falke wrote:
> >> 
> >> > On Wed, Mar 20, 2002 at 07:16:37PM +0000, Gregory Berkolaiko wrote:
> [...]
> >> > This is known as lazy evaluation. You don't need a time field. A
> >> > simple bit "valid" is sufficient.
> >> 
> >> My life seems to be full of discoveries which are already known and even 
> >> have a name.
> >> 
> >> Anyway, simple bit won't do for me.  This is the sequence of event which 
> >> is possible and can't be handled nicely by one bit:
> >> 
> >> * time = 1
> >> 1. Compute quantity x for city A (stamped: 1)
> >> 2. Compute quantify x for city B (stamped: 1)
> >> 3. Something happens which (might) render cached values of x in A and B 
> >>    invalid.  Increment time.
> >> * time = 2
> >> 4. Compute quantity x for city B (previous stamped 1 < time => should be 
> >>    recalculated)
> >> 
> >> Now we have cached value in A, which isn't valid and a valid cached value 
> >> in B.  We cannot describe this situation using only
> >> bool x_cache_valid;
> >
> >Assume you add the following to struct city:
> > bool x_valid;
> > int x;
> >
> >than get_x(pcity) is 
> >{
> >  if(!pcity->x_valid)
> >    update_x(pcity);
> >  assert(pcity->x_valid);
> >  return pcity->x;
> >}
> >
> >update_x(pcity)
> >{
> >  assert(!pcity->x_valid);
> >  x=...;
> >  pcity->x_valid=TRUE;
> >}
> >
> 
> >some_event(...)
> >{
> >  city_iterate(...)
> >    ...
> >    mark_x_invalid(pcity);
> >  ....
> >}

> I have this funny feeling that cache optimization just got
> very heavy.

Do you mean code impact or runtime impact?

> Raimar, you always manages to introduce a loop over the known
> world into things when you "optimize" them :-).

The loop is already there. Like in global_city_refresh.

> >mark_x_invalid(pcity)
> >{
> >  pcity->x_valid=FALSE;
> >}
> >
> >     Raimar
> 
> I think Gregory's incremental counter is probably about the 
> best, but you might want to think about when the counter wraps.

I still don't understand why we need counters when bits are
sufficient.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "That's fundamental game play!  My main enemy is *ALWAYS* fighting 
  a 4-front war.  I make sure of it!"
    -- Tony Stuckey, freeciv-dev