RE: [computer-go] Pattern Matcher

[Vincent Diepeveen <diep@xxxxxxxxx>]

For branch intensive commercial code (so well written code) speedup = 30%.

Also it will avoid hopefully register stalls.

intel c++ has it, gcc has it and microsoft is acting slow. Now that opteron
profits less and intel processors more, intel may be happy that msvc 2005
gets it. The beta they turned off feature. 

Opteron would look too fast.

At a processor 1 branch misprediction at p4 is a minimum of 20, an average
of 35 and a worst case of even way more cycles penalty.

if( a == 292 && b[x] = stone ){

  .. lots of code

}

Very slow.

Processor has CMOV instructions, very fast when i try to search for big
primes with some hobby proggie i wrote.

CMOV has a latency of 2 cycles.

So for example:
  if( !a ) 
    b = 0;

all modern compilers will generate a cmov here. That's why optimizing for a
processor is very important.

Net2003 is very fast without pgo in fact: -O2 -G7

Intel c++ might be way faster for branch intensive code as it has PGO.

But be careful to check that it is 100% correct output. I had some nasty
bugs with floating point code with intel c++.

You can however sometimes rewrite that to 64 bits integer code. Executes
faster too.

We will see such nasty surprises too when JAVA and C# are going to get used
in future for benchmarks and are considered important. You will really
blink 10 times with your eyes if you see what the compiler experts will
manage to get out of a certain program which is in a testset and where they
can so called 'hand optimize assembly code for' with their 'general
compiler version'.

The speed intel c++ gets at certain specint2000 programs is just unrealistic.

Then sun stroke. They managed to speedup a certain fortran floating point
program a factor 7. 

So a new processor of them, just 100% the same like old one, it looked
quite better suddenly :)

Last few months GCC 3.3 to 3.4 has been speeded up 60% for the C programs
in specint2000.

Vincent

At 12:07 9-11-2004 -0200, Mark Boon wrote:
>No, I must admit my ignorance, as I had never heard of it. A Google got me
>this though:
>
>Profile Guided Optimization for static languages provide
>benefit #3 at the cost of not being transparent
>(they require a multi-phase compilation process). Additionally,
>PGO suffers from three main problems:
>(1)Empirically, developers are unlikely to use PGO, except
>when compiling benchmarks.
>(2) When PGO is
>used, the application is tuned to the behavior of the
>training run. If the training run is not representative
>of the end-user's usage patterns, the program may actually
>be pessimized by the profile information. (3)
>The profiling information is completely static, meaning
>that the compiler cannot make use of phase behavior
>in the program or adapt to changing usage patterns.
>
>Seems to me not something I can care to get into for a Go program.
>
>In your next mail you're all making nonsense assumptions about my program
>that you know nothing about. I measured what I measured. What you think
>about my programming skills is just for you, as it's also something you know
>nothing about. So far it's all talk from your side, showing very little
>respect.
>
>Come on, where is your 3 times faster C compilation of John's example?
>
>> -----Original Message-----
>> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
>> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Vincent
>> Diepeveen
>> Sent: Tuesday, November 09, 2004 11:55
>> To: computer-go; computer-go
>> Subject: RE: [computer-go] Pattern Matcher
>>
>>
>> Mark, did you already try a PGO with your C code?
>>
>> At 09:20 9-11-2004 -0200, Mark Boon wrote:
>> >> -----Original Message-----
>> >> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
>> >> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Vincent
>> >> Diepeveen
>> >> Sent: Tuesday, November 09, 2004 2:52
>> >> To: drd@xxxxxxxxxxxxxxxxx
>> >> Cc: computer-go@xxxxxxxxxxxxxxxxx
>> >> Subject: Re: [computer-go] Pattern Matcher
>> >>
>> >>
>> >> You claim JAVA is fast.
>> >>
>> >> I disprove it clearly as you again showed a memory trashing program.
>> >
>> >What is it with you guys? You didn't disprove anyhing. You're
>> just talking.
>> >
>> >>
>> >> In cilkchess you could get away with it by slowing down the program a
>> >> factor 40 first. Not this time.
>> >>
>> >> It is not acceptible to use this childish programming as a 'proof' that
>> >> JAVA is not that much slower than C.
>> >>
>> >> It's just about a factor 3 slower, not 30%.
>> >
>> >How did the program run? Was the C version 3 times faster than
>> Java or not?
>> >Did you try it? I must admit I didn't try it myself, but then
>> again I'm not
>> >doubting the result Don claimed.
>> >
>> >Goliath is what I consider a typical Go program. 90% (if not
>> 99.9%) of the
>> >execution is spent doing simple test-branch, integer oprations,
>> >array-indexing and function-calls. I'm assuming chess programs are not so
>> >different. I've spent a lot of time optimizing it when it was
>> written in C,
>> >without actually getting to the point of worrying about assembler all the
>> >time. When this was translated to Java, it was first 2 times
>> slower with the
>> >first JITs 7 years ago. Soon after that the difference dwindled
>> to 30%-50%.
>> >Do you think Goliath was made by 'childish programming'?
>> (Actually, I think
>> >it was, but not for the reasons you think something is childish.) Are you
>> >doubting the results I got?
>> >
>> >Now where is *your* proof?
>> >
>> >All you rant on about are assembler instructions that should be
>> avoided, bla
>> >bla. Maybe that is important in chess, but not in Go. If I had to worry
>> >about what instructions the compiler generates I would still be fretting
>> >over just the basic stuff in Go. No time for that, algorithms
>> needed to be
>> >discovered, code needed to be written. I regret not looking more at chess
>> >algorithms, as it turned out I reinvented more of it than necessary. But
>> >still it's all so trivial compared to the important stuff in Go. Yes, I
>> >didn't know it was called 'null-move', but apparently I already
>> used it in
>> >Goliath 15 years ago. When did chess-programs start to use it?
>> >
>> >Worrying about instructions? It would all change with the next
>> generation of
>> >CPUs, it's a waste of time. It works in chess because there
>> speed is almost
>> >the *only* important thing. So the only way to get that extra
>> little bit is
>> >to worry about CPU specific stuff. Not so in Go. You're talking
>> about a poor
>> >hashtable implementation, not important in Go. And some of your
>> peers seem
>> >to doubt it's all that important in chess even. If an
>> instruction that gets
>> >used by the compiler in a Go program is slow, I simply expect
>> that compilers
>> >and chip-designs will take care of it in their next generation.
>> >
>> >Yes, optimization is important. But new ideas are more important. I doubt
>> >*you* can write a faster ladder-routine in C than the Java one in the
>> >library I published, without actually looking how it's done.
>> Most likely it
>> >will be 3 times SLOWER, if not more.
>> >
>> >If all you care about is chess-programming, why are you here? We're
>> >interested in your knowledge about chess programming, as long as
>> there's any
>> >relevance to Go. And I know a lot more effort has been put into
>> >chess-programming than in Go, so hopefully there are bits there
>> we can learn
>> >from it. But stop treating us as a bunch of backward idiots. I
>> don't treat
>> >you as one, and I think some more respect would be appropriate.
>> >
>> >
>> >
>> >
>> >
>> >
>> >_______________________________________________
>> >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/
>>
>
>_______________________________________________
>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/