[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] fastlib can be faster
|
From: |
Paul Pogonyshev |
|
Subject: |
[gnugo-devel] fastlib can be faster |
|
Date: |
Wed, 1 Jan 2003 22:16:43 +0200 |
- speed optimizations in board.c (mainly in fastlib())
this patch speeds fastlib() up considerably. the algorithm of
the function remains the same, but it is rewritten to exclude
loops (like in approxlib(), for instance). another half of
speedup is gained by replacing calls to neighbor_of_string
with macros.
i left the old implementation and added a stub function, which
asserts that the results of the two implementations match. they
are #if'ed and currently disabled. i've run the first regression
batch and the assertion has never failed.
here is the full list of changes:
- fastlib() rewritten with loops unrolled
- 5 new macros: NEIGHBOR_OF_STRING and
NON_<direction>_NEIGHBOR_OF_STRING (feel free to find better
names) replaced most calls to neighbor_of_string
- macro STRING_AT_VERTEX got another parameter - color
the total speedup is rather large, around 3% maybe (now there
will be more time to run experimental semeai code ;)
the profiles are on nngs2.tst.
BEFORE:
% cumulative self self total
time seconds seconds calls ms/call ms/call name
7.59 49.35 49.35 129597008 0.00 0.00 scan_for_patterns
6.25 89.95 40.60 180744884 0.00 0.00 fastlib
4.45 118.89 28.94 48356109 0.00 0.00 order_moves
4.19 146.13 27.24 75745203 0.00 0.00 do_play_move
3.40 168.25 22.12 314336 0.07 0.48
compute_connection_distances
-----------------------------------------------
1.96 0.79 8709934/180744884 accuratelib [171]
38.64 15.59 172034950/180744884 approxlib [48]
[52] 8.8 40.60 16.38 180744884 fastlib [52]
9.81 0.00 184099552/205708660 neighbor_of_string [120]
6.57 0.00 38831162/39786139 count_common_libs [142]
-----------------------------------------------
AFTER:
% cumulative self self total
time seconds seconds calls ms/call ms/call name
7.98 49.86 49.86 129597008 0.00 0.00 scan_for_patterns
4.59 78.51 28.65 180744884 0.00 0.00 fastlib
4.43 106.21 27.70 48356109 0.00 0.00 order_moves
4.05 131.52 25.31 75745203 0.00 0.00 do_play_move
3.47 153.21 21.69 314336 0.07 0.45
compute_connection_distances
-----------------------------------------------
1.38 0.36 8709934/180744884 accuratelib [188]
27.27 7.03 172034950/180744884 approxlib [52]
[64] 5.8 28.65 7.39 180744884 fastlib [64]
7.39 0.00 38831162/39786139 count_common_libs [136]
-----------------------------------------------
Paul
Index: board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.60
diff -u -p -r1.60 board.c
--- board.c 9 Dec 2002 10:41:22 -0000 1.60
+++ board.c 1 Jan 2003 20:06:25 -0000
@@ -207,8 +207,38 @@ static int next_stone[BOARDMAX];
#define MARK_STRING(pos) string[string_number[pos]].mark = string_mark
-#define STRING_AT_VERTEX(pos, s)\
- (IS_STONE(board[pos]) && string_number[pos] == (s))
+#define STRING_AT_VERTEX(pos, s, color)\
+ ((board[pos] == color) && string_number[pos] == (s))
+
+#define NEIGHBOR_OF_STRING(pos, s, color)\
+ (STRING_AT_VERTEX(SOUTH(pos), s, color)\
+ || STRING_AT_VERTEX(WEST(pos), s, color)\
+ || STRING_AT_VERTEX(NORTH(pos), s, color)\
+ || STRING_AT_VERTEX(EAST(pos), s, color))
+
+/* These four macros have rather confusing names. It should be read as:
+ * "(pos) is a neighbor of string (s) of (color) in any direction except
+ * the specified one".
+ */
+#define NON_SOUTH_NEIGHBOR_OF_STRING(pos, s, color)\
+ (STRING_AT_VERTEX(SOUTH(pos), s, color)\
+ || STRING_AT_VERTEX(WEST(pos), s, color)\
+ || STRING_AT_VERTEX(EAST(pos), s, color))
+
+#define NON_WEST_NEIGHBOR_OF_STRING(pos, s, color)\
+ (STRING_AT_VERTEX(WEST(pos), s, color)\
+ || STRING_AT_VERTEX(NORTH(pos), s, color)\
+ || STRING_AT_VERTEX(SOUTH(pos), s, color))
+
+#define NON_NORTH_NEIGHBOR_OF_STRING(pos, s, color)\
+ (STRING_AT_VERTEX(NORTH(pos), s, color)\
+ || STRING_AT_VERTEX(EAST(pos), s, color)\
+ || STRING_AT_VERTEX(WEST(pos), s, color))
+
+#define NON_EAST_NEIGHBOR_OF_STRING(pos, s, color)\
+ (STRING_AT_VERTEX(EAST(pos), s, color)\
+ || STRING_AT_VERTEX(SOUTH(pos), s, color)\
+ || STRING_AT_VERTEX(NORTH(pos), s, color))
#define LIBERTIES(pos)\
string[string_number[pos]].liberties
@@ -2012,7 +2042,161 @@ findlib(int str, int maxlib, int *libs)
*/
int
-fastlib(int pos, int color, int ignore_capture)
+fastlib(int pos, int color, int ignore_captures)
+{
+ int ally1 = -1;
+ int ally2 = -1;
+ int fast_liberties = 0;
+
+ ASSERT1(board[pos] == EMPTY, pos);
+ ASSERT1(IS_STONE(color), pos);
+
+ /* Find neighboring strings of the same color. If there are more than two of
+ * them, we give up (it's too difficult to count their common liberties).
+ */
+ if (board[SOUTH(pos)] == color) {
+ ally1 = string_number[SOUTH(pos)];
+
+ if (board[WEST(pos)] == color
+ && string_number[WEST(pos)] != ally1) {
+ ally2 = string_number[WEST(pos)];
+
+ if (board[NORTH(pos)] == color
+ && string_number[NORTH(pos)] != ally1
+ && string_number[NORTH(pos)] != ally2)
+ return -1;
+ }
+ else if (board[NORTH(pos)] == color
+ && string_number[NORTH(pos)] != ally1)
+ ally2 = string_number[NORTH(pos)];
+
+ if (board[EAST(pos)] == color
+ && string_number[EAST(pos)] != ally1) {
+ if (ally2 < 0)
+ ally2 = string_number[EAST(pos)];
+ else if (string_number[EAST(pos)] != ally2)
+ return -1;
+ }
+ }
+ else if (board[WEST(pos)] == color) {
+ ally1 = string_number[WEST(pos)];
+
+ if (board[NORTH(pos)] == color
+ && string_number[NORTH(pos)] != ally1) {
+ ally2 = string_number[NORTH(pos)];
+
+ if (board[EAST(pos)] == color
+ && string_number[EAST(pos)] != ally1
+ && string_number[EAST(pos)] != ally2)
+ return -1;
+ }
+ else if (board[EAST(pos)] == color
+ && string_number[EAST(pos)] != ally1)
+ ally2 = string_number[EAST(pos)];
+ }
+ else if (board[NORTH(pos)] == color) {
+ ally1 = string_number[NORTH(pos)];
+
+ if (board[EAST(pos)] == color
+ && string_number[EAST(pos)] != ally1)
+ ally2 = string_number[EAST(pos)];
+ }
+ else if (board[EAST(pos)] == color)
+ ally1 = string_number[EAST(pos)];
+
+ /* If we are to ignore captures, the things are very easy. */
+ if (ignore_captures) {
+ if (ally1 < 0) { /* No allies */
+ if (LIBERTY(SOUTH(pos)))
+ fast_liberties++;
+ if (LIBERTY(WEST(pos)))
+ fast_liberties++;
+ if (LIBERTY(NORTH(pos)))
+ fast_liberties++;
+ if (LIBERTY(EAST(pos)))
+ fast_liberties++;
+ }
+ else if(ally2 < 0) { /* One ally */
+ if (LIBERTY(SOUTH(pos))
+ && !NON_SOUTH_NEIGHBOR_OF_STRING(SOUTH(pos), ally1, color))
+ fast_liberties++;
+ if (LIBERTY(WEST(pos))
+ && !NON_WEST_NEIGHBOR_OF_STRING(WEST(pos), ally1, color))
+ fast_liberties++;
+ if (LIBERTY(NORTH(pos))
+ && !NON_NORTH_NEIGHBOR_OF_STRING(NORTH(pos), ally1, color))
+ fast_liberties++;
+ if (LIBERTY(EAST(pos))
+ && !NON_EAST_NEIGHBOR_OF_STRING(EAST(pos), ally1, color))
+ fast_liberties++;
+
+ fast_liberties += string[ally1].liberties - 1;
+ }
+ else { /* Two allies */
+ if (LIBERTY(SOUTH(pos))
+ && !NON_SOUTH_NEIGHBOR_OF_STRING(SOUTH(pos), ally1, color)
+ && !NON_SOUTH_NEIGHBOR_OF_STRING(SOUTH(pos), ally2, color))
+ fast_liberties++;
+ if (LIBERTY(WEST(pos))
+ && !NON_WEST_NEIGHBOR_OF_STRING(WEST(pos), ally1, color)
+ && !NON_WEST_NEIGHBOR_OF_STRING(WEST(pos), ally2, color))
+ fast_liberties++;
+ if (LIBERTY(NORTH(pos))
+ && !NON_NORTH_NEIGHBOR_OF_STRING(NORTH(pos), ally1, color)
+ && !NON_NORTH_NEIGHBOR_OF_STRING(NORTH(pos), ally2, color))
+ fast_liberties++;
+ if (LIBERTY(EAST(pos))
+ && !NON_EAST_NEIGHBOR_OF_STRING(EAST(pos), ally1, color)
+ && !NON_EAST_NEIGHBOR_OF_STRING(EAST(pos), ally2, color))
+ fast_liberties++;
+
+ fast_liberties += string[ally1].liberties + string[ally2].liberties
+ - count_common_libs(string[ally1].origin, string[ally2].origin) - 1;
+ }
+ }
+ /* We are to take captures into account. This case is much more rare, so
+ * it is not optimized much.
+ */
+ else {
+ int k;
+
+ for (k = 0; k < 4; k++) {
+ int neighbor = pos + delta[k];
+
+ if (LIBERTY(neighbor)
+ && (ally1 < 0 || !NEIGHBOR_OF_STRING(neighbor, ally1, color))
+ && (ally2 < 0 || !NEIGHBOR_OF_STRING(neighbor, ally2, color)))
+ fast_liberties++;
+ else if (board[neighbor] == OTHER_COLOR(color) /* A capture */
+ && LIBERTIES(neighbor) == 1) {
+ int neighbor_size = COUNTSTONES(neighbor);
+
+ if (neighbor_size == 1 || (neighbor_size == 2 && ally1 < 0))
+ fast_liberties++;
+ else
+ return -1;
+ }
+ }
+
+ if (ally1 >= 0) {
+ fast_liberties += string[ally1].liberties - 1;
+ if (ally2 >= 0)
+ fast_liberties += string[ally2].liberties
+ - count_common_libs(string[ally1].origin, string[ally2].origin);
+ }
+ }
+
+ return fast_liberties;
+}
+
+
+/* Enable this to check that the newer implementation above gives
+ * correct answers (using the older implementation). Don't forget to
+ * rename the newer implementation to `fastlib_new'.
+ */
+#if 0
+static int
+fastlib_old(int pos, int color, int ignore_capture)
{
int k;
int ally1 = NO_MOVE;
@@ -2082,6 +2266,18 @@ fastlib(int pos, int color, int ignore_c
return fast_liberties;
}
+
+int fastlib(int pos, int color, int ignore_captures)
+{
+ int liberties1 = fastlib_old(pos, color, ignore_captures);
+ int liberties2 = fastlib_new(pos, color, ignore_captures);
+
+ ASSERT1(liberties1 == liberties2, pos);
+
+ return liberties1;
+}
+#endif
+
/* Find the liberties a stone of the given color would get if played
* at (pos), ignoring possible captures of opponent stones. (pos)
* must be empty. If libs != NULL, the locations of up to maxlib
@@ -2516,7 +2712,7 @@ count_common_libs(int str1, int str2)
liberties2 = string[n].liberties;
if (liberties2 <= MAX_LIBERTIES) {
- /* Speed optimization: neighbor_of_string is quite expensive */
+ /* Speed optimization: NEIGHBOR_OF_STRING is quite expensive */
liberty_mark++;
for (k = 0; k < liberties1; k++)
@@ -2536,7 +2732,7 @@ count_common_libs(int str1, int str2)
}
for (k = 0; k < liberties1; k++)
- if (neighbor_of_string(libs1[k], str2))
+ if (NEIGHBOR_OF_STRING(libs1[k], string_number[str2], board[str2]))
commonlibs++;
return commonlibs;
@@ -2584,7 +2780,7 @@ find_common_libs(int str1, int str2, int
liberties2 = string[n].liberties;
if (liberties2 <= MAX_LIBERTIES) {
- /* Speed optimization: neighbor_of_string is quite expensive */
+ /* Speed optimization: NEIGHBOR_OF_STRING is quite expensive */
liberty_mark++;
for (k = 0; k < liberties1; k++)
@@ -2607,7 +2803,7 @@ find_common_libs(int str1, int str2, int
}
for (k = 0; k < liberties1; k++)
- if (neighbor_of_string(libs1[k], str2)) {
+ if (NEIGHBOR_OF_STRING(libs1[k], string_number[str2], board[str2])) {
if (commonlibs < maxlib)
libs[commonlibs] = libs1[k];
commonlibs++;
@@ -2653,7 +2849,7 @@ have_common_lib(int str1, int str2, int
}
for (k = 0; k < liberties1; k++) {
- if (neighbor_of_string(libs1[k], str2)) {
+ if (NEIGHBOR_OF_STRING(libs1[k], string_number[str2], board[str2])) {
if (lib)
*lib = libs1[k];
return 1;
@@ -3004,7 +3200,7 @@ liberty_of_string(int pos, int str)
if (IS_STONE(board[pos]))
return 0;
- return neighbor_of_string(pos, str);
+ return NEIGHBOR_OF_STRING(pos, string_number[str], board[str]);
}
@@ -3020,7 +3216,7 @@ second_order_liberty_of_string(int pos,
for (k = 0; k < 4; k++)
if (board[pos + delta[k]] == EMPTY
- && neighbor_of_string(pos + delta[k], str))
+ && NEIGHBOR_OF_STRING(pos + delta[k], string_number[str], board[str]))
return 1;
return 0;
@@ -3034,36 +3230,18 @@ second_order_liberty_of_string(int pos,
int
neighbor_of_string(int pos, int str)
{
- int s;
int color = board[str];
ASSERT1(IS_STONE(color), str);
ASSERT_ON_BOARD1(pos);
- s = string_number[str];
-
- if (board[SOUTH(pos)] == color
- && string_number[SOUTH(pos)] == s)
- return 1;
-
- if (board[WEST(pos)] == color
- && string_number[WEST(pos)] == s)
- return 1;
+ return NEIGHBOR_OF_STRING(pos, string_number[str], color);
+}
- if (board[NORTH(pos)] == color
- && string_number[NORTH(pos)] == s)
- return 1;
- if (board[EAST(pos)] == color
- && string_number[EAST(pos)] == s)
- return 1;
-
- return 0;
-}
/*
* Returns true if (pos) has a neighbor of color (color).
*/
-
int has_neighbor(int pos, int color)
{
ASSERT_ON_BOARD1(pos);
@@ -3788,7 +3966,8 @@ extend_neighbor_string(int pos, int s)
{
int k;
int liberties_updated = 0;
- int other = OTHER_COLOR(board[pos]);
+ int color = board[pos];
+ int other = OTHER_COLOR(color);
/* Link in the stone in the cyclic list. */
int pos2 = string[s].origin;
@@ -3836,9 +4015,7 @@ extend_neighbor_string(int pos, int s)
*/
if (LIBERTY(SOUTH(pos))) {
if (!liberties_updated
- && !(STRING_AT_VERTEX(SS(pos), s)
- || STRING_AT_VERTEX(SW(pos), s)
- || STRING_AT_VERTEX(SE(pos), s)))
+ && !NON_SOUTH_NEIGHBOR_OF_STRING(SOUTH(pos), s, color))
ADD_LIBERTY(s, SOUTH(pos));
}
else if (UNMARKED_COLOR_STRING(SOUTH(pos), other)) {
@@ -3852,9 +4029,7 @@ extend_neighbor_string(int pos, int s)
if (LIBERTY(WEST(pos))) {
if (!liberties_updated
- && !(STRING_AT_VERTEX(WW(pos), s)
- || STRING_AT_VERTEX(NW(pos), s)
- || STRING_AT_VERTEX(SW(pos), s)))
+ && !NON_WEST_NEIGHBOR_OF_STRING(WEST(pos), s, color))
ADD_LIBERTY(s, WEST(pos));
}
else if (UNMARKED_COLOR_STRING(WEST(pos), other)) {
@@ -3868,9 +4043,7 @@ extend_neighbor_string(int pos, int s)
if (LIBERTY(NORTH(pos))) {
if (!liberties_updated
- && !(STRING_AT_VERTEX(NN(pos), s)
- || STRING_AT_VERTEX(NW(pos), s)
- || STRING_AT_VERTEX(NE(pos), s)))
+ && !NON_NORTH_NEIGHBOR_OF_STRING(NORTH(pos), s, color))
ADD_LIBERTY(s, NORTH(pos));
}
else if (UNMARKED_COLOR_STRING(NORTH(pos), other)) {
@@ -3884,9 +4057,7 @@ extend_neighbor_string(int pos, int s)
if (LIBERTY(EAST(pos))) {
if (!liberties_updated
- && !(STRING_AT_VERTEX(EE(pos), s)
- || STRING_AT_VERTEX(NE(pos), s)
- || STRING_AT_VERTEX(SE(pos), s)))
+ && !NON_EAST_NEIGHBOR_OF_STRING(EAST(pos), s, color))
ADD_LIBERTY(s, EAST(pos));
}
else if (UNMARKED_COLOR_STRING(EAST(pos), other)) {
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [gnugo-devel] fastlib can be faster,
Paul Pogonyshev <=