[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [gnugo-devel] DFA rewrite

From: Inge Wallin
Subject: Re: [gnugo-devel] DFA rewrite
Date: Mon, 2 Sep 2002 10:13:57 +0200 (MEST)

Evan Daniel wrote:
> So, my suggestion is to build the DFA to match against the entire board,
> using a much larger state table but a potential speed increase of a factor
> of ~30 (the number of squares in the largest pattern).  I think this trade
> off is worth it.

This is a good idea, but there is a little problem.

If you do a profile of the running engine, you can clearly see that
pattern matching itself takes less than 10% of the run time and
reading takes almost 90%.  All this reading comes from constraints in
the pattern, i.e. once a pattern has matched some reading is done to
see if it really applies.

So if you get a factor 30 speedup of the pattern matching, the maximum
you will get overall is 9,7% (97% of 10%).  You have to think if this
is worth it, considering the large extra use of memory that the
gigantic DFA will incur.

I think that the biggest gain will come from reducing the overall
number of patterns that are matched and also making cheaper

(Note: The exact percentages above may be somewhat off since they are
quoted from memory.)


reply via email to

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