Re: [computer-go] Pattern Matcher

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 16:09 9-11-2004 +0100, Arend Bayer wrote:
>
>
>On Tue, 9 Nov 2004, Vincent Diepeveen wrote:
>
>> The best possible book you can get is for free.
>> 
>> Go to the AMD and intel websites and get the processor documentation.
>> 
>> If you realize what the processor is fast at, and what it is slow at, it is
>> very trivial to code for that. 
>
>I did this some time ago, and found it pretty much a waste of time as far
>as optimizing GNU Go is concerned. The reason is that GNU Go's performance
>is 90 % bound by branch-misprediction, and that you cannot optimize
>these branches away. Btw I was told that the same held true for the
>version of Many Faces that David Fotland had submitted to SPEC95, and I
>would not be surprised if that is true for any go program.
>Arend

There is 3 ways to reduce branch mispredictions:
  a) rewrite your code to fall through principles
  b) within patterns be sure to get more cmov's.

A simple example of that can be demonstrated using more local variables

#define EYE_BONUS 500
 ... 
 ... {
   if( a == 1 && b[i] == 361 ) // very bad and slow code
     score += EYE_BONUS;

The C compilers are so good nowadays that they will be able to make CMOV's
out of :
 ...
 ... {
   int x=b[i];    
   if( a == 1 && x == 361 ) 
     score += EYE_BONUS;     

speed savings are on average a factor 12 for this piece of code.

Reason compilers are not allowed to make CMOV's out of the first piece of
code is because there is a possibility that 'i' can be an index outside the
array b.

  c) use PGO

Probably everybody should do PGO. Idea is you do a long testrun (the longer
the better, at itanium2 i found out for DIEP i needed to run longer than 24
hours with intel c++ even as it's an IPF processor) and then the data
collected will for example reorder your code.

So there is less of a need for writing your own code fall through, but B
you definitely should follow.

Vincent

>
>
>_______________________________________________
>computer-go mailing list
>computer-go@xxxxxxxxxxxxxxxxx
>http://www.computer-go.org/mailman/listinfo/computer-go/
>
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/