Hi Micheal,
Thanks for the test (Intel -> AMD, Windows XP -> Windows 7, x32 -> x64,
great, three birds with one stone!). So much for portability. But,
hooray for test-cases!
This may be related to the __lzcnt intrinsic, giving you a completely
different result, i.e., 32 - my result. Could you try replacing this
function in bitmap.cpp? I believe I tested this alternative during
development and it generates only slightly worse performing code.
__forceinline
unsigned int bitmap_t::lowest_index () const {
const __m128i comp = _mm_cmpeq_epi32 (_mm_setzero_si128 (), board);
unsigned long m = _mm_movemask_epi8 (comp) ^ 0xffff;
if (!_BitScanForward (&m, m)) return 127;
/* offending instruction */
//return 8*m + __lzcnt (board.m128i_u32[m/4]);
/* new code follows */
unsigned long n;
_BitScanForward (&n, board.m128i_u32[m/4]);
return 8*m + n;
}
René
PS. x64 ... new playground, you could use __lzcnt64 ... so many things
to try!
On Tue, Aug 25, 2009 at 5:43 PM, Michael Williams
<michaelwilliam...@gmail.com <mailto:michaelwilliam...@gmail.com>> wrote:
(AMD Phenom CPU)
Michael Williams wrote:
It came through fine the first time. Gmail probably hid the
duplicate text from you for convenience since it saw that it was
text that you already sent out. Or something.
I can compile the original (9x9) bitmap Go files in Windows 7
x64, but when I run it I get this:
test-error [bitmap_t::lowest_index]: 0 31
test-error [bitmap_t::lowest_index]: 1 30
test-error [bitmap_t::lowest_index]: 2 29
test-error [bitmap_t::lowest_index]: 3 28
test-error [bitmap_t::lowest_index]: 4 27
test-error [bitmap_t::lowest_index]: 5 26
test-error [bitmap_t::lowest_index]: 6 25
test-error [bitmap_t::lowest_index]: 7 24
test-error [bitmap_t::lowest_index]: 8 23
test-error [bitmap_t::lowest_index]: 9 22
test-error [bitmap_t::lowest_index]: 10 21
test-error [bitmap_t::lowest_index]: 11 20
test-error [bitmap_t::lowest_index]: 12 19
test-error [bitmap_t::lowest_index]: 13 18
test-error [bitmap_t::lowest_index]: 14 17
test-error [bitmap_t::lowest_index]: 15 16
test-error [bitmap_t::lowest_index]: 16 15
test-error [bitmap_t::lowest_index]: 17 14
test-error [bitmap_t::lowest_index]: 18 13
test-error [bitmap_t::lowest_index]: 19 12
test-error [bitmap_t::lowest_index]: 20 11
test-error [bitmap_t::lowest_index]: 21 10
test-error [bitmap_t::lowest_index]: 22 9
test-error [bitmap_t::lowest_index]: 23 8
test-error [bitmap_t::lowest_index]: 24 7
test-error [bitmap_t::lowest_index]: 25 6
test-error [bitmap_t::lowest_index]: 26 5
test-error [bitmap_t::lowest_index]: 27 4
test-error [bitmap_t::lowest_index]: 28 3
test-error [bitmap_t::lowest_index]: 29 2
test-error [bitmap_t::lowest_index]: 30 1
test-error [bitmap_t::lowest_index]: 31 0
test-error [bitmap_t::lowest_index]: 32 63
test-error [bitmap_t::lowest_index]: 33 62
test-error [bitmap_t::lowest_index]: 34 61
test-error [bitmap_t::lowest_index]: 35 60
test-error [bitmap_t::lowest_index]: 36 59
test-error [bitmap_t::lowest_index]: 37 58
test-error [bitmap_t::lowest_index]: 38 57
test-error [bitmap_t::lowest_index]: 39 56
test-error [bitmap_t::lowest_index]: 40 55
test-error [bitmap_t::lowest_index]: 41 54
test-error [bitmap_t::lowest_index]: 42 53
test-error [bitmap_t::lowest_index]: 43 52
test-error [bitmap_t::lowest_index]: 44 51
test-error [bitmap_t::lowest_index]: 45 50
test-error [bitmap_t::lowest_index]: 46 49
test-error [bitmap_t::lowest_index]: 47 48
test-error [bitmap_t::lowest_index]: 48 47
test-error [bitmap_t::lowest_index]: 49 46
test-error [bitmap_t::lowest_index]: 50 45
test-error [bitmap_t::lowest_index]: 51 44
test-error [bitmap_t::lowest_index]: 52 43
test-error [bitmap_t::lowest_index]: 53 42
test-error [bitmap_t::lowest_index]: 54 41
test-error [bitmap_t::lowest_index]: 55 40
test-error [bitmap_t::lowest_index]: 56 39
test-error [bitmap_t::lowest_index]: 57 38
test-error [bitmap_t::lowest_index]: 58 37
test-error [bitmap_t::lowest_index]: 59 36
test-error [bitmap_t::lowest_index]: 60 35
test-error [bitmap_t::lowest_index]: 61 34
test-error [bitmap_t::lowest_index]: 62 33
test-error [bitmap_t::lowest_index]: 63 32
test-error [bitmap_t::lowest_index]: 64 95
test-error [bitmap_t::lowest_index]: 65 94
test-error [bitmap_t::lowest_index]: 66 93
test-error [bitmap_t::lowest_index]: 67 92
test-error [bitmap_t::lowest_index]: 68 91
test-error [bitmap_t::lowest_index]: 69 90
test-error [bitmap_t::lowest_index]: 70 89
test-error [bitmap_t::lowest_index]: 71 88
test-error [bitmap_t::lowest_index]: 72 87
test-error [bitmap_t::lowest_index]: 73 86
test-error [bitmap_t::lowest_index]: 74 85
test-error [bitmap_t::lowest_index]: 75 84
test-error [bitmap_t::lowest_index]: 76 83
test-error [bitmap_t::lowest_index]: 77 82
test-error [bitmap_t::lowest_index]: 78 81
test-error [bitmap_t::lowest_index]: 79 80
test-error [bitmap_t::lowest_index]: 80 79
test-error-1 [bitmap_t::is_one_bit]: 0
test-error-1 [bitmap_t::is_one_bit]: 1
test-error-1 [bitmap_t::is_one_bit]: 2
test-error-1 [bitmap_t::is_one_bit]: 3
test-error-1 [bitmap_t::is_one_bit]: 4
test-error-1 [bitmap_t::is_one_bit]: 5
test-error-1 [bitmap_t::is_one_bit]: 6
test-error-1 [bitmap_t::is_one_bit]: 7
test-error-1 [bitmap_t::is_one_bit]: 8
test-error-1 [bitmap_t::is_one_bit]: 9
test-error-1 [bitmap_t::is_one_bit]: 10
test-error-1 [bitmap_t::is_one_bit]: 11
test-error-1 [bitmap_t::is_one_bit]: 12
test-error-1 [bitmap_t::is_one_bit]: 13
test-error-1 [bitmap_t::is_one_bit]: 14
test-error-1 [bitmap_t::is_one_bit]: 15
test-error-1 [bitmap_t::is_one_bit]: 16
test-error-1 [bitmap_t::is_one_bit]: 17
test-error-1 [bitmap_t::is_one_bit]: 18
test-error-1 [bitmap_t::is_one_bit]: 19
test-error-1 [bitmap_t::is_one_bit]: 20
test-error-1 [bitmap_t::is_one_bit]: 21
test-error-1 [bitmap_t::is_one_bit]: 22
test-error-1 [bitmap_t::is_one_bit]: 23
test-error-1 [bitmap_t::is_one_bit]: 24
test-error-1 [bitmap_t::is_one_bit]: 25
test-error-1 [bitmap_t::is_one_bit]: 26
test-error-1 [bitmap_t::is_one_bit]: 27
test-error-1 [bitmap_t::is_one_bit]: 28
test-error-1 [bitmap_t::is_one_bit]: 29
test-error-1 [bitmap_t::is_one_bit]: 30
test-error-1 [bitmap_t::is_one_bit]: 31
test-error-1 [bitmap_t::is_one_bit]: 32
test-error-1 [bitmap_t::is_one_bit]: 33
test-error-1 [bitmap_t::is_one_bit]: 34
test-error-1 [bitmap_t::is_one_bit]: 35
test-error-1 [bitmap_t::is_one_bit]: 36
test-error-1 [bitmap_t::is_one_bit]: 37
test-error-1 [bitmap_t::is_one_bit]: 38
test-error-1 [bitmap_t::is_one_bit]: 39
test-error-1 [bitmap_t::is_one_bit]: 40
test-error-1 [bitmap_t::is_one_bit]: 41
test-error-1 [bitmap_t::is_one_bit]: 42
test-error-1 [bitmap_t::is_one_bit]: 43
test-error-1 [bitmap_t::is_one_bit]: 44
test-error-1 [bitmap_t::is_one_bit]: 45
test-error-1 [bitmap_t::is_one_bit]: 46
test-error-1 [bitmap_t::is_one_bit]: 47
test-error-1 [bitmap_t::is_one_bit]: 48
test-error-1 [bitmap_t::is_one_bit]: 49
test-error-1 [bitmap_t::is_one_bit]: 50
test-error-1 [bitmap_t::is_one_bit]: 51
test-error-1 [bitmap_t::is_one_bit]: 52
test-error-1 [bitmap_t::is_one_bit]: 53
test-error-1 [bitmap_t::is_one_bit]: 54
test-error-1 [bitmap_t::is_one_bit]: 55
test-error-1 [bitmap_t::is_one_bit]: 56
test-error-1 [bitmap_t::is_one_bit]: 57
test-error-1 [bitmap_t::is_one_bit]: 58
test-error-1 [bitmap_t::is_one_bit]: 59
test-error-1 [bitmap_t::is_one_bit]: 60
test-error-1 [bitmap_t::is_one_bit]: 61
test-error-1 [bitmap_t::is_one_bit]: 62
test-error-1 [bitmap_t::is_one_bit]: 63
test-error-1 [bitmap_t::is_one_bit]: 64
test-error-1 [bitmap_t::is_one_bit]: 65
test-error-1 [bitmap_t::is_one_bit]: 66
test-error-1 [bitmap_t::is_one_bit]: 67
test-error-1 [bitmap_t::is_one_bit]: 68
test-error-1 [bitmap_t::is_one_bit]: 69
test-error-1 [bitmap_t::is_one_bit]: 70
test-error-1 [bitmap_t::is_one_bit]: 71
test-error-1 [bitmap_t::is_one_bit]: 72
test-error-1 [bitmap_t::is_one_bit]: 73
test-error-1 [bitmap_t::is_one_bit]: 74
test-error-1 [bitmap_t::is_one_bit]: 75
test-error-1 [bitmap_t::is_one_bit]: 76
test-error-1 [bitmap_t::is_one_bit]: 77
test-error-1 [bitmap_t::is_one_bit]: 78
test-error-1 [bitmap_t::is_one_bit]: 79
test-error-1 [bitmap_t::is_one_bit]: 80
And then it crashes.
René van de Veerdonk wrote:
[I do not know what happens, but this is the second time the
computer-go archives miss the body. Maybe its the
attachment. I apologize for sending this a second time, this
time without attachment. If someone knows what the problem
is ... I am using Gmail]
Antoine,
I apologize for misrepresenting your feelings. What I wanted
to convey is that your e-mail expressed that with the same
amount of computation, other implementation strategies
provide more information, so the information gained for the
effort put in is disappointing. In other words, bitmap-go
had better be much faster to make up for the lack of
information gained ... and it wasn't. That's pretty much
what you are saying as well, I believe. As are the others in
this thread. I think we can all agree on this.
Going into this project, I was well aware that I was going
to end up with light playouts only, and that heavy playouts
is the way to go except perhaps for some special purposes
such as ladder readouts. I was also well aware of the
scaling argument. But, I hadn't thought that this would be
the first thing thrown at my first post, as there are many
programmers that seem to be stuck at 9x9. Nonetheless,
bitmap-go as a topic keeps resurfacing on this mailing list
every once in a while and nobody ever put solid data and a
reference implementation behind it. That is what I wanted to
accomplish with my mockup.
Confession #2: I have been working on my own MCTS
implementation using the standard implementation methods
that almost everybody else is using. But there is a
never-ending laundry-list of things that I would like to
include before I would reach reasonable strength (where
reasonable is a moving target). In the mean time, there are
many others that have demonstrated much more capable
programmers than I ever will be. So, by providing this
bitmap-go mockup at least I had the feeling that I was
contributing something newsworthy to the conversation. This
may have never happened if I would wait until my MCTS
program is ready. I imagine that there are others on this
list in a similar situation. Besides, this was an
interesting side-project and perhaps someone else can
benefit from it (go for it Brian!). And, yes, it was fun.
Okay, enough mesmerizing, on to the main topic.
David, Lukasz,
I did modify my mockup to do 19x19 bitmap-go (attached). It
is a hardcoded solution using arrays of three 128-bit
variables. I did not even attempt to optimize this version,
so this is not the best possible solution. Nonetheless, here
is a comparison:
Example output (9x9):
=====================
[game] = 30236.1, [moves] = 111.071
[game] = 30249.7, [moves] = 111.068
[game] = 30145.7, [moves] = 111.089
[game] = 30237.7, [moves] = 111.122
[game] = 30210.1, [moves] = 111.101
[game] = 78.0488 kpps, [moves] = 111.023
[game] = 78.0488 kpps, [moves] = 111.045
[game] = 78.0488 kpps, [moves] = 111.046
[game] = 79.0123 kpps, [moves] = 111.131
[game] = 78.0488 kpps, [moves] = 111.082
[legal] 110/51, [pick] 110/74, [play] 106/168, [score] 44,
[win] 0.4187
[legal] 111/51, [pick] 111/74, [play] 106/168, [score] 40,
[win] 0.4201
[legal] 111/52, [pick] 111/75, [play] 106/168, [score] 42,
[win] 0.4276
[legal] 111/52, [pick] 111/74, [play] 106/169, [score] 41,
[win] 0.4092
[legal] 111/52, [pick] 111/74, [play] 106/169, [score] 44,
[win] 0.4221
Example output (19x19):
=======================
[game] = 316452, [moves] = 455.036
[game] = 316378, [moves] = 455.126
[game] = 316266, [moves] = 455.177
[game] = 316017, [moves] = 455.08
[game] = 316210, [moves] = 455.16
[game] = 7.45052 kpps, [moves] = 455.267
[game] = 7.45921 kpps, [moves] = 455.055
[game] = 7.45921 kpps, [moves] = 455.17
[game] = 7.45921 kpps, [moves] = 455.188
[game] = 7.47664 kpps, [moves] = 455.013
[legal] 454/144, [pick] 454/128, [play] 449/430, [score]
173, [win] 0.4592
[legal] 455/144, [pick] 455/128, [play] 449/431, [score]
173, [win] 0.4655
[legal] 454/144, [pick] 454/128, [play] 449/430, [score]
173, [win] 0.4611
[legal] 454/144, [pick] 454/128, [play] 449/431, [score]
173, [win] 0.4674
[legal] 455/144, [pick] 455/128, [play] 450/430, [score]
175, [win] 0.4661
Summary:
========
function 9x9 19x19 ratio
-----------------------------------
game [ cc ] 30216 316265 10.47
game [kpps] 78 7.46 10.45
moves 111 455 4.10
legal [ cc ] 52 144 2.77
pick [ cc ] 74 128 1.73
play [ cc ] 168 430 2.56
score [ cc ] 42 173 4.12
legal+pick+play 294 702 2.39
So, it looks that I was overly pessimistic in terms of
performance drop per move, which is a factor of 2.4x (with
little effort to optimize for 19x19). But, with 4.1x more
moves, this still resulted in a 10x speed penalty. With the
provided reference numbers, Libego only drops 4.5-5.0x,
indicating that there is almost no performance loss per move
(1.2x). Is this difference roughly in line with others
expectation?
With that, I hope this at least provides some data for
future discussions, and reference implementation for others
that may want to pick up the ball from here. Someone could
add a gtp-interface and make it available as one of Don's
reference implementations for starting go-programmers. I
would still be interested to improve this solution, but I
think I need a fresh set of eyes in order to make any more
progress. I would like to re-iterate that I expect
significant gains on a 64-bit OS as a result on the doubling
of the number of available registers. It would be nice if
someone would be able to post some results. Newer CPU's
(will) also have instructions available that can
significantly speed things up (bit-test, compare, popcount,
wider variables, etc).
René van de Veerdonk
On Tue, Aug 25, 2009 at 12:42 PM, Antoine de Maricourt
<antoine.de-marico...@m4x.org
<mailto:antoine.de-marico...@m4x.org>
<mailto:antoine.de-marico...@m4x.org
<mailto:antoine.de-marico...@m4x.org>>> wrote:
Hi René,
David,
Confession: I have not tested 19x19. As you have
noted, and
others before you over the years, a 19x19 board does
not fit in
one but three 128-bit registers and there would be a
rather big
penalty as a result, perhaps (likely?) wiping out all
of the
benefits of bitmaps. Antoine voiced his
disappointment about the
speed advantage even on 9x9 in the e-mail to the list
that
served as my basis. My hope, as Hideko Kato points
out, is in
longer registers or perhaps being able to port this
to a GPU. A
64-bit OS with twice the number registers would also
surely help
out. Nevertheless, I was surprised that I was able to
get to
almost the same level of speed as Libego provides.
As far as I remember, I was not disappointed by the speed
itself on
9x9 boards, but mainly with the following 2 points:
a) my feeling is that, as you say, it does not scale very
well on
19x19 (on current hardware).
I don't think other "classical" implementations suffer
such a big
penalty when scaling from 9x9 to 19x19.
b) I also felt that this kind of implementation was not
very flexible.
For instance, I had another classical implementation,
running at
equivalent speed, but in which local 3x3 pattern matching
was almost
for free, as well as other more elaborated information.
When I started to think about introducing 3x3 local
patterns in the
bitmap only implementation, it was clear it would not be
for free.
At that time, my conclusion was that if one only needs
pure random
play with no intelligence at all during playouts, then bitmap
implementation could compete (at least on 9x9).
If one needs more elaborated knowledge (such as small
patterns
matching, or even knowledge about blocks of stones), then
pure
bitmap implementation is probably not so competitive.
I thus gave up with the idea and jumped to more promising
ones.
Anyway, I'm glad my post has been usefull to you. And I
encourage
you to improve your implementation and let us know,
especially if
you have fun. Starting with something and playing with it
is a good
way to have new ideas, even if this makes your initial
ones look
less interesting a while after.
Best regards,
Antoine
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
<mailto:computer-go@computer-go.org>
<mailto:computer-go@computer-go.org
<mailto:computer-go@computer-go.org>>
http://www.computer-go.org/mailman/listinfo/computer-go/
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org <mailto:computer-go@computer-go.org>
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org <mailto:computer-go@computer-go.org>
http://www.computer-go.org/mailman/listinfo/computer-go/
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
