On 3-dec-08, at 10:31, Heikki Levanto wrote:
Having said that, I can't help responding to one detail:
I had seen people write about memory usage of the tree, but never
understood the concerns.
One thing to remember is that more memory use means more cache
misses, and
more access to the main memory. On modern computers, those can cost
as much
as executing a thousand instructions! So memory optimizing can
often pay off,
also with respect to time!
Of course, Java does a lot of memory management behind the scenes, so
optimizing such can be harder... But when writing in C or C++, it
does make
sense.
I've seen this stated often. But color me skeptical. If what you say
is true, then the MC-AMAF bot, which hardly uses any memory at all
and which fits in the secondary cache entirely, code and data
combined, should show an enormous speed-up in terms of number of
playouts per second. Instead it does only about twice the number of
playouts per second as the tree-search version, which can be almost
if not entirely explained by the extra work that needs to be done to
traverse and maintain the tree. If this is because I use Java, then
Don's concise C implementation of the MC-AMAF bot should be a lot
faster than my bloated Java version. Which, ahem, is not the case at
all. I think a well-crafted C program can be up to twice as fast as a
similar Java program. But I doubt that has much to do with cache misses.
I think in computer-Go, trying to control cache misses is futile no
matter the language. Maybe you can do it for a relatively trivial,
well-understood and stable sub-part. But then you risk losing the
gain again as soon as it gets incorporated into a larger whole. So
your efforts go to waste.
So this is in the "show me" category for me. You can use C or C++ if
you like, but show me a tree-search bot that speeds up the number of
playouts significantly by reducing the node-size. Maybe it's
possible, but I don't believe it until I see it. This could be
different for Chess programs, at least I've seen it claimed often.
But I don't envy them, it must be excruciatingly frustrating to deal
with.
Mark
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
