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

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

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. 

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

>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.

The usual fix for this is to do ((counter2 - counter1) < 0) or
something that measures the relative vs absolute times, and thus
works across the wrap boundary. It will fail if a value is not
updated for more than half the time cycle, but you can't win
them all.


How many counters might you need to (re)set on a given operation?
Is this 1, a small fixed number, dynamic/open-ended?

Is there any control on which subsets of counters might apply if
there is an open-ended possibility?

What is the way in which you determine the dependency of something
and corresponding counter(s) to update? Is this hard coded or is
there a "registry" for each something where counters can sign up
to be notified?

>-- 
> email: rf13@xxxxxxxxxxxxxxxxx
> "This is Linux Country. On a quiet night, you can hear Windows reboot."

Cheers,
RossW
=====