Re: [gnugo-devel] yet another one speed optimization

[Arend Bayer]

Paul wrote:

> here are the first few lines of a profile of gnugo 3.3.16-pre-3
> on nngs2.tst:
>
> Each sample counts as 0.00195312 seconds.
>   %   cumulative   self              self     total
>  time   seconds   seconds    calls   s/call   s/call  name
>  12.63 <<  57.15    57.15 133344624     0.00     0.00  scan_for_patterns
>   4.98     79.70    22.55 175060566     0.00     0.00  fastlib
>   4.16     98.52    18.82   320334     0.00     0.00  
> compute_connection_distances
>   3.95    116.39    17.87 70621678     0.00     0.00  do_play_move
>   3.16    130.68    14.29 63575116     0.00     0.00  hashtable_search
>   2.92    143.90    13.22 74884558     0.00     0.00  incremental_order_moves
>   2.81    156.63    12.73 55062649     0.00     0.00  order_moves
>   2.65    168.64    12.01    98154     0.00     0.00  do_push_owl
>   2.30    179.07    10.43       96     0.11     0.13  
> hashtable_partially_clear
>   2.21    189.09    10.02 84961653     0.00     0.00  check_pattern_light
>
> i was quite surprised to see that scan_for_patterns() takes 12.5%
> already. in the previous profile i made it was only about 7.5%.
> maybe its a side effect on nando's recent patch - since tactical
> reading now takes less time, scan_for_patterns() takes relatively
> more. or maybe it's just because i now use gcc 3.2.

Yes this is bad, and the problem will increase as processor speeds go up
(as scan_for_patterns is mostly memory latency bound, whereas the rest
of the code is mostly CPU bound). On what processor/RAM is this?

> -/* perform pattern matching with dfa filtering */
> +/* Perform pattern matching with dfa filtering. Sort patterns to keep
> + * the same order as standard matcher.
> + */
>  static void
>  do_dfa_matchpat(dfa_rt_t *pdfa,
>               int anchor, matchpat_callback_fn_ptr callback,

> +
> +#else /* !DFA_SORT */
> +
> +/* Perform pattern matching with dfa filtering. */
> +static void
> +do_dfa_matchpat(dfa_rt_t *pdfa,
> +             int anchor, matchpat_callback_fn_ptr callback,
> +             int color, struct pattern *database,
> +             void *callback_data, char goal[BOARDMAX],
> +                int anchor_in_goal)
(...)

This might be a good time to kill DFA_SORT. It is superceeded by the
newer sorting algorithms in owl.c in my opinion (I don't think anyone
has ever used this since it has been turned off by default).

Arend