[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] new cache for readconnect and semeai
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] new cache for readconnect and semeai |
|
Date: |
Sun, 11 Apr 2004 19:15:07 +0200 (CEST) |
- complete conversion to new cache
- add priority to reading results in new cache
- kill unused hash_ng_init()
- minor statistics improvements
Some story about it in a separate mail. The patch causes 2 PASSes and
does save some 1.7% of owl nodes.
I think what remains to do is one more comparison with switching back
to the old cache, deciding to kill the old cache, and doing some
measurements about what to choose as default cache size.
Arend
Index: engine/cache.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.c,v
retrieving revision 1.38
diff -u -p -r1.38 cache.c
--- engine/cache.c 5 Feb 2004 22:54:42 -0000 1.38
+++ engine/cache.c 11 Apr 2004 05:49:02 -0000
@@ -115,7 +115,7 @@ tt_init(Transposition_table *table, int
int num_entries;
/* Make sure the hash system is initialized. */
- hash_ng_init();
+ hash_init();
keyhash_init();
num_entries = memsize / sizeof(Hashentry_ng);
@@ -193,10 +193,8 @@ tt_get(Transposition_table *table,
hashdata_xor(hashval, *extra_hash);
/* Sanity check. */
- if (remaining_depth < 0)
- remaining_depth = 0;
- if (remaining_depth > HN_MAX_REMAINING_DEPTH)
- remaining_depth = HN_MAX_REMAINING_DEPTH;
+ if (remaining_depth < 0 || remaining_depth > HN_MAX_REMAINING_DEPTH)
+ return 0;
/* Get the correct entry and node. */
entry = &table->entries[hashdata_remainder(hashval, table->num_entries)];
@@ -207,17 +205,20 @@ tt_get(Transposition_table *table,
else
return 0;
+ stats.position_hits++;
+
/* Return data. Only set the result if remaining depth in the table
* is big enough to be trusted. The move can always be used for move
* ordering if nothing else.
*/
if (move)
- *move = hn_get_move(*node);
- if ((unsigned) remaining_depth <= hn_get_remaining_depth(*node)) {
+ *move = hn_get_move(node->data);
+ if ((unsigned) remaining_depth <= hn_get_remaining_depth(node->data)) {
if (value1)
- *value1 = hn_get_value1(*node);
+ *value1 = hn_get_value1(node->data);
if (value2)
- *value2 = hn_get_value2(*node);
+ *value2 = hn_get_value2(node->data);
+ stats.read_result_hits++;
return 2;
}
@@ -241,6 +242,9 @@ tt_update(Transposition_table *table,
Hashnode_ng *deepest;
Hashnode_ng *newest;
unsigned int data;
+ /* Get routine costs definitions from cache.h. */
+ static const int routine_costs[] = { ROUTINE_COSTS };
+ gg_assert(routine_costs[NUM_CACHE_ROUTINES] == -1);
/* Get the combined hash value. */
calculate_hashval_for_tt(komaster, kom_pos, routine, target1, target2,
@@ -249,12 +253,11 @@ tt_update(Transposition_table *table,
hashdata_xor(hashval, *extra_hash);
/* Sanity check. */
- if (remaining_depth < 0)
- remaining_depth = 0;
- if (remaining_depth > HN_MAX_REMAINING_DEPTH)
- remaining_depth = HN_MAX_REMAINING_DEPTH;
+ if (remaining_depth < 0 || remaining_depth > HN_MAX_REMAINING_DEPTH)
+ return;
- data = hn_create_data(remaining_depth, value1, value2, move, 0);
+ data = hn_create_data(remaining_depth, value1, value2, move,
+ routine_costs[routine]);
/* Get the entry and nodes. */
entry = &table->entries[hashdata_remainder(hashval, table->num_entries)];
@@ -263,34 +266,32 @@ tt_update(Transposition_table *table,
/* See if we found an already existing node. */
if (hashdata_is_equal(hashval, deepest->key)
- && (unsigned) remaining_depth >= hn_get_remaining_depth(*deepest)) {
-
+ && (unsigned) remaining_depth >= hn_get_remaining_depth(deepest->data)) {
+
/* Found deepest */
deepest->data = data;
-
- }
+
+ }
else if (hashdata_is_equal(hashval, newest->key)
- && (unsigned) remaining_depth >= hn_get_remaining_depth(*newest)) {
-
+ && (unsigned) remaining_depth >=
hn_get_remaining_depth(newest->data)) {
+
/* Found newest */
newest->data = data;
-
+
/* If newest has become deeper than deepest, then switch them. */
- if (hn_get_remaining_depth(*newest) > hn_get_remaining_depth(*deepest)) {
+ if (hn_get_remaining_depth(newest->data)
+ > hn_get_remaining_depth(deepest->data)) {
Hashnode_ng temp;
-
+
temp = *deepest;
*deepest = *newest;
*newest = temp;
}
-
- }
- else if ((unsigned) remaining_depth > hn_get_remaining_depth(*deepest)) {
-
- /* This can only happen if newest is empty. */
- if (hn_get_remaining_depth(*newest) < hn_get_remaining_depth(*deepest))
+
+ }
+ else if (hn_get_total_cost(data) > hn_get_total_cost(deepest->data)) {
+ if (hn_get_total_cost(newest->data) < hn_get_total_cost(deepest->data))
*newest = *deepest;
-
deepest->key = hashval;
deepest->data = data;
}
@@ -300,6 +301,7 @@ tt_update(Transposition_table *table,
newest->data = data;
}
+ stats.position_entered++;
table->is_clean = 0;
}
@@ -909,31 +911,11 @@ hashnode_new_result(Hashtable *table, Ha
void
reading_cache_init(int bytes)
{
- float nodes;
-
#if USE_HASHTABLE_NG
+ tt_init(&ttable, bytes);
+#else
+ float nodes;
- /* Use a majority of the memory for the transposition table because
- * that one is used for the tactical reading. Tests reveal that we
- * use approximately 500 tactical reading nodes for each owl node.
- * This would point to 99.8%, but it is better to have a bit too
- * many owl nodes in the cache than too few.
- *
- * Using 5% for the owl nodes and 95% for the transposition table
- * seems to give a 2% speedup, but this should be better once the
- * owl table is gone and everything is in the new transposition
- * table.
- */
-#define NG_PERCENTAGE 95
- tt_init(&ttable, bytes / 100 * NG_PERCENTAGE);
-
- /* Use the rest of the available memory for the old cache where
- * still owl, semeai and readconnect caching takes place.
- */
- bytes = bytes / 100 * (100 - NG_PERCENTAGE);
-#endif
-
-
/* Initialize hash table.
*
* The number 1.4 below is the quotient between the number of nodes
@@ -958,6 +940,7 @@ reading_cache_init(int bytes)
"Warning: failed to allocate hashtable, caching disabled.\n");
hashflags = HASH_NOTHING;
}
+#endif
}
Index: engine/cache.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.h,v
retrieving revision 1.44
diff -u -p -r1.44 cache.h
--- engine/cache.h 5 Feb 2004 22:54:42 -0000 1.44
+++ engine/cache.h 11 Apr 2004 05:49:02 -0000
@@ -50,11 +50,13 @@
* fields:
*
* RESERVED : 5 bits
- * remaining_depth: 5 bits (depth - stackp) NOTE: HN_MAX_REMAINING_DEPTH
* value1 : 4 bits
* value2 : 4 bits
* move : 10 bits
- * flags : 4 bits
+ * cost : 4 bits
+ * remaining_depth: 5 bits (depth - stackp) NOTE: HN_MAX_REMAINING_DEPTH
+ *
+ * The last 9 bits together give an index for the total costs.
*/
typedef struct {
Hash_data key;
@@ -72,18 +74,19 @@ typedef struct {
} Hashentry_ng;
/* Hn is for hash node. */
-#define hn_get_remaining_depth(hn) (((hn).data >> 22) & 0x1f)
-#define hn_get_value1(hn) (((hn).data >> 18) & 0x0f)
-#define hn_get_value2(hn) (((hn).data >> 14) & 0x0f)
-#define hn_get_move(hn) (((hn).data >> 4) & 0x3ff)
-#define hn_get_flags(hn) (((hn).data >> 0) & 0x0f)
+#define hn_get_value1(hn) ((hn >> 23) & 0x0f)
+#define hn_get_value2(hn) ((hn >> 19) & 0x0f)
+#define hn_get_move(hn) ((hn >> 9) & 0x3ff)
+#define hn_get_cost(hn) ((hn >> 5) & 0x0f)
+#define hn_get_remaining_depth(hn) ((hn >> 0) & 0x1f)
+#define hn_get_total_cost(hn) ((hn >> 0) & 0x1ff)
-#define hn_create_data(remaining_depth, value1, value2, move, flags) \
- (((remaining_depth & 0x1f) << 22) \
- | (((value1) & 0x0f) << 18) \
- | (((value2) & 0x0f) << 14) \
- | (((move) & 0x3ff) << 4) \
- | (((flags) & 0x0f) << 0))
+#define hn_create_data(remaining_depth, value1, value2, move, cost) \
+ ((((value1) & 0x0f) << 23) \
+ | (((value2) & 0x0f) << 19) \
+ | (((move) & 0x3ff) << 9) \
+ | (((cost) & 0x0f) << 5) \
+ | (((remaining_depth & 0x1f) << 0)))
/* Transposition_table: transposition table used for caching. */
Index: engine/genmove.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/genmove.c,v
retrieving revision 1.87
diff -u -p -r1.87 genmove.c
--- engine/genmove.c 10 Apr 2004 14:30:03 -0000 1.87
+++ engine/genmove.c 11 Apr 2004 05:49:03 -0000
@@ -78,7 +78,7 @@ reset_engine()
/* Initialize things for hashing of positions. */
reading_cache_clear();
-
+
hashdata_recalc(&hashdata, board, board_ko_pos);
worms_examined = -1;
@@ -321,18 +321,11 @@ do_genmove(int *move, int color, float p
int save_depth;
start_timer(0);
+ clearstats();
/* Prepare our table of moves considered. */
memset(potential_moves, 0, sizeof(potential_moves));
- /* Reset all the statistics for each move. */
- stats.nodes = 0;
- stats.position_entered = 0;
- stats.position_hits = 0;
- stats.read_result_entered = 0;
- stats.read_result_hits = 0;
- stats.hash_collisions = 0;
-
/* no move is found yet. */
*move = NO_MOVE;
val = -1;
@@ -567,15 +560,9 @@ do_genmove(int *move, int color, float p
}
/* If statistics is turned on, this is the place to show it. */
- if (showstatistics) {
- gprintf("Nodes: %d\n", stats.nodes);
- gprintf("Positions entered: %d\n", stats.position_entered);
- gprintf("Position hits: %d\n", stats.position_hits);
- gprintf("Read results entered: %d\n", stats.read_result_entered);
- gprintf("Read result hits: %d\n", stats.read_result_hits);
- gprintf("Hash collisions: %d\n", stats.hash_collisions);
- }
-
+ if (showstatistics)
+ showstats();
+
if (showtime) {
double spent = time_report(0, "TIME to generate move at ", *move, 1.0);
total_time += spent;
@@ -585,8 +572,6 @@ do_genmove(int *move, int color, float p
slowest_movenum = movenum + 1;
}
}
- if (0 && (debug & DEBUG_BREAKIN))
- print_persistent_breakin_cache();
/* Some consistency checks to verify that things are properly
* restored and/or have not been corrupted.
Index: engine/hash.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.c,v
retrieving revision 1.24
diff -u -p -r1.24 hash.c
--- engine/hash.c 24 Jan 2004 04:04:56 -0000 1.24
+++ engine/hash.c 11 Apr 2004 05:49:04 -0000
@@ -38,59 +38,6 @@
*/
-/* Random values for the hash function. */
-static Hash_data white_hash_ng[BOARDMAX];
-static Hash_data black_hash_ng[BOARDMAX];
-static Hash_data ko_hash_ng[BOARDMAX];
-
-static struct init_struct {
- Hash_data *array;
- int array_size;
-} hash_init_values[] = {
- {white_hash_ng, BOARDMAX},
- {black_hash_ng, BOARDMAX},
- {ko_hash_ng, BOARDMAX}
-};
-
-
-/*
- * Initialize the entire hash and transposition table system.
- *
- * This should only be called once, and before calling any other
- * functions in this file.
- */
-
-void
-hash_ng_init(void)
-{
- static int is_initialized = 0;
- Hash_data *array;
- int size;
- unsigned i;
- int j;
-
- if (is_initialized)
- return;
-
-#if TRACE_READ_RESULTS
- /* We need consistent hash values when this option is enabled. */
- gg_srand(1);
-#endif
-
- for (i = 0;
- i < sizeof(hash_init_values) / sizeof(struct init_struct);
- i++) {
- array = hash_init_values[i].array;
- size = hash_init_values[i].array_size;
-
- for (j = 0; j < size; j++)
- hashdata_init(array[j], gg_urand(), gg_urand());
- }
-
- is_initialized = 1;
-}
-
-
/* ================================================================ */
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.210
diff -u -p -r1.210 liberty.h
--- engine/liberty.h 10 Apr 2004 14:30:03 -0000 1.210
+++ engine/liberty.h 11 Apr 2004 05:49:05 -0000
@@ -45,6 +45,8 @@
void start_timer(int n);
double time_report(int n, const char *occupation, int move, double mintime);
+void showstats(void);
+void clearstats(void);
void transformation_init(void);
@@ -99,6 +101,15 @@ enum routine_id {
"owl_connection_defends", \
"owl_substantial", \
"owl_confirm_safety"
+
+/* To prioritize between different types of reading, we give a cost
+ * ranking to each of the routines above:
+ * 3 for owl, 2 for break-in, 1 for connection, 0 for tactical reading.
+ * -1 is left at the end for a consistency check.
+ */
+#define ROUTINE_COSTS \
+ 3, 3, 3, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, -1
+
const char *routine_id_to_string(enum routine_id routine);
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.202
diff -u -p -r1.202 owl.c
--- engine/owl.c 10 Apr 2004 14:30:03 -0000 1.202
+++ engine/owl.c 11 Apr 2004 05:49:12 -0000
@@ -554,9 +554,6 @@ do_owl_analyze_semeai(int apos, int bpos
const char *best_move_name = NULL;
int this_resulta = -1;
int this_resultb = -1;
-/* FIXME: Temporary measure to turn new cache off for semeai. */
-#undef USE_HASHTABLE_NG
-#define USE_HASHTABLE_NG 0
#if USE_HASHTABLE_NG
int xpos;
int value1;
@@ -584,13 +581,15 @@ do_owl_analyze_semeai(int apos, int bpos
ASSERT1(board[apos] == owla->color, apos);
ASSERT1(board[bpos] == owlb->color, bpos);
+ apos = find_origin(apos);
+ bpos = find_origin(bpos);
#if USE_HASHTABLE_NG
if (stackp <= semeai_branch_depth && (hashflags & HASH_SEMEAI)
&& !pass && owl_phase
&& tt_get(&ttable, komaster, kom_pos, SEMEAI, apos, bpos,
depth - stackp, NULL,
- &value1, &value2, &xpos)) {
+ &value1, &value2, &xpos) == 2) {
/* TRACE_CACHED_RESULT2(*read_result);*/
if (value1 != 0)
*move = xpos;
@@ -1773,9 +1772,6 @@ do_owl_attack(int str, int *move, int *w
struct eyevalue probable_eyes; /* Best guess of eyevalue. */
const char *live_reason;
int move_cutoff;
-/* FIXME: Temporary measure to turn new cache back on for owl. */
-#undef USE_HASHTABLE_NG
-#define USE_HASHTABLE_NG 1
#if USE_HASHTABLE_NG
int xpos;
int value1;
@@ -1790,6 +1786,7 @@ do_owl_attack(int str, int *move, int *w
shape_patterns.initialized = 0;
+ str = find_origin(str);
#if USE_HASHTABLE_NG
if ((hashflags & HASH_OWL_ATTACK)
@@ -2518,6 +2515,7 @@ do_owl_defend(int str, int *move, int *w
shape_patterns.initialized = 0;
+ str = find_origin(str);
#if USE_HASHTABLE_NG
if ((hashflags & HASH_OWL_DEFEND)
@@ -5406,8 +5404,11 @@ owl_find_lunches(struct local_owl_data *
owl->lunch_attack_code[lunches] = acode;
owl->lunch_attack_point[lunches] = apos;
owl->lunch_defend_code[lunches] = dcode;
- if (dcode != 0)
+ ASSERT1(board[apos == EMPTY], lunch);
+ if (dcode != 0) {
owl->lunch_defense_point[lunches] = dpos;
+ ASSERT1(board[apos == EMPTY], lunch);
+ }
else
owl->lunch_defense_point[lunches] = NO_MOVE;
lunches++;
Index: engine/readconnect.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v
retrieving revision 1.72
diff -u -p -r1.72 readconnect.c
--- engine/readconnect.c 6 Apr 2004 19:49:17 -0000 1.72
+++ engine/readconnect.c 11 Apr 2004 05:49:16 -0000
@@ -1939,9 +1939,6 @@ recursive_connect2(int str1, int str2, i
int savemove = NO_MOVE;
int savecode = 0;
int tried_moves = 0;
-/* FIXME: Temporary measure to turn off new cache in readconnect. */
-#undef USE_HASHTABLE_NG
-#define USE_HASHTABLE_NG 0
#if USE_HASHTABLE_NG
int value;
#else
@@ -1977,6 +1974,9 @@ recursive_connect2(int str1, int str2, i
return 0;
}
+ str1 = find_origin(str1);
+ str2 = find_origin(str2);
+
#if USE_HASHTABLE_NG
if (stackp <= depth && (hashflags & HASH_CONNECT)
@@ -2179,6 +2179,9 @@ recursive_disconnect2(int str1, int str2
sgf_dumptree = NULL;
count_variations = 0;
+ str1 = find_origin(str1);
+ str2 = find_origin(str2);
+
attack_code1 = attack(str1, &attack_pos1);
if (attack_code1 == WIN) {
sgf_dumptree = save_sgf_dumptree;
@@ -2898,9 +2901,6 @@ recursive_break(int str, const char goal
int savemove = NO_MOVE;
int savecode = 0;
int tried_moves = 0;
-/* FIXME: Temporary measure to turn new cache back on for break_in. */
-#undef USE_HASHTABLE_NG
-#define USE_HASHTABLE_NG 1
#if USE_HASHTABLE_NG
int retval;
#else
Index: engine/utils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v
retrieving revision 1.87
diff -u -p -r1.87 utils.c
--- engine/utils.c 24 Jan 2004 04:04:56 -0000 1.87
+++ engine/utils.c 11 Apr 2004 05:49:24 -0000
@@ -2323,6 +2323,28 @@ time_report(int n, const char *occupatio
return dt;
}
+void
+clearstats()
+{
+ stats.nodes = 0;
+ stats.position_entered = 0;
+ stats.position_hits = 0;
+ stats.read_result_entered = 0;
+ stats.read_result_hits = 0;
+ stats.hash_collisions = 0;
+}
+
+void
+showstats()
+{
+ gprintf("Nodes: %d\n", stats.nodes);
+ gprintf("Positions entered: %d\n", stats.position_entered);
+ gprintf("Position hits: %d\n", stats.position_hits);
+ gprintf("Read results entered: %d\n", stats.read_result_entered);
+ gprintf("Read result hits: %d\n", stats.read_result_hits);
+ gprintf("Hash collisions: %d\n", stats.hash_collisions);
+}
+
/*
* Local Variables:
Index: interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.142
diff -u -p -r1.142 play_gtp.c
--- interface/play_gtp.c 24 Jan 2004 04:04:56 -0000 1.142
+++ interface/play_gtp.c 11 Apr 2004 05:49:27 -0000
@@ -349,7 +349,10 @@ play_gtp(FILE *gtp_input, FILE *gtp_dump
/* Prepare pattern matcher and reading code. */
reset_engine();
+ clearstats();
gtp_main_loop(commands, gtp_input, gtp_dump_commands);
+ if (showstatistics)
+ showstats();
}
- [gnugo-devel] new cache for readconnect and semeai,
Arend Bayer <=