[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] Looping over the board
From: |
Arend Bayer |
Subject: |
Re: [gnugo-devel] Looping over the board |
Date: |
Wed, 22 Dec 2004 09:18:48 +0100 (CET) |
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