Re: [gnugo-devel] Looping over the board

[Arend Bayer]

Gunnar wrote:

> 1. Introduce an array next_board_point[] which is set up to point from
>    each point on the board to the next point on the board in the same
>    order as the loop construction above and from the last point to
>    NO_MOVE. Then we can loop with 
> 
>    for (pos = BOARDMIN; pos != NO_MOVE; pos = next_board_point[pos]) {
>      ...board[pos]...
>    }
> 
>    without having to worry about off-board points.

Let me point out some performance drawback here:
a) It wastes 1KB L1-Cache for next_board_point[]
b) It will prevent compiler optimizations, as the compiler won't
understand the loop anymore: e. g. in

>    for (pos = BOARDMIN; pos != MAX_BOARD; pos++) {
>      ...board[pos]...
>    }

the compiler will not use (pos) but board+pos as induction variable of
the loop, which means it can save recomputing board+pos for every
iteration. Also, it might be able to use prefetching for the arrays
index with [pos] in the loop, etc.

An alternative, admittedly uglier solution would be

   #define LOOP_BOARD(pos) \
     for (pos = BOARDMIN; pos < BOARDMAX; \ 
          (ON_BOARD(pos++) ? pos : pos = pos + 1 + MAX_BOARD - boardsize))

> 2. Introduce a macro
> 
>    #define LOOP_BOARD(pos) \
>      for (pos = BOARDMIN; pos != NO_MOVE; pos = next_board_point[pos])
> 
>    and loop with the construction
>    
>    LOOP_BOARD(pos) {
>      ...board[pos]...
>    }
> 

> The drawback of the last construction is that it's doing a somewhat
> scary amount of preprocesser magic, hiding a complete for statement in
> a macro.
Well, if you suggest it the preprocessor magic cannot be that scary :)

Despite my performance objection I am in favor of your proposal, since
none of the current board loops are performance critical; we should just
keep in mind to possibly not use it where loops could become
bottlenecks.

Arend