Re: [gnugo-devel] paul_3_13.5.gz

[Paul Pogonyshev]

i wrote:
> > the patch cuts off around 600k (!) from the executable and must give a
> > measureable speedup as well (haven't checked).
>
> today i checked the speed and got an unexpected result: the 1D
> version is a tiny little bit slower than the 2D one - the
> difference is 1 - 2 seconds on nngs.tst (which runs for a bit
> more than 20 minutes on my computer). i did the check three
> times and the results are very consistent.
>
> either something went wrong or the rather large transformation[][]
> array (almost 43k) is not doing very fast. i'm going to look
> through the whole patch in search for a mistake. i'll post the
> results soon.

so i have looked trough the patch (although i wrote there were tons
of changes, they were pretty similar). haven't found any mistakes,
but found a couple of places to optimize.

first of all, what i think could cause the slowdown are some places
where 2D computations left (dfa matching and out-of-board checks in
standard matcher) for which, with the patch in, we have to use
I(anchor) and J(anchor) to obtain the two coordinates.

- scan_for_patterns() is called _very_ often, so

    dfa_pos = DFA_POS(I(anchor), J(anchor)) + DFA_OFFSET;

  can be sped up with a lookup array, like

    dfa_pos = lookup_dfa_pos[anchor];

- transformation[][] array can be reorganized, so most often used
  offsets (those around (0,0)) come first. must improve caching.

- looks like `p' array is really not needed with the patch. not
  that copying board to p takes any noticeable time, but accessing
  board[] instead of p[] can also improve caching.

any other ideas are welcome.

Paul