Re: speedups (was: Re: [gnugo-devel] Timing data)

[Arend Bayer]

On Mon, 25 Feb 2002, Gunnar Farneback wrote:

> Arend wrote:
> > 1. Owl patterns should have a classification that can tell
> >    "constraint is quick to evaluate". In this case, the constraint should
> >    be evaluated before owl_safe_move is called. Consider e.g. VA24:

> This may be a good idea, but hand selection of the patterns doesn't
> sound very maintainable in the long run. I suggest the following
> generalization:
> 
> * Introduce a new constraint_complexity field in the pattern struct.
> * Associate a cost with each autohelper in the big table in mkpat.c.
> * Compute the constraint complexity in mkpat by summing the cost for
>   each of the involved autohelpers.
> * Use the constraint complexity estimate to decide whether to evaluate
>   constraint or safe move condition first.
> * The constraint complexity estimate could also be used when sorting
>   the evaluation order of owl patterns with the same value.

My intention was just to single out patterns whose constraint does not
contain any call to a reading function. As the owl_safe_move gets cached
and is very likely to get used again, I'd guess that a single call to
a reading functions will on average make the constraint more expensive than
owl_safe_move.

I agree that all your suggestions could make a lot of sense; however, I
don't know whether there is a good way to guess the constraint complexity.
attack(*) could have very different expected time consumption, depending
on the pattern.

> This solution would be more generally useful, automatically apply to
> new patterns, and be easy to tune just by changing table values.
> 
> > 2. I think pop_owl would be basically unnecessary if the owl_data is
> >    directly written to and read from the stack. That'd save 3%. (I haven't
> >    really checked whether this would work.)
> 
> The very reason why push_owl() and pop_owl() exist in the first place
> is that the owl data is big enough that storing it on the stack caused
> stack overflow on some platforms.

I did not explain clearly what I meant. We have the hand created owl stack,
basically a malloc-created array owl_stack[owl_depth]. I meant
that the local_owl_data gets directly written into and read from THIS stack.
The idea is that afterwards push_owl looks like

push_owl(...)
{
  owl_stack_pointer++;
  owl_stack[owl_stack_pointer] = owl_stack[owl_stack_pointer];
}

(no save here) and

static void
pop_owl(...)
{
  (...)
  owl_stack_pointer--;
}

(No need to copy anything here.)

Then "owl" can be replaced by "&owl_stack[owl_stack_pointer]" everywhere
in do_owl_attack/defend.

Arend