Complete.Org: Mailing Lists: Archives: freeciv-dev: March 2002:
[Freeciv-Dev] Re: [RFC] Caching AI values

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: rf13@xxxxxxxxxxxxxxxxxxxxxx
Cc: Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>, freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: [RFC] Caching AI values
From: "Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>
Date: Fri, 22 Mar 2002 20:20:40 -0500

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;
>  assert(!pcity->x_valid);
>  x=...;
>  pcity->x_valid=TRUE;

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

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


[Prev in Thread] Current Thread [Next in Thread]