[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] hash_1_28.4: revision of hash_1_28.3
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] hash_1_28.4: revision of hash_1_28.3 |
|
Date: |
Sat, 23 Mar 2002 23:30:28 +0100 (CET) |
- hashing dependent on compiler switches, default 64 bit and no full position
- default cache size set to 8
So here is the revision of the hashing patches. Its tested rather extensively
(but not with full regressions).
The two compiler switches are NUM_HASHVALUES and FULL_POSITION_IN_HASH.
NUM_HASHVALUES can be set indirectly by specifying MIN_HASHBITS, which
is preferable to get more consistent behaviour between 32/64 bit machines.
(Just to check: Am I right asuming that "sizeof(long) == sizeof(unsigned long)"
on all systems?)
I first considered setting the minimum number of hash bits to 96. But I did
not get a single mistake/assertion failure when running "make second_batch"
with 32 bit hashing. So this suggests that we would get far less than one
mistake per game with 32 bit hashing (note that a hash collision does not
at all imply a wrong read result lookup yet: the routine, the string in
question and stackp have to agree as well). So with 64 bits, we should get
less than one mistake per 10^10 games (if we trust the random generator).
However, if we use 96 bits instead of 64, that costs only 5% of memory (I
have not measured the performance loss).
With 96 bits, I measured a 4.5% speed improvement for nngs.tst compared
to the old hashing. This was almost the same with 8MB instead of 16 MB
cache size (in fact, 8MB was minimally faster), so I suggest to reduce
the default to 8.
Dan, if you want to play safe and stick with the old hashing, change
HASHING_SCHEME to 1 in hash.h and ignore the cache size part.
To reduce the drawback of the probabilistic approach, I can promise to
make sure we have the random seed in crash reports before 3.2. This should
be useful in any case.
Arend
Index: configure
===================================================================
RCS file: /cvsroot/gnugo/gnugo/configure,v
retrieving revision 1.43
diff -u -r1.43 configure
--- configure 4 Mar 2002 06:49:07 -0000 1.43
+++ configure 23 Mar 2002 22:08:16 -0000
@@ -677,7 +677,7 @@
--enable-grid-opt enable the grid optimsation within the pattern
matcher (default)
--enable-grid-opt=distrust enable the grid optimsation in non-trusting mode
--disable-grid-opt disable the grid optimisation
- --enable-cache-size=n reserve n Mb RAM for caching (16 default)
+ --enable-cache-size=n reserve n Mb RAM for caching (8 default)
--enable-level=n n = default level (8 standard, up to 10 supported)
--enable-semeai-variations=n n = semeai variations (250 standard)
--disable-dfa use old non-dfa pattern matcher
@@ -1358,7 +1358,7 @@
fi;
-default_cache_size=16
+default_cache_size=8
default_level=10
default_semeai_variations=250
Index: configure.in
===================================================================
RCS file: /cvsroot/gnugo/gnugo/configure.in,v
retrieving revision 1.41
diff -u -r1.41 configure.in
--- configure.in 1 Mar 2002 14:54:31 -0000 1.41
+++ configure.in 23 Mar 2002 22:08:18 -0000
@@ -43,7 +43,7 @@
--enable-grid-opt=distrust enable the grid optimsation in non-trusting mode
--disable-grid-opt disable the grid optimisation])
-default_cache_size=16
+default_cache_size=8
default_level=10
default_semeai_variations=250
Index: engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.42
diff -u -r1.42 board.c
--- engine/board.c 22 Mar 2002 08:18:32 -0000 1.42
+++ engine/board.c 23 Mar 2002 22:08:32 -0000
@@ -496,25 +496,25 @@
if (str == NO_MOVE) {
if (!komaster_is_empty(komaster, kom_pos))
gg_snprintf(buf, 100, "%s (variation %d, hash %lx, komaster %s:%s)",
- message, count_variations, hashdata.hashval,
+ message, count_variations, hashdata.hashval[0],
komaster_to_string(komaster, kom_pos),
location_to_string(kom_pos));
else
gg_snprintf(buf, 100, "%s (variation %d, hash %lx)",
- message, count_variations, hashdata.hashval);
+ message, count_variations, hashdata.hashval[0]);
}
else {
if (!komaster_is_empty(komaster, kom_pos))
gg_snprintf(buf, 100,
"%s at %s (variation %d, hash %lx, komaster %s:%s)",
message, location_to_string(str), count_variations,
- hashdata.hashval,
+ hashdata.hashval[0],
komaster_to_string(komaster, kom_pos),
location_to_string(kom_pos));
else
gg_snprintf(buf, 100, "%s at %s (variation %d, hash %lx)",
message, location_to_string(str), count_variations,
- hashdata.hashval);
+ hashdata.hashval[0]);
}
sgftreeAddPlayLast(sgf_dumptree, NULL, color, I(pos), J(pos));
sgftreeAddComment(sgf_dumptree, NULL, buf);
@@ -597,12 +597,12 @@
message = "UNKNOWN";
if (!komaster_is_empty(komaster, kom_pos))
gg_snprintf(buf, 100, "tryko: %s (variation %d, %lx, komaster %s:%s)",
- message, count_variations, hashdata.hashval,
+ message, count_variations, hashdata.hashval[0],
komaster_to_string(komaster, kom_pos),
location_to_string(kom_pos));
else
gg_snprintf(buf, 100, "tryko: %s (variation %d, %lx)",
- message, count_variations, hashdata.hashval);
+ message, count_variations, hashdata.hashval[0]);
if (0) {
/* tm - I don't find these pass moves helpful in the tree. */
sgftreeAddPlayLast(sgf_dumptree, NULL, color, -1, -1);
@@ -715,8 +715,9 @@
PUSH_VALUE(board_ko_pos);
memcpy(&hashdata_stack[stackp], &hashdata, sizeof(hashdata));
- board_ko_pos = 0;
- hashdata_remove_ko(&hashdata);
+ if (board_ko_pos != NO_MOVE)
+ hashdata_invert_ko(&hashdata, board_ko_pos);
+ board_ko_pos = NO_MOVE;
PUSH_VALUE(black_captured);
PUSH_VALUE(white_captured);
@@ -817,7 +818,7 @@
if (count_variations)
gprintf("%o (variation %d)", count_variations-1);
#else
- gprintf("%o (%d)", hashdata.hashval);
+ gprintf("%o (%d)", hashdata.hashval[0]);
#endif
gprintf("%o\n");
@@ -884,11 +885,16 @@
/* Check the hash table to see if it corresponds to the cumulative one. */
hashdata_recalc(&oldkey, board, board_ko_pos);
+#if FULL_POSITION_IN_HASH
gg_assert(hashdata_diff_dump(&oldkey, &hashdata) == 0);
+#else
+ gg_assert(hashdata_compare(&oldkey, &hashdata) == 0);
+#endif
#endif
+ if (board_ko_pos != NO_MOVE)
+ hashdata_invert_ko(&hashdata, board_ko_pos);
board_ko_pos = NO_MOVE;
- hashdata_remove_ko(&hashdata);
/* If the move is a pass, we can skip some steps. */
if (pos != PASS_MOVE) {
@@ -901,7 +907,11 @@
#if CHECK_HASHING
/* Check the hash table to see if it equals the previous one. */
hashdata_recalc(&oldkey, board, board_ko_pos);
+#if FULL_POSITION_IN_HASH
gg_assert(hashdata_diff_dump(&oldkey, &hashdata) == 0);
+#else
+ gg_assert(hashdata_compare(&oldkey, &hashdata) == 0);
+#endif
#endif
}
new_position();
@@ -3759,8 +3769,11 @@
if (string[s].liberties == 1
&& string[s].size == 1
&& captured_stones == 1) {
+ /* In case of a double ko: clear old ko position first. */
+ if (board_ko_pos != NO_MOVE)
+ hashdata_invert_ko(&hashdata, board_ko_pos);
board_ko_pos = string[s].libs[0];
- hashdata_set_ko(&hashdata, board_ko_pos);
+ hashdata_invert_ko(&hashdata, board_ko_pos);
}
}
Index: engine/cache.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.c,v
retrieving revision 1.11
diff -u -r1.11 cache.c
--- engine/cache.c 4 Mar 2002 06:49:08 -0000 1.11
+++ engine/cache.c 23 Mar 2002 22:08:35 -0000
@@ -93,7 +93,9 @@
/* Data about the node itself. */
fprintf(outfile, "Hash value: %lx\n", (unsigned long) node->key.hashval);
+#if FULL_POSITION_IN_HASH
hashposition_dump(&(node->key.hashpos), outfile);
+#endif
for (result = node->results; result != NULL; result = result->next) {
read_result_dump(result, outfile);
@@ -367,7 +369,7 @@
*/
for (k = 0; k < table->num_nodes; k++) {
node = &(table->all_nodes[k]);
- bucket = node->key.hashval % table->hashtablesize;
+ bucket = node->key.hashval[0] % table->hashtablesize;
previous = NULL;
current = table->hashtable[bucket];
@@ -469,7 +471,7 @@
node->results = NULL;
/* ...and enter it into the table. */
- bucket = hd->hashval % table->hashtablesize;
+ bucket = hd->hashval[0] % table->hashtablesize;
node->next = table->hashtable[bucket];
table->hashtable[bucket] = node;
@@ -493,13 +495,24 @@
{
Hashnode *node;
int bucket;
+ int i;
- bucket = hd->hashval % table->hashtablesize;
+ bucket = hd->hashval[0] % table->hashtablesize;
for (node = table->hashtable[bucket]; node != NULL; node = node->next) {
- if (node->key.hashval != hd->hashval)
+ if (node->key.hashval[0] != hd->hashval[0])
continue;
- if (hashposition_compare(&hd->hashpos, &node->key.hashpos) == 0)
+ for (i = 1; i < NUM_HASHVALUES; i++)
+ if (node->key.hashval[i] != hd->hashval[i]) {
+ stats.hash_collisions++;
+ break;
+ }
+ if (i >= NUM_HASHVALUES)
+#if FULL_POSITION_IN_HASH
+ if (hashposition_compare(&hd->hashpos, &node->key.hashpos) == 0)
+ break;
+#else
break;
+#endif
}
return node;
}
@@ -589,6 +602,8 @@
/ (1.5 * sizeof(Hashnode *)
+ sizeof(Hashnode)
+ 1.4 * sizeof(Read_result)));
+ if (0)
+ gprintf("Allocated memory for %d hash nodes. \n", (int) nodes);
/* If we get a zero size hash table, disable hashing completely. */
if (nodes < 1.0)
hashflags = HASH_NOTHING;
@@ -691,7 +706,11 @@
/* Check the hash table to see if we have had this position before. */
hashdata_recalc(&key, board, board_ko_pos);
+#if FULL_POSITION_IN_HASH
gg_assert(hashdata_diff_dump(&key, &hashdata) == 0);
+#else
+ gg_assert(hashdata_compare(&key, &hashdata) == 0);
+#endif
/* Find this position in the table. If it wasn't found, enter it. */
hashnode = hashtable_search(movehash, &hashdata);
Index: engine/hash.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.c,v
retrieving revision 1.11
diff -u -r1.11 hash.c
--- engine/hash.c 22 Mar 2002 08:18:32 -0000 1.11
+++ engine/hash.c 23 Mar 2002 22:08:37 -0000
@@ -40,15 +40,15 @@
static int is_initialized = 0;
-
/* Random values for the hash function. For stones and ko position. */
-static Hashvalue white_hash[BOARDMAX];
-static Hashvalue black_hash[BOARDMAX];
-static Hashvalue ko_hash[BOARDMAX];
-
+static Hashvalue white_hash[BOARDMAX][NUM_HASHVALUES];
+static Hashvalue black_hash[BOARDMAX][NUM_HASHVALUES];
+static Hashvalue ko_hash[BOARDMAX][NUM_HASHVALUES];
+#if FULL_POSITION_IN_HASH
static Compacttype white_patterns[4 * sizeof(Compacttype)];
static Compacttype black_patterns[4 * sizeof(Compacttype)];
+#endif
/* Get a random Hashvalue, where all bits are used. */
@@ -73,8 +73,11 @@
hash_init(void)
{
int pos;
- int x;
+ int i;
struct gg_rand_state state;
+#if FULL_POSITION_IN_HASH
+ int x;
+#endif
if (is_initialized)
return;
@@ -90,15 +93,17 @@
gg_srand(1);
#endif
- for (pos = BOARDMIN; pos < BOARDMAX; pos++)
- if (ON_BOARD(pos)) {
- black_hash[pos] = hash_rand();
- white_hash[pos] = hash_rand();
- ko_hash[pos] = hash_rand();
- }
-
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+ if (ON_BOARD(pos)) {
+ black_hash[pos][i] = hash_rand();
+ white_hash[pos][i] = hash_rand();
+ ko_hash[pos][i] = hash_rand();
+ }
+
gg_set_rand_state(&state);
+#if FULL_POSITION_IN_HASH
{
Compacttype mask;
@@ -107,6 +112,7 @@
black_patterns[x] = mask << 1;
}
}
+#endif
is_initialized = 1;
}
@@ -120,6 +126,7 @@
* which are used e.g. by the comparison functions used in qsort().
*/
+#if FULL_POSITION_IN_HASH
int
hashposition_compare(Hashposition *pos1, Hashposition *pos2)
{
@@ -160,12 +167,13 @@
else
gfprintf(outfile, " Ko position: %1m", pos->ko_pos);
}
+#endif /* FULL_POSITION_IN_HASH */
/* ---------------------------------------------------------------- */
-/* Calculate the compactboard and the hashvalue in one function.
+/* Calculate the compactboard and the hashvalues in one function.
* They are always used together and it saves us a loop and a function
* call.
*/
@@ -173,50 +181,50 @@
void
hashdata_recalc(Hash_data *target, Intersection *p, int ko_pos)
{
- /* USE_SHIFTING is a (CPU dependent?) optimization.
- * The theory behind it is that shifting is relatively cheap.
- * Referencing a precomputed array uses the bus, and might consume
- * a cacheslot.
- *
- * FIXME: Do some more measuring.
- * Here is the result so far:
- * Platform Speedup (comparing SHIFT to TABLE)
- * ------------------------------------------------
- * Intel PII 2-3% of total run-time
- * SPARC ???
- */
-
-#define USE_SHIFTING 1
-#if USE_SHIFTING
+#if FULL_POSITION_IN_HASH
unsigned int index;
- int pos;
Compacttype bits;
+#endif
+ int pos;
+ int i;
- target->hashval = 0;
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ target->hashval[i] = 0;
+#if FULL_POSITION_IN_HASH
bits = 1;
index = 0;
target->hashpos.board[index] = 0;
+#endif
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos))
continue;
switch (p[pos]) {
default:
case EMPTY:
+#if FULL_POSITION_IN_HASH
bits <<= 2;
+#endif
break;
case WHITE:
- target->hashval ^= white_hash[pos];
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ target->hashval[i] ^= white_hash[pos][i];
+#if FULL_POSITION_IN_HASH
target->hashpos.board[index] |= bits;
bits <<= 2;
+#endif
break;
case BLACK:
- target->hashval ^= black_hash[pos];
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ target->hashval[i] ^= black_hash[pos][i];
+#if FULL_POSITION_IN_HASH
bits <<= 1;
target->hashpos.board[index] |= bits;
bits <<= 1;
+#endif
break;
}
+#if FULL_POSITION_IN_HASH
if (!bits) {
/* This means the bit fell off the left side. */
bits = 1;
@@ -224,85 +232,43 @@
if (index < COMPACT_BOARD_SIZE)
target->hashpos.board[index] = 0;
}
+#endif
}
/* This cleans up garbage bits at the (unused) end of the array.
* It probably should not really be necessary.
*/
+#if FULL_POSITION_IN_HASH
while (++index < COMPACT_BOARD_SIZE)
target->hashpos.board[index] = 0;
-
-#else /* USE_SHIFTING */
-
- int index;
- int subindex;
- int pos;
- Compacttype bits;
-
- target->hashval = 0;
- index = 0;
- subindex = 0;
- bits = 0;
- for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
- if (!ON_BOARD(pos))
- continue;
- switch (p[pos]) {
- default:
- case EMPTY:
- break;
- case WHITE:
- target->hashval ^= white_hash[pos];
- bits |= white_patterns[subindex];
- break;
- case BLACK:
- target->hashval ^= black_hash[pos];
- bits |= black_patterns[subindex];
- break;
- }
-
- if (++subindex == POINTSPERCOMPACT) {
- target->hashpos.board[index++] = bits;
- bits = 0;
- subindex = 0;
- }
- }
-
- if (subindex != 0)
- target->hashpos.board[index] = bits;
-#endif /* USE_SHIFTING */
+#endif
if (ko_pos != 0)
- target->hashval ^= ko_hash[ko_pos];
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ target->hashval[i] ^= ko_hash[ko_pos][i];
+#if FULL_POSITION_IN_HASH
target->hashpos.ko_pos = ko_pos;
+#endif
}
/*
- * Set ko in the hash value and hash position.
+ * Set or remove ko in the hash value and hash position.
*/
void
-hashdata_set_ko(Hash_data *hd, int pos)
+hashdata_invert_ko(Hash_data *hd, int pos)
{
- hd->hashval ^= ko_hash[pos];
+ int i;
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ hd->hashval[i] ^= ko_hash[pos][i];
+#if FULL_POSITION_IN_HASH
hd->hashpos.ko_pos = pos;
+#endif
}
-/*
- * Remove any ko from the hash value and hash position.
- */
-
-void
-hashdata_remove_ko(Hash_data *hd)
-{
- if (hd->hashpos.ko_pos != 0) {
- hd->hashval ^= ko_hash[hd->hashpos.ko_pos];
- hd->hashpos.ko_pos = 0;
- }
-}
-
/*
* Set or remove a stone of COLOR at pos in a Hash_data.
@@ -311,18 +277,27 @@
void
hashdata_invert_stone(Hash_data *hd, int pos, int color)
{
+#if FULL_POSITION_IN_HASH
int i = I(pos);
int j = J(pos);
int index = (i * board_size + j) / POINTSPERCOMPACT;
int subindex = (i * board_size + j) % POINTSPERCOMPACT;
+#endif
+ int k;
if (color == BLACK) {
- hd->hashval ^= black_hash[pos];
+ for (k = 0; k < NUM_HASHVALUES; k++)
+ hd->hashval[k] ^= black_hash[pos][k];
+#if FULL_POSITION_IN_HASH
hd->hashpos.board[index] ^= black_patterns[subindex];
+#endif
}
else if (color == WHITE) {
- hd->hashval ^= white_hash[pos];
+ for (k = 0; k < NUM_HASHVALUES; k++)
+ hd->hashval[k] ^= white_hash[pos][k];
+#if FULL_POSITION_IN_HASH
hd->hashpos.board[index] ^= white_patterns[subindex];
+#endif
}
}
@@ -333,6 +308,7 @@
* return is the same as for hashposition_compare()
*/
+#if FULL_POSITION_IN_HASH
int
hashdata_diff_dump(Hash_data *hd1, Hash_data *hd2)
{
@@ -392,16 +368,25 @@
return retval;
}
+#endif
int
hashdata_compare(Hash_data *hd1, Hash_data *hd2)
{
- int rc;
+ int rc = 0;
+ int i;
- rc = (hd1->hashval == hd2->hashval) ? 0 : 2;
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ if (hd1->hashval[i] != hd2->hashval[i])
+ rc = 2;
+ if ( rc == 2 && i > 0)
+ stats.hash_collisions++;
+
+#if FULL_POSITION_IN_HASH
if (rc == 0)
rc = hashposition_compare(&hd1->hashpos, &hd2->hashpos);
+#endif
return rc;
}
Index: engine/hash.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.h,v
retrieving revision 1.6
diff -u -r1.6 hash.h
--- engine/hash.h 4 Mar 2002 06:49:08 -0000 1.6
+++ engine/hash.h 23 Mar 2002 22:08:38 -0000
@@ -20,6 +20,7 @@
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <stdio.h>
+#include <gnugo.h>
/*
* This file, together with engine/hash.c implements hashing of go positions
@@ -55,12 +56,42 @@
/* for testing: Enables a lot of checks. */
#define CHECK_HASHING 0
+/* Set this to 1 for old hashing, 2 for new hashing, 3 for experiments. */
+#define HASHING_SCHEME 2
+
+/* Old hashing. */
+#if (HASHING_SCHEME==1)
+#define NUM_HASHVALUES 1
+#define FULL_POSITION_IN_HASH 1
+#endif
+
+/* Proposed new hashing. */
+#if (HASHING_SCHEME==2)
+
+/* How many bits should be used at least for hashing? Set this to 32 for
+ * some memory save and speedup, at the cost of occasional irreproducable
+ * mistakes (and possibly assertion failures).
+ * With 64 bits, there should be less than one such mistake in 10^9 games.
+ * Set this to 96 if this is not safe enough for you.
+ */
+#define MIN_HASHBITS 64
+
+#define NUM_HASHVALUES (MIN_HASHBITS / ( 8 * SIZEOF_LONG))
+#define FULL_POSITION_IN_HASH 0 /* Set this to 1 for debugging. */
+#endif
+
+/* Use this for self-defined values. */
+#if (HASHING_SCHEME==3)
+#define NUM_HASHVALUES ?
+#define FULL_POSITION_IN_HASH ?
+#endif
+
/*
* We define a special compact representation of the board for the
- * positions. In this representation each location is represented
- * by 2 bits with 0 meaning EMPTY, 1 meaning WHITE and 2 meaning
- * BLACK as defined in gnugo.h.
+ * positions, used if FULL_POSITION_IN_HASH is set. In this representation
+ * each location is represented by 2 bits with 0 meaning EMPTY, 1 meaning
+ * WHITE and 2 meaning BLACK as defined in gnugo.h.
* COMPACT_BOARD_SIZE is the size of such a compact representation
* for the maximum board size allowed.
*
@@ -84,11 +115,12 @@
#define POINTSPERCOMPACT ((int) sizeof(Compacttype) * 4)
#define COMPACT_BOARD_SIZE ((MAX_BOARD) * (MAX_BOARD) / POINTSPERCOMPACT + 1)
-
+#if FULL_POSITION_IN_HASH
typedef struct hashposition_t {
Compacttype board[COMPACT_BOARD_SIZE];
int ko_pos;
} Hashposition;
+#endif
/*
@@ -97,19 +129,22 @@
*/
typedef struct {
- Hashvalue hashval;
+ Hashvalue hashval[NUM_HASHVALUES];
+#if FULL_POSITION_IN_HASH
Hashposition hashpos;
+#endif
} Hash_data;
void hash_init(void);
+#if FULL_POSITION_IN_HASH
int hashposition_compare(Hashposition *pos1, Hashposition *pos2);
void hashposition_dump(Hashposition *pos, FILE *outfile);
+#endif
void hashdata_recalc(Hash_data *hd, Intersection *board, int ko_pos);
int hashdata_compare(Hash_data *hd1, Hash_data *hd2);
-void hashdata_set_ko(Hash_data *hd, int pos);
-void hashdata_remove_ko(Hash_data *hd);
+void hashdata_invert_ko(Hash_data *hd, int pos);
void hashdata_invert_stone(Hash_data *hd, int pos, int color);
void hashdata_set_tomove(Hash_data *hd, int to_move);
- [gnugo-devel] hash_1_28.4: revision of hash_1_28.3,
Arend Bayer <=