[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] MAX_LIBERTIES
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] MAX_LIBERTIES |
|
Date: |
Tue, 16 Nov 2004 20:31:18 +0100 (CET) |
Triggered by Anders Kierulf's remark on MAX_LIBERTIES, I tried two
things: Reducing it (to improve cache locality), or removing it (thus
simplifying the code and removing a lot of branches).
Reducing it to 8 gave a speedup of almost 1%. Removing it (as in the
preliminary patch below) cost about 0.1% compared to the current
situation.
So question: Do we rather want slightly easier code or 1% performance
gain?
Arend
Index: engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.103
diff -u -p -r1.103 board.c
--- engine/board.c 13 Nov 2004 04:46:43 -0000 1.103
+++ engine/board.c 16 Nov 2004 19:33:12 -0000
@@ -247,15 +247,13 @@ static int next_stone[BOARDMAX];
#define ADD_LIBERTY(s, pos)\
do {\
- if (string[s].liberties < MAX_LIBERTIES)\
- string[s].libs[string[s].liberties] = pos;\
+ string[s].libs[string[s].liberties] = pos;\
string[s].liberties++;\
} while (0)
#define ADD_AND_MARK_LIBERTY(s, pos)\
do {\
- if (string[s].liberties < MAX_LIBERTIES)\
- string[s].libs[string[s].liberties] = pos;\
+ string[s].libs[string[s].liberties] = pos;\
string[s].liberties++;\
ml[pos] = liberty_mark;\
} while (0)
@@ -1403,63 +1401,17 @@ findlib(int str, int maxlib, int *libs)
/* We already have the list of liberties and only need to copy it to
* libs[].
- *
- * However, if the string has more than MAX_LIBERTIES liberties the
- * list is truncated and if maxlib is also larger than MAX_LIBERTIES
- * we have to traverse the stones in the string in order to find
- * where the liberties are.
*/
s = string_number[str];
liberties = string[s].liberties;
+ maxlib = gg_min(liberties, maxlib);
- if (liberties <= MAX_LIBERTIES || maxlib <= MAX_LIBERTIES) {
- /* The easy case, it suffices to copy liberty locations from the
- * incrementally updated list.
- */
- for (k = 0; k < maxlib && k < liberties; k++)
- libs[k] = string[s].libs[k];
- }
- else {
- /* The harder case, where we have to traverse the stones in the
- * string. We don't have to check explicitly if we are back to
- * the start of the chain since we will run out of liberties
- * before that happens.
- */
- int pos;
- liberty_mark++;
- for (k = 0, pos = FIRST_STONE(s);
- k < maxlib && k < liberties;
- pos = NEXT_STONE(pos)) {
- if (UNMARKED_LIBERTY(SOUTH(pos))) {
- libs[k++] = SOUTH(pos);
- MARK_LIBERTY(SOUTH(pos));
- if (k >= maxlib)
- break;
- }
-
- if (UNMARKED_LIBERTY(WEST(pos))) {
- libs[k++] = WEST(pos);
- MARK_LIBERTY(WEST(pos));
- if (k >= maxlib)
- break;
- }
-
- if (UNMARKED_LIBERTY(NORTH(pos))) {
- libs[k++] = NORTH(pos);
- MARK_LIBERTY(NORTH(pos));
- if (k >= maxlib)
- break;
- }
-
- if (UNMARKED_LIBERTY(EAST(pos))) {
- libs[k++] = EAST(pos);
- MARK_LIBERTY(EAST(pos));
- if (k >= maxlib)
- break;
- }
- }
- }
-
+ /* The easy case, it suffices to copy liberty locations from the
+ * incrementally updated list.
+ */
+ for (k = 0; k < maxlib; k++)
+ libs[k] = string[s].libs[k];
+
return liberties;
}
@@ -1708,10 +1660,7 @@ approxlib(int pos, int color, int maxlib
*/
entry->threshold = maxlib;
- if (maxlib <= MAX_LIBERTIES)
- liberties = do_approxlib(pos, color, maxlib, libs);
- else
- liberties = slow_approxlib(pos, color, maxlib, libs);
+ liberties = do_approxlib(pos, color, maxlib, libs);
entry->liberties = liberties;
entry->position_hash = board_hash;
@@ -1727,10 +1676,7 @@ approxlib(int pos, int color, int maxlib
return liberties;
}
- if (maxlib <= MAX_LIBERTIES)
- liberties = do_approxlib(pos, color, maxlib, libs);
- else
- liberties = slow_approxlib(pos, color, maxlib, libs);
+ liberties = do_approxlib(pos, color, maxlib, libs);
#endif /* not USE_BOARD_CACHES */
@@ -1746,14 +1692,9 @@ do_approxlib(int pos, int color, int max
int liberties = 0;
/* Look for empty neighbors and the liberties of the adjacent
- * strings of the given color. The algorithm below won't work
- * correctly if any of the adjacent strings have more than
- * MAX_LIBERTIES liberties AND maxlib is larger than MAX_LIBERTIES.
- * therefore approxlib() calls more robust slow_approxlib() if
- * this might be the case.
- */
-
- /* Start by marking pos itself so it isn't counted among its own
+ * strings of the given color.
+ *
+ * Start by marking pos itself so it isn't counted among its own
* liberties.
*/
liberty_mark++;
@@ -2058,76 +1999,21 @@ do_accuratelib(int pos, int color, int m
/* An own neighbor string */
struct string_data *s = &string[string_number[pos2]];
- if (s->liberties <= MAX_LIBERTIES || maxlib <= MAX_LIBERTIES - 1) {
- /* The easy case - we already have all (necessary) liberties of
- * the string listed
- */
- for (l = 0; l < s->liberties; l++) {
- lib = s->libs[l];
- if (UNMARKED_LIBERTY(lib)) {
- if (libs)
- libs[liberties] = lib;
- liberties++;
- if (liberties >= maxlib)
- return liberties;
+ /* The easy case - we already have all (necessary) liberties of
+ * the string listed
+ */
+ for (l = 0; l < s->liberties; l++) {
+ lib = s->libs[l];
+ if (UNMARKED_LIBERTY(lib)) {
+ if (libs)
+ libs[liberties] = lib;
+ liberties++;
+ if (liberties >= maxlib)
+ return liberties;
- MARK_LIBERTY(lib);
- }
+ MARK_LIBERTY(lib);
}
}
- else {
- /* The harder case - we need to find all the liberties of the
- * string by traversing its stones. We stop as soon as we have
- * traversed all the stones or have reached maxlib. Unfortunately,
- * we cannot use the trick from findlib() since some of the
- * liberties may already have been marked.
- */
- int stone = pos2;
- do {
- if (UNMARKED_LIBERTY(SOUTH(stone))) {
- if (libs)
- libs[liberties] = SOUTH(stone);
- liberties++;
- if (liberties >= maxlib)
- return liberties;
-
- MARK_LIBERTY(SOUTH(stone));
- }
-
- if (UNMARKED_LIBERTY(WEST(stone))) {
- if (libs)
- libs[liberties] = WEST(stone);
- liberties++;
- if (liberties >= maxlib)
- return liberties;
-
- MARK_LIBERTY(WEST(stone));
- }
-
- if (UNMARKED_LIBERTY(NORTH(stone))) {
- if (libs)
- libs[liberties] = NORTH(stone);
- liberties++;
- if (liberties >= maxlib)
- return liberties;
-
- MARK_LIBERTY(NORTH(stone));
- }
-
- if (UNMARKED_LIBERTY(EAST(stone))) {
- if (libs)
- libs[liberties] = EAST(stone);
- liberties++;
- if (liberties >= maxlib)
- return liberties;
-
- MARK_LIBERTY(EAST(stone));
- }
-
- stone = NEXT_STONE(stone);
- } while (stone != pos2);
- }
-
MARK_STRING(pos2);
}
else if (board[pos2] == OTHER_COLOR(color)
@@ -2193,7 +2079,7 @@ do_accuratelib(int pos, int color, int m
int
count_common_libs(int str1, int str2)
{
- int all_libs1[MAXLIBS], *libs1;
+ int *libs1;
int liberties1, liberties2;
int commonlibs = 0;
int k, n, tmp;
@@ -2214,36 +2100,22 @@ count_common_libs(int str1, int str2)
str2 = tmp;
}
- if (liberties1 <= MAX_LIBERTIES) {
- /* Speed optimization: don't copy liberties with findlib */
- libs1 = string[n].libs;
- n = string_number[str2];
- liberties2 = string[n].liberties;
-
- if (liberties2 <= MAX_LIBERTIES) {
- /* Speed optimization: NEIGHBOR_OF_STRING is quite expensive */
- liberty_mark++;
-
- for (k = 0; k < liberties1; k++)
- MARK_LIBERTY(libs1[k]);
-
- libs1 = string[n].libs;
- for (k = 0; k < liberties2; k++)
- if (!UNMARKED_LIBERTY(libs1[k]))
- commonlibs++;
-
- return commonlibs;
- }
- }
- else {
- findlib(str1, MAXLIBS, all_libs1);
- libs1 = all_libs1;
- }
+ /* Speed optimization: don't copy liberties with findlib */
+ libs1 = string[n].libs;
+ n = string_number[str2];
+ liberties2 = string[n].liberties;
+
+ /* Speed optimization: NEIGHBOR_OF_STRING is quite expensive */
+ liberty_mark++;
for (k = 0; k < liberties1; k++)
- if (NEIGHBOR_OF_STRING(libs1[k], string_number[str2], board[str2]))
+ MARK_LIBERTY(libs1[k]);
+
+ libs1 = string[n].libs;
+ for (k = 0; k < liberties2; k++)
+ if (!UNMARKED_LIBERTY(libs1[k]))
commonlibs++;
-
+
return commonlibs;
}
@@ -2260,7 +2132,7 @@ count_common_libs(int str1, int str2)
int
find_common_libs(int str1, int str2, int maxlib, int *libs)
{
- int all_libs1[MAXLIBS], *libs1;
+ int *libs1;
int liberties1, liberties2;
int commonlibs = 0;
int k, n, tmp;
@@ -2282,37 +2154,20 @@ find_common_libs(int str1, int str2, int
str2 = tmp;
}
- if (liberties1 <= MAX_LIBERTIES) {
- /* Speed optimization: don't copy liberties with findlib */
- libs1 = string[n].libs;
- n = string_number[str2];
- liberties2 = string[n].liberties;
+ /* Speed optimization: don't copy liberties with findlib */
+ libs1 = string[n].libs;
+ n = string_number[str2];
+ liberties2 = string[n].liberties;
- if (liberties2 <= MAX_LIBERTIES) {
- /* Speed optimization: NEIGHBOR_OF_STRING is quite expensive */
- liberty_mark++;
+ /* Speed optimization: NEIGHBOR_OF_STRING is quite expensive */
+ liberty_mark++;
- for (k = 0; k < liberties1; k++)
- MARK_LIBERTY(libs1[k]);
-
- libs1 = string[n].libs;
- for (k = 0; k < liberties2; k++)
- if (!UNMARKED_LIBERTY(libs1[k])) {
- if (commonlibs < maxlib)
- libs[commonlibs] = libs1[k];
- commonlibs++;
- }
-
- return commonlibs;
- }
- }
- else {
- findlib(str1, MAXLIBS, all_libs1);
- libs1 = all_libs1;
- }
-
for (k = 0; k < liberties1; k++)
- if (NEIGHBOR_OF_STRING(libs1[k], string_number[str2], board[str2])) {
+ MARK_LIBERTY(libs1[k]);
+
+ libs1 = string[n].libs;
+ for (k = 0; k < liberties2; k++)
+ if (!UNMARKED_LIBERTY(libs1[k])) {
if (commonlibs < maxlib)
libs[commonlibs] = libs1[k];
commonlibs++;
@@ -2328,7 +2183,7 @@ find_common_libs(int str1, int str2, int
int
have_common_lib(int str1, int str2, int *lib)
{
- int all_libs1[MAXLIBS], *libs1;
+ int *libs1;
int liberties1;
int k, n, tmp;
@@ -2348,13 +2203,8 @@ have_common_lib(int str1, int str2, int
str2 = tmp;
}
- if (liberties1 <= MAX_LIBERTIES)
- /* Speed optimization: don't copy liberties with findlib */
- libs1 = string[n].libs;
- else {
- findlib(str1, MAXLIBS, all_libs1);
- libs1 = all_libs1;
- }
+ /* Speed optimization: don't copy liberties with findlib */
+ libs1 = string[n].libs;
for (k = 0; k < liberties1; k++) {
if (NEIGHBOR_OF_STRING(libs1[k], string_number[str2], board[str2])) {
@@ -3262,7 +3112,7 @@ update_liberties(int s)
/* Push the old information. */
PUSH_VALUE(string[s].liberties);
- for (k = 0; k < string[s].liberties && k < MAX_LIBERTIES; k++) {
+ for (k = 0; k < string[s].liberties; k++) {
PUSH_VALUE(string[s].libs[k]);
}
string[s].liberties = 0;
@@ -3335,22 +3185,18 @@ remove_liberty(int str_number, int pos)
int k;
struct string_data *s = &string[str_number];
- if (s->liberties > MAX_LIBERTIES)
- update_liberties(str_number);
- else {
- for (k = 0; k < s->liberties; k++)
- if (s->libs[k] == pos) {
- /* We need to push the last entry too because it may become
- * destroyed later.
- */
- PUSH_VALUE(s->libs[s->liberties - 1]);
- PUSH_VALUE(s->libs[k]);
- PUSH_VALUE(s->liberties);
- s->libs[k] = s->libs[s->liberties - 1];
- s->liberties--;
- break;
- }
- }
+ for (k = 0; k < s->liberties; k++)
+ if (s->libs[k] == pos) {
+ /* We need to push the last entry too because it may become
+ * destroyed later.
+ */
+ PUSH_VALUE(s->libs[s->liberties - 1]);
+ PUSH_VALUE(s->libs[k]);
+ PUSH_VALUE(s->liberties);
+ s->libs[k] = s->libs[s->liberties - 1];
+ s->liberties--;
+ break;
+ }
}
@@ -3387,8 +3233,7 @@ do_remove_string(int s)
remove_neighbor(neighbor, s);
PUSH_VALUE(string[neighbor].liberties);
- if (string[neighbor].liberties < MAX_LIBERTIES)
- string[neighbor].libs[string[neighbor].liberties] = pos;
+ string[neighbor].libs[string[neighbor].liberties] = pos;
string[neighbor].liberties++;
}
}
@@ -3403,14 +3248,12 @@ do_remove_string(int s)
PUSH_VALUE(string[neighbor].liberties);
if (NEIGHBOR_OF_STRING(pos, neighbor, other)) {
- if (string[neighbor].liberties < MAX_LIBERTIES)
- string[neighbor].libs[string[neighbor].liberties] = pos;
+ string[neighbor].libs[string[neighbor].liberties] = pos;
string[neighbor].liberties++;
}
if (NEIGHBOR_OF_STRING(pos2, neighbor, other)) {
- if (string[neighbor].liberties < MAX_LIBERTIES)
- string[neighbor].libs[string[neighbor].liberties] = pos2;
+ string[neighbor].libs[string[neighbor].liberties] = pos2;
string[neighbor].liberties++;
}
}
@@ -3551,19 +3394,8 @@ extend_neighbor_string(int pos, int s)
PUSH_VALUE(string[s].size);
string[s].size++;
- /* If s has too many liberties, we don't know where they all are and
- * can't update the liberties with the algorithm we otherwise
- * use. In that case we can only recompute the liberties from
- * scratch.
- */
- if (string[s].liberties > MAX_LIBERTIES) {
- update_liberties(s);
- liberties_updated = 1;
- }
- else {
- /* The place of the new stone is no longer a liberty. */
- remove_liberty(s, pos);
- }
+ /* The place of the new stone is no longer a liberty. */
+ remove_liberty(s, pos);
/* Mark old neighbors of the string. */
string_mark++;
@@ -3677,27 +3509,12 @@ assimilate_string(int s, int pos)
* It is assumed that the liberties of s have been marked before
* this function is called.
*/
- if (string[s2].liberties <= MAX_LIBERTIES) {
- for (k = 0; k < string[s2].liberties; k++) {
- int pos2 = string[s2].libs[k];
- if (UNMARKED_LIBERTY(pos2)) {
- ADD_AND_MARK_LIBERTY(s, pos2);
- }
+ for (k = 0; k < string[s2].liberties; k++) {
+ int pos2 = string[s2].libs[k];
+ if (UNMARKED_LIBERTY(pos2)) {
+ ADD_AND_MARK_LIBERTY(s, pos2);
}
}
- else {
- /* If s2 had too many liberties the above strategy wouldn't be
- * effective, since not all liberties are listed in
- * libs[] the chain of stones for s2 is no
- * longer available (it has already been merged with s) so we
- * can't reconstruct the s2 liberties. Instead we capitulate and
- * rebuild the list of liberties for s (including the neighbor
- * strings assimilated so far) from scratch.
- */
- liberty_mark++; /* Reset the mark. */
- string[s].liberties = 0; /* To avoid pushing the current list. */
- update_liberties(s);
- }
/* Remove s2 as neighbor to the neighbors of s2 and instead add s if
* they don't already have added it. Also add the neighbors of s2 as
Index: engine/board.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.h,v
retrieving revision 1.17
diff -u -p -r1.17 board.h
--- engine/board.h 13 Nov 2004 04:46:43 -0000 1.17
+++ engine/board.h 16 Nov 2004 19:33:12 -0000
@@ -43,7 +43,7 @@
*/
#define MAXLIBS (2*(MAX_BOARD*MAX_BOARD + 1)/3)
/* This is a smaller, practical number of liberties that we care to keep track
of. */
-#define MAX_LIBERTIES 20
+#define MAX_LIBERTIES MAXLIBS
/* This is an upper bound of the number of strings that can exist on
- [gnugo-devel] MAX_LIBERTIES,
Arend Bayer <=