[computer-go] Monte Carlo combined with minimax search

[Dave Denholm]

"Chrilly" <c.donninger at wavenet.at> writes:

> I have ported a C chess programm which was initially written for a
> Hitachi microcontroller to Java. The Java version was on a PC only 15%
> slower. One can write C-programs in Java with the rules below. The 15%
> difference are due to the better optimization of a C-Compiler. The
> Java to Virtual-Machine compiler produces very poor code. Obviously
> the Just-In-Time compiler in the runtime does only some loophole
> optimizations which can not compete with the optimizations of a
> C-Compiler. When switching off the JIT-Compiler the Java code runs 15
> times slower.
>

> The rules to produce very fast Java codes are:
>
> a) Avoid new, any creation of new objects.
> b) Function/method codes are in Java expensive, because the correct
> method is determined dynamically. I C its a simply "call"
> instruction. The standard Java calling convention is by orders more
> expensive than in C.

I think that virtual invoke is so important that JVMs have optimised
this reasonably well. While still slower than a static invoke, it can be
done with only one extra memory dereference. It need not be orders of
magnitude more expensive. Avoid synchronised methods is best.

Invoke of a static method need not be any slower than a c invoke,
since the target method can be determined at JIT time.

Invoking via interfaces should definitely be avoided.


> To circumvent this problem one has to declare the
> class as final. In this case the compiler can generate also a "call"
> instruction like in C.

A JVM can potentially make optimisations like *assume* a method is
final (it is sufficient for a method to be final - don't have to mark
the whole class final). Then if it is proved wrong, it can throw away
any JIT code it has generated, and regenerate it more pessimistically.

> In my program there was only one big final
> class which contained all the functions/methods of the original
> code. I removed effectivly the object-system and wrote a
> flat-collection of functions like in plain C.


static methods ? No real reason to collect them all in one class.

> c) The Java Virtual Engine can only process 32-Bit numbers. All other
> data are second class citizens which are converted to 32-Bit. Using
> e.g. a Byte array makes things worse, because there is an additional
> Convert to 32-Bit instruction involved.

I don't agree here. Assuming a JIT that compiles to native code, as
long as the native instruction set includes opcodes to sign-extend a
narrow quantity up to the width of a register, there is no penalty for
using narrow types. (And there is a benefit of packing the data if it
means more can fit into the memory cache.)


dd
-- 
Dave Denholm              <ddenholm at esmertec.com>       http://www.esmertec.com