Re: [gnugo-devel] Patch: new cache implementation

[Arend Bayer]

Hi Inge,

as I also will be on holidays when you come back, I'll write some
comments now.

> Here is the first implementation of the new hash and cache scheme that
> I described in
> http://mail.gnu.org/archive/html/gnugo-devel/2003-02/msg00046.html. If
> you don't remember it, I suggest that you reread that mail before
> going any further here.

I think you made it even harder than necessary: You mixed in two changes
that are completely unrelated:
1. Change of the type of the hash values
2. Reorganize the cache table.

No. 1 is debatable at least (it takes away the possibilty to easily
change the number of bits for the hash values if I read your code
correctly), so maybe a patch to just do no. 2 would be better.

At least, before we hardwire the hash value to 64 bit, we should do
some estimates that we won't make hash collisions too likely even once
we, say, increase the number of reading nodes by a factor of 10.

Or if you think you need no. 1 then maybe do it as a separate patch
first.

> 1. I use the type uint64_t from stdint.h as a 64 bit integer that
>    stores the hash value.  This is a type that is defined in the C99
>    standard.   However, we were discussing the patch on NNGS yesterday
>    and Gunnar has issues with that, since he thinks that there are too
>    many old compilers out there that don't have stdint.h.
>
>    I hope that some expert in autoconfig can device a test for stdint
>    so that I can use it if it works and implement another way if there
>    are only 32 bit integers on the target system.  Arend?

Oh dear, how did I get myself into that reputation? I think there is
nothing better than what Wolfgang Manner suggested (or s.th. similar).

> 2. The old implementation and the new one currently resides side by
>    side.  The plan is to retire the old one and only use the new one.
>    That will have to be done after I come back from my vacation in two
>    weeks.
>
>    Currently I allocate 1% of the memory to the old hash table and 99%
>    of it for the new one.
(...)
>    I think that owl nodes are more important to save than tactical
>    reading nodes so instead of 0.2% I allocate 1%, and that seems to
>    work out pretty well.

You need to allocate more than 1% for the other caches. They also store the
connection reading results. (I also think that that's where the
PASSes/FAILs are coming from, as connectino reading also has a node
limit.)

> What are the results then?  Pretty promising.
>
> Although I have only implemented the new scheme for do_attack() and
> do_find_defense() yet, there is already a 5% increase in performace.
> This is completely due to a more efficient caching of reading nodes.
> This makes me think that it might even be useful to enter the patch
> into gnugo before 3.4.

While I really like your patch, I am against putting it into 3.4. We are
simply too close to release.

Some details below.

Arend


> diff -ur gnugo/engine/.deps/aftermath.Po gnugo-tt/engine/.deps/aftermath.Po
> --- gnugo/engine/.deps/aftermath.Po   Sun Jun 29 21:51:56 2003
> +++ gnugo-tt/engine/.deps/aftermath.Po        Sat Jul  5 13:58:13 2003
Please exclude these files from your diff. If you don't want to use
"cvs diff", you can put
"alias ggdiff='diff -X ~/.diffignore -urp'"
into you .bashrc or whatever, and a list such as

\.deps
*\.o
CVS
owl_attackpat\.c
owl_defendpat\.c
owl_vital_apat\.c

etc. into ~/.diffignore.

> diff -ur gnugo/engine/cache.c gnugo-tt/engine/cache.c
> --- gnugo/engine/cache.c      Wed Jun  4 14:48:49 2003
> +++ gnugo-tt/engine/cache.c   Sat Jul  5 13:57:19 2003
> @@ -21,6 +21,7 @@
>  \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
>
>
> +#include "random.h"
>  #include "gnugo.h"
>
>  #include <stdio.h>

Why that?

> +tt_get(Transposition_table *table,
> +       int komaster, int kom_pos, int routine, int target,
> +       int remaining_depth,
> +       int *result, int *move)
(...)

> +  /* 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 ((unsigned) remaining_depth <= hn_get_remaining_depth(*node)) {
> +    if (result)
> +      *result = hn_get_result1(*node);

That's a subtle change in behaviour that also needs discussion
(the old one only set the result if "==" in the above equation). I am not
against it, but one should be aware that it makes debugging more
difficult.

> +  if (move)
> +    *move = hn_get_move(*node);
That's a start towards iterative deepening, I suppose? (Yeah, yeah!)

> diff -ur gnugo/engine/cache.h gnugo-tt/engine/cache.h
> --- gnugo/engine/cache.h      Sat Jul  5 13:52:21 2003
> +++ gnugo-tt/engine/cache.h   Sat Jul  5 13:57:24 2003

> +typedef struct {
> +  Hashvalue_ng  key;
> +  uint32_t      data;
> +} Hashnode_ng;
> +
> +
> +/* Hashentry: an entry, with two nodes of the hash_table
> + */
> +typedef struct {
> +  Hashnode_ng  deepest;
> +  Hashnode_ng  newest;
> +} Hashentry_ng;

When you described your plans, you wanted to store the "most expensive"
(in terms of reading nodes) instead of "deepest". Any motivation for
that change? Also, I find the name "deepest" a bit confusing, because
you mean the entry where the remaining depth is highest, i.e. more
likely a node at very shallow depth in the tree.


> diff -ur gnugo/engine/globals.c gnugo-tt/engine/globals.c
> --- gnugo/engine/globals.c    Thu Jun 19 20:57:45 2003
> +++ gnugo-tt/engine/globals.c Sat Jul  5 13:57:31 2003
> @@ -57,7 +57,9 @@
>  Intersection shadow[BOARDMAX];
>
>  /* Hashing of positions. */
> -Hash_data    hashdata;
> +Hash_data     hashdata;
> +Hashvalue_ng  hashval_ng;
> +Transposition_table  ttable;

I think the transposition table should rather be a private variable
inside cache.c, just as the old one.