subject:"Re\: \[computer\-go\] Drunken sailor on payday"

terry mcintyre wrote:
A bird's-eye view of computer-Go programming: a large part of what a
Go program does will probably be some sort of analysis of a deep tree
of possible moves, involving the exploration of millions of possible
positions. The guts of this should be as optimal as possible. A slower
language such as Ruby or Perl is not a good fit for such efforts - but
that's a strawman argument, of little practical relevance.

Higher-level optimizations can provide far more remarkable speed gains
than the choice of implementation language.
This is obviously true and a well known principle, but when you compare
languages for speed, the assumption is that you are using the same
algorithms - anything else is just unfair.

When you talk about Lukasz Lew and his very fast implementation, you
will notice also that he chose C to write his library. I don't think
this is a wild coincidence.It's a mentality and Lukasz has the right
mentality. The kind of person who writes such a library is concerned
about each single percent of execution speed because he knows they add
up.He is not going to immediately start the project with a stupid
decision. If he were willing to do that, chances are good that he
would be willing to take other non-optimal choices.

Of course I'm not saying that you can't do what Lukasz did using a
different language. You could start with any constraints you want and
then be disciplined from that point on - but you wouldn't end up with
the same amazing results Lukasz did.

He could have chosen Ruby, a far more expressive language.Perhaps
it it would be a better choice for him because Ruby's amazing freedom of
expression would unlock his mind and let him soar to new heights, but
somehow Lukasz suffered along in C.

- Don

When Lukasz Lew wrote libego, I believe he recast the algorithms a few
times in order to extract maximum performance, as he discovered more
about how his chosen language ( C++ ) is compiled into assembler, and
how that affects performance. Improvements to move ordering algorithms
can enable reductions in the breadth of trees, which greatly reduce
the size of the tree. Improvements in the quality of playouts result
in vast improvements to the quality of the evaluations, which can lead
to reductions in evaluation times. Several have noted that fast
mersenne twister algorithms improve the speed and quality of random
playouts. Ways to refactor, to incorporate higher-level knowledge, and
otherwise increase the performance of our programs will be discovered
as we learn more about the demands of computer Go. Better algorithms
can improve program performance by factors of tens, hundreds, even
thousands. Some future improvements will surely lead to increases of
hundreds of elo points in ratings, given the same hardware and
implementation language. Some of us will find ways to wring lots of
elo points from multiple processors. Some of these improvements may be
much more easily expressed in higher-level languages than in C.

I cut my teeth on FORTRAN and C and assembler, having written hundreds
of thousand lines in such languages, as well as piles of scripts in
Perl, Ruby, Python, R, and other languages. I've chosen to study Lisp
again ( which I last tinkered with in the 70s ) because I think I see
interesting ways to take advantage of the unique properties of Lisp. I
could write C equivalents to these capabilities - but I'd rather use a
language where where my ideas are a more natural fit. There's a saying
that any sufficiently sophisticated program will eventually include a
buggy implementation of the Lisp eval loop. My efforts may use C
libraries for some speed-intensive task; it may be all Lisp; too early
to make that judgment.

When humans explain how they play Go, their algorithms rarely require
the investigation of millions of potential positions. A good program
need not follow the same methods as a good human player, but it just
might be that human play still offers a few very high-level
optimizations. Fuel for thought.

Be a better sports nut! Let your teams follow you with Yahoo Mobile.
Try it now.
http://us.rd.yahoo.com/evt=51731/*http://mobile.yahoo.com/sports;_ylt=At9_qDKvtAbMuh1G1SQtBI7ntAcJ

___
computer-go mailing list
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/

Re: [computer-go] Drunken sailor on payday

C is the one true language and must be indented with the one true brace
style :-)

- Don


Stefan Nobis wrote:
 Benjamin Teuber [EMAIL PROTECTED] writes:

   
 Man, we really need a complete Common Lisp Go Framework which also
 has some fast low-level code to show all these C gurus its true
 power :)
 

 I think so, too. :)

 I don't want to say CL is the one and only language (for me surely it
 is), I only try to emphasize that C is not the only choice.

   
 

 ___
 computer-go mailing list
 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/

Re: [computer-go] Drunken sailor on payday

2007-11-22 Thread Stefan Nobis

Benjamin Teuber [EMAIL PROTECTED] writes:

 Man, we really need a complete Common Lisp Go Framework which also
 has some fast low-level code to show all these C gurus its true
 power :)

I think so, too. :)

I don't want to say CL is the one and only language (for me surely it
is), I only try to emphasize that C is not the only choice.

-- 
Until the next mail...,
Stefan.


pgpza4eWVxwnP.pgp
Description: PGP signature
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

Stefan,

What is the state of common lisp these days?What is fastest compiler
for X86 and how does it compare to C code in performance?

I was either going to experiment with Forth or lisp in the near
future.   I will get around to both eventually. 

- Don


Stefan Nobis wrote:
 Benjamin Teuber [EMAIL PROTECTED] writes:

   
 Man, we really need a complete Common Lisp Go Framework which also
 has some fast low-level code to show all these C gurus its true
 power :)
 

 I think so, too. :)

 I don't want to say CL is the one and only language (for me surely it
 is), I only try to emphasize that C is not the only choice.

   
 

 ___
 computer-go mailing list
 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/

Re: [computer-go] Drunken sailor on payday

I'm also curious about scheme compilers and the quality of code they
generate.   Does anyone have the dirt on these?

- Don


Stefan Nobis wrote:
 Benjamin Teuber [EMAIL PROTECTED] writes:

   
 Man, we really need a complete Common Lisp Go Framework which also
 has some fast low-level code to show all these C gurus its true
 power :)
 

 I think so, too. :)

 I don't want to say CL is the one and only language (for me surely it
 is), I only try to emphasize that C is not the only choice.

   
 

 ___
 computer-go mailing list
 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/

Re: [computer-go] Drunken sailor on payday

2007-11-22 Thread Benjamin Teuber

AFAIK, CMUCL is the fastest free lisp available. But I would rather
stick with its offspring, SBCL, which might be a bit slower, but it is
being worked on actively, it is quite portable
(http://sbcl.sourceforge.net/platform-table.html) and it supports
native threads (CMUCL just has green threads). Of course it's not easy
to compare speed of different languages, but e.g.
http://shootout.alioth.debian.org/gp4/benchmark.php?test=alllang=all
might give you an idea (oh shame, Java seems faster there).

Cheers,
Ben

On Nov 22, 2007 10:54 PM, Don Dailey [EMAIL PROTECTED] wrote:
 Stefan,

 What is the state of common lisp these days?What is fastest compiler
 for X86 and how does it compare to C code in performance?

 I was either going to experiment with Forth or lisp in the near
 future.   I will get around to both eventually.

 - Don



 Stefan Nobis wrote:
  Benjamin Teuber [EMAIL PROTECTED] writes:
 
 
  Man, we really need a complete Common Lisp Go Framework which also
  has some fast low-level code to show all these C gurus its true
  power :)
 
 
  I think so, too. :)
 
  I don't want to say CL is the one and only language (for me surely it
  is), I only try to emphasize that C is not the only choice.
 
 
  

 
  ___
  computer-go mailing list
  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/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-22 Thread Benjamin Teuber

Maybe this link is a bit more interesting..
http://shootout.alioth.debian.org/gp4/benchmark.php?test=alllang=sbcllang2=gcc

On Nov 23, 2007 12:30 AM, Benjamin Teuber [EMAIL PROTECTED] wrote:
 Of course it's not easy
 to compare speed of different languages, but e.g.
 http://shootout.alioth.debian.org/gp4/benchmark.php?test=alllang=all
 might give you an idea (oh shame, Java seems faster there).
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-22 Thread Russell Wallace

On Nov 22, 2007 12:13 PM, Jacques Basaldúa [EMAIL PROTECTED] wrote:
 I am still waiting to
 meet the first person who answers affirmatively to the question:
 Have you ever paid for a program written in Java?

*raises hand*

You need wait no longer ^.^ - and that was back in the days when Swing
sucked. It's much better these days.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

Thanks for a great read there first of all.

But...  and this is something I see time and again and I must admit I don't
really understand.  What makes C faster than C++?  I feel like C++ is all
about you don't pay for what you don't use.  Furthermore, I feel that C++
has at least one feature that in a one certain special case will result in
faster code.  While I generally would say avoid indirect calls where
performance is critical (for obvious reasons) thereare certain times when it
is faster than climbing through tons of logic.  For these cases, if one
indirect branch is reasonably likely the optimization most recent x86 chips
take with static branch prediction is to assume the [indirect] branch is
not taken which might seem wierd but makes sense since the chip can't
easily guess this information statically.  Good compilers will usually write
the most commonly jumped to location after the indirect uncomditional jump
instruction s

JMP  [EBX]
JMP  default_function

is output.  Unfortunately, C doesnt' have a way to specify this base case.
Trying to code this yourself won't really work either because a C compiler
is likely to notice that the branch is unconditional and remove you branch
that occurs after anyway  Which would be if you were using the low level
jumping routines anyhow.  There are a couple other features as well.

So my question really is, how do you add features to a language (some of
which give you opportunities to optimize things you wouldn't be able to) and
come out slower?  I'm assuming that if you are using C++ you know how to use
discretion in feature use ofcourse.  I also believe there may genuinely be a
reason I don't understand since I see many good programmers picking C over
C++.  Thanks in advance for any explanation you have.

- Nick

On Nov 22, 2007 11:07 AM, Don Dailey [EMAIL PROTECTED] wrote:

 I think we are missing the point of programmer productivity with higher
 level languages.   High level languages MIGHT improve the speed at which
 you write code,   but usually that is a minor concern. In computer
 GO, what you want is the pathway that gives you the best programs in the
 least amount of effort.

 For that,  C currently appears to be the best choice.This in not
 just my opinion, there is empirical evidence to support this claim.
 Take a close look at the very best GO programs in the world,  and I
 doubt you will see Ruby and Python programs.   I doubt you will see Java
 programs. All of these programming languages,  as wonderful as they
 may be and most of which claim dramatically increased productivity,
 simply are not producing.

 Most  arguments for using these languages are nonsense.They focus on
 only one aspect of the total picture - how fast you can write bug-free
 code.Some languages are clearly better than others at that but the
 biggest factor by far is the programmer herself.

 Many say,  it's just not worth a few percent speedup to code in a low
 level language. I hope you realize that few percent is probably
 in the best case around 50%.   We could argue about the exact number,
 but the fact is that you take a substantial hit programming in Java (for
 instance) and that is not even a high level language.

 Computer Go is still in the dark ages but is gradually emerging from it
 - it's starting to be appreciated that 50% represents a significant
 strength improvement.   That probably means it's low hanging fruit -
 in other words you are probably going to get the most improvement for
 your programming time developing and programming in C.

 And yet many will say,  but I would rather spend my time improving the
 algorithm in a language that makes it easy to express my ideas.   I
 might be throwing away 50%,  but I will quickly make up the difference
 with my vastly improved ability to experiment and express my wonderful
 ideas. One might even argue that using a low level language like C
 is actually inhibiting their ability to forge ahead.

 My experience in computer chess is that the people who think this way,
 never catch up.   I call this the drunken sailor approach.   The
 metaphor is the drunken sailor who blows most of his paycheck the day he
 gets it.   He does this, because it seems to him like a lot of money.
 When there is a lot of money in your pocket,  it's easy to spend it
 frivolously and then tighten up when you are almost broke.

 Computers are fast.   You don't mind taking the 2 to 1 hit (or whatever
 it is)  for the extra luxury of programming in a high level language.
 However, this mentality doesn't stop here.   If you are thinking this
 way,  chances are that you take other shortcuts  for the long term
 good.

 The problem is that you never stop taking the hit.You say, in 18
 months computers will be 2X faster, so it doesn't matter.   This is
 the stupidest thing I keep hearing. In 18 months you will have a
 faster computer,  but your program will STILL be a crippled program that
 sucks.

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Petr Baudis

On Thu, Nov 22, 2007 at 11:36:58AM +1800, Nick Apperson wrote:
 Thanks for a great read there first of all.
 
 But...  and this is something I see time and again and I must admit I don't
 really understand.  What makes C faster than C++?  I feel like C++ is all
 about you don't pay for what you don't use.

My personal stance is that the extra cruft and basically mysterious
behaviour in some cases (I know many programmers and even some gcc
developers, and only one or maybe two who can say that they completely
understand identifier lookup mechanism in C++) is not worth the extra
features you are getting. I believe C gives you all the constructs you
really need and frequently the extra C++ constructs just reduce
readability. But this is just question of taste and many people will
like the extra C++ features and that's really ok, too.

I think C++ is much like Perl. Many oh-so-cool features and constructs,
but things can get out of hand real fast. ;-)

(And I do like Perl. Including the cool features and constructs. But
Perl and C are pretty much _the_ two languages I use and I never had too
much motivation to mix the cool features with low level code as in C++.)

 Furthermore, I feel that C++
 has at least one feature that in a one certain special case will result in
 faster code.  While I generally would say avoid indirect calls where
 performance is critical (for obvious reasons) thereare certain times when it
 is faster than climbing through tons of logic.  For these cases, if one
 indirect branch is reasonably likely the optimization most recent x86 chips
 take with static branch prediction is to assume the [indirect] branch is
 not taken which might seem wierd but makes sense since the chip can't
 easily guess this information statically.  Good compilers will usually write
 the most commonly jumped to location after the indirect uncomditional jump
 instruction s
 
 JMP  [EBX]
 JMP  default_function
 
 is output.  Unfortunately, C doesnt' have a way to specify this base case.
 Trying to code this yourself won't really work either because a C compiler
 is likely to notice that the branch is unconditional and remove you branch
 that occurs after anyway  Which would be if you were using the low level
 jumping routines anyhow.  There are a couple other features as well.

This is indeed not standardized but C compilers tend to have their own
extensions for this. Many codebases have likely(a) and unlikely(a) macros
they use in conditions which are defined to expand to

__builtin_expect(!!(a), 1)

or 0 respectively in case the code is compiled by gcc. I'd expect MSVC
to have some similar way to hint this.

(gcc also supports -fprofile-generate and -fprofile-use, which is pretty
cool too - gcc will re-optimize the binary based on profiling
information gathered from a test run of the program. It can be quite a
non-trivial boost.)


However, I don't get how is this related to C vs C++? AFAIK C++ does not
have an official way to hint the compiler about branching probability
either?

-- 
Petr Pasky Baudis
We don't know who it was that discovered water, but we're pretty sure
that it wasn't a fish.  -- Marshall McLuhan
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

right... well C++ does have this using virtual methods.  I meant to add that
part.

C++ also has templates which while they theoretically don't add any
performance.  Practically speaking they add tons because you don't have to
split your optimization time between 10 or more versions of the same
function.  I don't buy the stuff people throw down about programmer
productiveity being more important than raw speed, but if you are starting
at the same speed and it is easier to optimize you will likely get a faster
program.

And I totally agree with you that things can get out of hand fast.  I'd say
C++ is probably one of the hardest languages out there.  Templates can make
code blazingly fast in the general case, but writing them to work well can
be extremely challenging.  Multiple inheritence is somewhat easier to me,
but it can definately trip people up really quickly if they design their
code poorly.  There is a saying I think... but yeah C++ is not made for
people that aren't really good programmers.  No training wheels.

On Nov 22, 2007 11:51 AM, Petr Baudis [EMAIL PROTECTED] wrote:

 On Thu, Nov 22, 2007 at 11:36:58AM +1800, Nick Apperson wrote:
  Thanks for a great read there first of all.
 
  But...  and this is something I see time and again and I must admit I
 don't
  really understand.  What makes C faster than C++?  I feel like C++ is
 all
  about you don't pay for what you don't use.

 My personal stance is that the extra cruft and basically mysterious
 behaviour in some cases (I know many programmers and even some gcc
 developers, and only one or maybe two who can say that they completely
 understand identifier lookup mechanism in C++) is not worth the extra
 features you are getting. I believe C gives you all the constructs you
 really need and frequently the extra C++ constructs just reduce
 readability. But this is just question of taste and many people will
 like the extra C++ features and that's really ok, too.

 I think C++ is much like Perl. Many oh-so-cool features and constructs,
 but things can get out of hand real fast. ;-)

 (And I do like Perl. Including the cool features and constructs. But
 Perl and C are pretty much _the_ two languages I use and I never had too
 much motivation to mix the cool features with low level code as in C++.)

  Furthermore, I feel that C++
  has at least one feature that in a one certain special case will result
 in
  faster code.  While I generally would say avoid indirect calls where
  performance is critical (for obvious reasons) thereare certain times
 when it
  is faster than climbing through tons of logic.  For these cases, if one
  indirect branch is reasonably likely the optimization most recent x86
 chips
  take with static branch prediction is to assume the [indirect] branch
 is
  not taken which might seem wierd but makes sense since the chip can't
  easily guess this information statically.  Good compilers will usually
 write
  the most commonly jumped to location after the indirect uncomditional
 jump
  instruction s
 
  JMP  [EBX]
  JMP  default_function
 
  is output.  Unfortunately, C doesnt' have a way to specify this base
 case.
  Trying to code this yourself won't really work either because a C
 compiler
  is likely to notice that the branch is unconditional and remove you
 branch
  that occurs after anyway  Which would be if you were using the low
 level
  jumping routines anyhow.  There are a couple other features as well.

 This is indeed not standardized but C compilers tend to have their own
 extensions for this. Many codebases have likely(a) and unlikely(a) macros
 they use in conditions which are defined to expand to

__builtin_expect(!!(a), 1)

 or 0 respectively in case the code is compiled by gcc. I'd expect MSVC
 to have some similar way to hint this.

 (gcc also supports -fprofile-generate and -fprofile-use, which is pretty
 cool too - gcc will re-optimize the binary based on profiling
 information gathered from a test run of the program. It can be quite a
 non-trivial boost.)


 However, I don't get how is this related to C vs C++? AFAIK C++ does not
 have an official way to hint the compiler about branching probability
 either?

 --
Petr Pasky Baudis
 We don't know who it was that discovered water, but we're pretty sure
 that it wasn't a fish.  -- Marshall McLuhan
 ___
 computer-go mailing list
 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/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Heikki Levanto

On Wed, Nov 21, 2007 at 12:07:03PM -0500, Don Dailey wrote:
 My advice when this question comes up (which language for go programmer)
 is to first ask,  what do you hope to achieve?If you want to build a
 high performance go program,  anything other than C or assembler is like
 tying your hand behind your back. If you do this only as a hobby and
 have no aspirations (just for fun and pleasure) then by all means, you
 will be much happier in a high level language.

Interesting approach. I like C myself, so even as an amateur just dabbling in
the field, I have used it, and will do so again.

But of course teh choice is never so black and white. If I had unlimited
amount of time (or some student labour available ;-), I would make a good C
library available from higher-level languages, so that the parts that matter
could be fat and efficient C, and those that don't matter, or where lots of
experimentation is useful, could be done in (say) python. 

There just isn't much point in optimizing much out of the 'list_commands'
routine of the gtp interpreter, it is used at msot once per game, and
communicating teh result over a network is going to be much slower than what
ever is done to find the commands...


- Heikki
  who does not plan to do much more in the language war...


-- 
Heikki Levanto   In Murphy We Turst heikki (at) lsd (dot) dk

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Álvaro Begué

On Nov 21, 2007 1:41 PM, Don Dailey [EMAIL PROTECTED] wrote:
  (gcc also supports -fprofile-generate and -fprofile-use, which is pretty
  cool too - gcc will re-optimize the binary based on profiling
  information gathered from a test run of the program. It can be quite a
  non-trivial boost.)

 This puts even more distance between C/C++ and other languages.   I have not 
 yet experimented with this, but I look forward to it.   It delays the day I 
 will be able to code in D unfortunately!

Some chess programmers have told me that this feature works much
better in Visual C++ than in gcc. It's too bad I am not willing to
program in Windows to verify it.

Oh, and I completely agree with everything Don has said. It has taken
me years to learn how to use C++ efficiently, but I think these days I
write code that is as fast as C, it's organized better... and the STL
containers and the std::string class are really nice to have.

Álvaro.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

Hi Nick,

When I say C,  I really mean C or C++. C is basically a useful
subset of C++.

C++ may be closer to the ideal HP language than C.To me, the ideal
language will let you seamlessly step down to high performance coding in
something just as efficient as C but be able to use much higher level
language features without getting in the way of performance - which
after all is what computers are all about.Even though I personally
don't like c++ at least it doesn't invalidate this principle of being
higher level without compromising the low level performance.The idea
is that high level features should be optional.

An interesting language is D.   It's basically C with the option to use
high level constructs and it's quite nice.  It has everything needed to
be a C/C++ replacement.   It was designed specifically to be easy to
optimize (for compilers) and in principle it can be faster than even C
according to the website hype.   I tend to believe this is true because
it's really C code with stuff removed or added to improve (the
opportunities for) compiler optimizations.  However in practice,
it's still noticeably slower (in my tests of GO code, about 1.4 X slower. )

I'm not willing to give up very much performance for things I use C for,
  so I can't yet use D.   But I'm keeping a close eye on it.

  
- Don
 


Nick Apperson wrote:
 Thanks for a great read there first of all.

 But...  and this is something I see time and again and I must admit I
 don't really understand.  What makes C faster than C++?  I feel like
 C++ is all about you don't pay for what you don't use.  Furthermore, I
 feel that C++ has at least one feature that in a one certain special
 case will result in faster code.  While I generally would say avoid
 indirect calls where performance is critical (for obvious reasons)
 thereare certain times when it is faster than climbing through tons of
 logic.  For these cases, if one indirect branch is reasonably likely
 the optimization most recent x86 chips take with static branch
 prediction is to assume the [indirect] branch is not taken which
 might seem wierd but makes sense since the chip can't easily guess
 this information statically.  Good compilers will usually write the
 most commonly jumped to location after the indirect uncomditional jump
 instruction s

 JMP  [EBX]
 JMP  default_function

 is output.  Unfortunately, C doesnt' have a way to specify this base
 case.  Trying to code this yourself won't really work either because a
 C compiler is likely to notice that the branch is unconditional and
 remove you branch that occurs after anyway  Which would be if you
 were using the low level jumping routines anyhow.  There are a couple
 other features as well.

 So my question really is, how do you add features to a language (some
 of which give you opportunities to optimize things you wouldn't be
 able to) and come out slower?  I'm assuming that if you are using C++
 you know how to use discretion in feature use ofcourse.  I also
 believe there may genuinely be a reason I don't understand since I see
 many good programmers picking C over C++.  Thanks in advance for any
 explanation you have.

 - Nick

 On Nov 22, 2007 11:07 AM, Don Dailey [EMAIL PROTECTED]
 mailto:[EMAIL PROTECTED] wrote:

 I think we are missing the point of programmer productivity with
 higher
 level languages.   High level languages MIGHT improve the speed at
 which
 you write code,   but usually that is a minor concern. In
 computer
 GO, what you want is the pathway that gives you the best programs
 in the
 least amount of effort.

 For that,  C currently appears to be the best choice.This in not
 just my opinion, there is empirical evidence to support this claim.
 Take a close look at the very best GO programs in the world,  and I
 doubt you will see Ruby and Python programs.   I doubt you will
 see Java
 programs. All of these programming languages,  as wonderful as
 they
 may be and most of which claim dramatically increased productivity,
 simply are not producing.

 Most  arguments for using these languages are nonsense.They
 focus on
 only one aspect of the total picture - how fast you can write
 bug-free
 code.Some languages are clearly better than others at that but the
 biggest factor by far is the programmer herself.

 Many say,  it's just not worth a few percent speedup to code in a low
 level language. I hope you realize that few percent is
 probably
 in the best case around 50%.   We could argue about the exact number,
 but the fact is that you take a substantial hit programming in
 Java (for
 instance) and that is not even a high level language.

 Computer Go is still in the dark ages but is gradually emerging
 from it
 - it's starting to be appreciated that 50% represents a significant
 strength improvement.

Re: [computer-go] Drunken sailor on payday

sure thing:

--

struct foo {
  // some stuff gets executed
  virtual void do_something(somestruct s); // base case executed by default
};

struct foo_foo : foo {
  // some stuff gets executed
};

struct foo_bar : foo {
  // some stuff gets executed
  virtual void do_something(somestruct s); // special case
};

So then if we have say:

foo *f;
somestruct s;

// ... some code that sets f to something and changes s

f-do_something(s);



So now when the compiler is optimizing the code, it will optimize for the
base case of foo::do_something by default unless it has information that is
even better.  If our code instead read with f as a function pointer, the
compiler (assuming it can't determine the value) won't have a base case.


On Nov 22, 2007 12:18 PM, Petr Baudis [EMAIL PROTECTED] wrote:

 On Thu, Nov 22, 2007 at 12:04:53PM +1800, Nick Apperson wrote:
  right... well C++ does have this using virtual methods.  I meant to add
 that
  part.

 I'm sorry, I still don't get this - what do virtual methods have to do
 with branch prediction? Can you elaborate, please?

 --
Petr Pasky Baudis
 We don't know who it was that discovered water, but we're pretty sure
 that it wasn't a fish.  -- Marshall McLuhan
 ___
 computer-go mailing list
 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/

Re: [computer-go] Drunken sailor on payday

Hi Raymond,

The point I'm making is that you must focus on what's relevant.If
you are trying to win the title of world championship go program, then
maintainability of code is LOW on the list of what is important. In
a corporate environment it moves close to the TOP of the list of what is
important.

Experience in a language is a factor,  but nobody refutes that properly
coded C is fastest (next to properly code assembly) and if performance
is your goal,  then anything else accepts some compromise. That
compromise may work well for a particular individual and may even
produce a stronger program for them,  but it's still a handicap. 

For example,  Mogo probably could be coded in Java and still (probably)
be the best 9x9 program.   If so, then it would be the best despite the
fact that it was coded in Java, not because of it.   They would have had
to overcome a good bit of performance handicap.  

There are some tennis players that could beat me with one hand tied
behind their back,  but that doesn't mean it's the way to go.   They
would have to beat me despite the fact that one hand was tied behind
their back.A player close to my level would not have a chance with
this handicap because it is in fact a handicap, no matter how you cast it.

My feeling is that the engineer who starts his GO programming project in
a high level language is not going to be able to compete with the C
programmer, even if he is given the extra hardware to equalize.I say
this because he has already proven (in some sense) that he can't make
good decisions and you can be reasonably sure that he will make more bad
decisions.For example  you can be relatively sure that he will not
favor doing things fast if he has to write ugly code - after all he has
already made choices that indicates he values high level thinking and
nice code over low level efficiency.In fact it would be rather silly
if he used a high level language, but then resorted to performance tricks.

I don't say this to be ugly or to be critical of java or other
programmers.   These languages are fine choices as long as you don't
believe you are writing a cutting edge high performance go program.  

I am rather curious,  which CGOS program that is NOT in C/C++ or
assembler is highest rated?   Despite all the hype about expressibility
and code maintainability I would guess that the best programs are in C, 
then perhaps Java (since it's relatively fast) and that the weakest are
in the highly productive dynamic programming languages that are slow.

By the way,  I'm a huge advocate of Ruby, one of the slowest
languages! I love this language as well as Lua and others.  However,
common sense must prevail.It's just insane to reach for Ruby to
produce a high performance Go program.  And to a lesser degree Java.


- Don








Raymond Wold wrote:
 Don Dailey wrote:

 For that,  C currently appears to be the best choice.This in not
 just my opinion, there is empirical evidence to support this claim.
  

 The problem with empirical evidence is that you don't get the very
 much needed all else being equal. The people that code in C (and get
 great speeds for the algorithms where speed means a skill increase)
 are people that know C best, that have years of experience in it, and
 also, people that have a different attitude towards /how/ to solve
 problems, /what/ algorithms to write. I suspect that Java coders, and
 especially Haskell, Lisp, etc. coders, are people with significant
 less experience in those languages; partially because you need a lot
 less knowledge about programming to get started and get anywhere, but
 also because these languages have something of the hype about them*,
 and might be chosen as the language merely for being the latest
 language, or the highest-level one, learned so far. And you think
 differently when coding in a higher level language. It might well be
 that the slightly different mindset of low-level programmers is more
 suited for go. It might be that we /need/ a domain specific language
 for go.

 But none of this means that the /speed of execution/ is the crucial
 factor, or even an important one. Yes, perhaps the same algorithm in
 Haskell is ten times as slow as one in assembler. But does that mean
 that if you give a Haskell coder ten times as powerful hardware, that
 he'll be able to compete with the C coder? I'm not so sure.

 The maintainability aspect is not to be laughed at either. Once you
 get above a certain size in complexity of the program, having it in C
 from the start will mean a much greater inertia against expanding and
 experimenting with what you have. And I suspect go programms will have
 to go above this to beat the current set of algorithms. As seducing as
 the idea that there's an elegant solution is, I don't think it's
 realistic. And then we'll need the added clarity of high-level
 programming.

 *) Without that meaning they're worse languages for being hyped, or
 being

Re: [computer-go] Drunken sailor on payday

 (gcc also supports -fprofile-generate and -fprofile-use, which is pretty
 cool too - gcc will re-optimize the binary based on profiling
 information gathered from a test run of the program. It can be quite a
 non-trivial boost.)

This puts even more distance between C/C++ and other languages.   I have not 
yet experimented with this, but I look forward to it.   It delays the day I 
will be able to code in D unfortunately!

- Don



   
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

One thing that I haven't check into is whether the GDC D compiler has
these same options for profiling code and using the profile to further
improve the code.   If it does, then the performance gap between C and D
may not increase.

- Don


Don Dailey wrote:
 (gcc also supports -fprofile-generate and -fprofile-use, which is pretty
 cool too - gcc will re-optimize the binary based on profiling
 information gathered from a test run of the program. It can be quite a
 non-trivial boost.)
 

 This puts even more distance between C/C++ and other languages.   I have not 
 yet experimented with this, but I look forward to it.   It delays the day I 
 will be able to code in D unfortunately!

 - Don



   
   
 
 ___
 computer-go mailing list
 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/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Raymond Wold


Don Dailey wrote:


For that,  C currently appears to be the best choice.This in not
just my opinion, there is empirical evidence to support this claim.
 

The problem with empirical evidence is that you don't get the very 
much needed all else being equal. The people that code in C (and get 
great speeds for the algorithms where speed means a skill increase) are 
people that know C best, that have years of experience in it, and also, 
people that have a different attitude towards /how/ to solve problems, 
/what/ algorithms to write. I suspect that Java coders, and especially 
Haskell, Lisp, etc. coders, are people with significant less experience 
in those languages; partially because you need a lot less knowledge 
about programming to get started and get anywhere, but also because 
these languages have something of the hype about them*, and might be 
chosen as the language merely for being the latest language, or the 
highest-level one, learned so far. And you think differently when coding 
in a higher level language. It might well be that the slightly different 
mindset of low-level programmers is more suited for go. It might be that 
we /need/ a domain specific language for go.


But none of this means that the /speed of execution/ is the crucial 
factor, or even an important one. Yes, perhaps the same algorithm in 
Haskell is ten times as slow as one in assembler. But does that mean 
that if you give a Haskell coder ten times as powerful hardware, that 
he'll be able to compete with the C coder? I'm not so sure.


The maintainability aspect is not to be laughed at either. Once you get 
above a certain size in complexity of the program, having it in C from 
the start will mean a much greater inertia against expanding and 
experimenting with what you have. And I suspect go programms will have 
to go above this to beat the current set of algorithms. As seducing as 
the idea that there's an elegant solution is, I don't think it's 
realistic. And then we'll need the added clarity of high-level programming.


*) Without that meaning they're worse languages for being hyped, or 
being picked up for word of mouth value only.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Petr Baudis

On Thu, Nov 22, 2007 at 12:04:53PM +1800, Nick Apperson wrote:
 right... well C++ does have this using virtual methods.  I meant to add that
 part.

I'm sorry, I still don't get this - what do virtual methods have to do
with branch prediction? Can you elaborate, please?

-- 
Petr Pasky Baudis
We don't know who it was that discovered water, but we're pretty sure
that it wasn't a fish.  -- Marshall McLuhan
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Jason House

On Nov 21, 2007 1:18 PM, Petr Baudis [EMAIL PROTECTED] wrote:

 On Thu, Nov 22, 2007 at 12:04:53PM +1800, Nick Apperson wrote:
  right... well C++ does have this using virtual methods.  I meant to add
 that
  part.

 I'm sorry, I still don't get this - what do virtual methods have to do
 with branch prediction? Can you elaborate, please?



I don't know about branch predictions, but virtual functions have additional
overhead with figuring out which function to call.  They will also prevent
function inlining.  Both effects can yield a slow down in your code.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

Heikki,

Yes,  I like your approach of a library and using high level language. 

One must be careful that it doesn't get in the way.   Sometimes, the low
level library imposes some constraints so that you still don't quite get
the best of both worlds.

For example it would be great if you could use inline-perl to do
something like this, but it's not easy to use a C data structure with
perl, or visa versa.   

So you might end up with a program that is pretty much a C program with
just a few routines (like GTP) and the user interface written in perl or
python or whatever high level language you use.

They key is that you still want almost all the time (to get ultimate
performance) spent in the C library.   If 90% of the time is spent in
the library, then 99% of the executed code must be in C!  That' s
because a routine that might be insignificant written in C, might not be
so insignificant written in python.

Here is an example.   Let's say you have a fast C library that can make 
80,000 play-outs per second.   The python script could call the routine
that makes the playouts, but what is overhead from those 80,000 calls?  
It's not just the calls, but the results must be converted to a python
representation if the python program works with it.   

But if this is not much overhead, do you put the play-outs in the python
code too?   Perhaps you code the low level routines in C but a Python
routine is driving the process of a single random play-out?

My guess, is that most of the guts of the program still have to be
written in C and that the Python wrapper won't do very much interesting
stuff.   It's probably fine to do it this way and may save you some
time - but you are not really getting much of the benefit of the high
level program - you are not doing anything really important  in the
Python code.  

Nevertheless,  even if you only had a few low level C routines and let
Python do a lot of work,  you would having something MUCH faster than
pure Python and could do most of your experimentation in Python once you
had this library.Of course you wouldn't really have a high
performance program.   

It's hard to say just how far you could take and still be able to
benefit significantly from using Python or some other high level language.


- Don







Heikki Levanto wrote:
 On Wed, Nov 21, 2007 at 12:07:03PM -0500, Don Dailey wrote:
   
 My advice when this question comes up (which language for go programmer)
 is to first ask,  what do you hope to achieve?If you want to build a
 high performance go program,  anything other than C or assembler is like
 tying your hand behind your back. If you do this only as a hobby and
 have no aspirations (just for fun and pleasure) then by all means, you
 will be much happier in a high level language.
 

 Interesting approach. I like C myself, so even as an amateur just dabbling in
 the field, I have used it, and will do so again.

 But of course teh choice is never so black and white. If I had unlimited
 amount of time (or some student labour available ;-), I would make a good C
 library available from higher-level languages, so that the parts that matter
 could be fat and efficient C, and those that don't matter, or where lots of
 experimentation is useful, could be done in (say) python. 

 There just isn't much point in optimizing much out of the 'list_commands'
 routine of the gtp interpreter, it is used at msot once per game, and
 communicating teh result over a network is going to be much slower than what
 ever is done to find the commands...


 - Heikki
   who does not plan to do much more in the language war...


   
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Raymond Wold

On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote:
 Experience in a language is a factor,  but nobody refutes that properly
 coded C is fastest (next to properly code assembly) and if performance
 is your goal,  then anything else accepts some compromise. That
 compromise may work well for a particular individual and may even
 produce a stronger program for them,  but it's still a handicap. 

Do you have anything to back this up? I was under the impression that
most decent assembly programmers agreed that they can't compete with the
best C compilers. Assembly is for when you *need* to be in touch with
the very lowest level, which in most cases you don't, because lots and
lots of other assembly programmers have been there before you and
distilled their knowledge into really really smart compilers that know
more, and can try out more, than you ever could in a lifetime.

 For example,  Mogo probably could be coded in Java and still (probably)
 be the best 9x9 program.   If so, then it would be the best despite the
 fact that it was coded in Java, not because of it.   They would have had
 to overcome a good bit of performance handicap.  

Because its algorithms are well suited for more cycles.

 My feeling is that the engineer who starts his GO programming project in
 a high level language is not going to be able to compete with the C
 programmer, even if he is given the extra hardware to equalize.I say
 this because he has already proven (in some sense) that he can't make
 good decisions and you can be reasonably sure that he will make more bad
 decisions.For example  you can be relatively sure that he will not
 favor doing things fast if he has to write ugly code - after all he has
 already made choices that indicates he values high level thinking and
 nice code over low level efficiency.In fact it would be rather silly
 if he used a high level language, but then resorted to performance tricks.

See, the thing about (most) high-level languages is that the ugly
optimization is a myth. In a high-level language, the optimizers will
work best with *correct* code, coded as the language was intended, and
programmers who try to optimize invariably /slow down/ their code.

 I don't say this to be ugly or to be critical of java or other
 programmers.   These languages are fine choices as long as you don't
 believe you are writing a cutting edge high performance go program.  

This assumes that to be cutting edge, cycles matter. If your algorithms
are such that doubling the execution time available means a 0.01%
increase in wins (this is *obviously* not true for a Monte Carlo-heavy
program, but might be for others), then giving up clarity is not worth
it. And if that 0.01% increase means you'll spend weeks extra
programming, because you have to recode something from scratch instead
of using a simple refactoring, the high-level language IS a fine choice.

 I am rather curious,  which CGOS program that is NOT in C/C++ or
 assembler is highest rated?   Despite all the hype about expressibility
 and code maintainability I would guess that the best programs are in C, 
 then perhaps Java (since it's relatively fast) and that the weakest are
 in the highly productive dynamic programming languages that are slow.

This is because, at the current point in time, Monte Carlo programs
dominate. *This* *can* *change*.



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Petr Baudis

On Wed, Nov 21, 2007 at 09:16:48PM +0100, Raymond Wold wrote:
 On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote:
  Experience in a language is a factor,  but nobody refutes that properly
  coded C is fastest (next to properly code assembly) and if performance
  is your goal,  then anything else accepts some compromise. That
  compromise may work well for a particular individual and may even
  produce a stronger program for them,  but it's still a handicap. 
 
 Do you have anything to back this up? I was under the impression that
 most decent assembly programmers agreed that they can't compete with the
 best C compilers. Assembly is for when you *need* to be in touch with
 the very lowest level, which in most cases you don't, because lots and
 lots of other assembly programmers have been there before you and
 distilled their knowledge into really really smart compilers that know
 more, and can try out more, than you ever could in a lifetime.

I guess that you could say the original statement holds but humans
generally can't properly code assembly anymore. ;-)

 This assumes that to be cutting edge, cycles matter. If your algorithms
 are such that doubling the execution time available means a 0.01%
 increase in wins (this is *obviously* not true for a Monte Carlo-heavy
 program, but might be for others), then giving up clarity is not worth
 it. And if that 0.01% increase means you'll spend weeks extra
 programming, because you have to recode something from scratch instead
 of using a simple refactoring, the high-level language IS a fine choice.

I think that's somewhat contrived as well. I don't have that good idea
about all the populat computer go algorithsm, do you have example of
reasonably performing algorithm with these properties?

-- 
Petr Pasky Baudis
We don't know who it was that discovered water, but we're pretty sure
that it wasn't a fish.  -- Marshall McLuhan
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

On Nov 21, 2007 3:36 PM, Petr Baudis [EMAIL PROTECTED] wrote:
 On Wed, Nov 21, 2007 at 09:16:48PM +0100, Raymond Wold wrote:
  On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote:
   Experience in a language is a factor,  but nobody refutes that properly
   coded C is fastest (next to properly code assembly) and if performance
   is your goal,  then anything else accepts some compromise. That
   compromise may work well for a particular individual and may even
   produce a stronger program for them,  but it's still a handicap.
 
  Do you have anything to back this up? I was under the impression that
  most decent assembly programmers agreed that they can't compete with the
  best C compilers. Assembly is for when you *need* to be in touch with
  the very lowest level, which in most cases you don't, because lots and
  lots of other assembly programmers have been there before you and
  distilled their knowledge into really really smart compilers that know
  more, and can try out more, than you ever could in a lifetime.

 I guess that you could say the original statement holds but humans
 generally can't properly code assembly anymore. ;-)


What's to say that a computer program can't code assembly better than
any human possibly could?  There are a ton of tasks that computers do
thousands of times better than humans.  I think it makes perfect sense
that code written in C can execute faster than human-written assembly
code.

Colin
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Adrian Grajdeanu

Nick, do you know for a fact that a C++ complier will optimize for the 
base case of a virtual function? I was under the impression that it 
doesn't know (as in can't determine at compile time) whether the 
function was overwritten or not so it doesn't favor any of the cases. In 
fact I can't even figure how it would if it wanted to optimize an 
indirect function call.
I'm not trying to start a war, just to clarify my assumption. As it is I 
generally write code using virtual functions that I most often do 
overwrite. If what you say is true, then I am incurring the penalty most 
of the time and that would be bad...


Cheers,
Adrian


Nick Apperson wrote:

sure thing:

--

struct foo {
  // some stuff gets executed
  virtual void do_something(somestruct s); // base case executed by default
};

struct foo_foo : foo {
  // some stuff gets executed
};

struct foo_bar : foo {
  // some stuff gets executed
  virtual void do_something(somestruct s); // special case
};

So then if we have say:

foo *f;
somestruct s;

// ... some code that sets f to something and changes s

f-do_something(s);



So now when the compiler is optimizing the code, it will optimize for 
the base case of foo::do_something by default unless it has information 
that is even better.  If our code instead read with f as a function 
pointer, the compiler (assuming it can't determine the value) won't have 
a base case.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Stefan Nobis

Don Dailey [EMAIL PROTECTED] writes:

 To me, the ideal language will let you seamlessly step down to high
 performance coding in something just as efficient as C but be able
 to use much higher level language features without getting in the
 way of performance

Hmmm... you are just describing Common Lisp. :)

Just for the records: There are complete operating systems written in
Lisp on hardware much less capable than today not to mention all the
tools and applications -- many of the features of the Lisp Machine and
similiar systems are emerging today in tools like Visual Studio
selling it to the uninformed as genuine new ideas (intellisense, LINQ,
anonymous classes/functions, functions as first class objects,
closures, live debugging with on the fly code changes (oh, Visual
Studio has quite a long way to go to get the same flexibility in
debugging Lisp systems had 30-40 years ago) and much more).

As I said before: C has quite some drawbacks -- performance
wise. There are a couple of things in the standard preventing perfect
performance (calling conventions comes to mind but IIRC there are
more).

And as I said before: In many cases it's easier to get to decent
performance with C, but it's hard to get best performance in any
language and more often than not it's possible to get best or nearly
best performance even in a dynamic typed and very high level language
like Common Lisp (partly because there is no ABI defined for CL, so
compilers have much more freedom than C compilers).

One last point: You mentioned 50% speed gain is a big deal. No it's
not. If all you do is brute force computing then you are right. But
for me developing a Go engine is about complete new algorithms and
ideas, I'm not interested in (pure) monte carlo like engines. And if
you play with ideas, often redesigning the complete engine than C is
really bad and higher level language are much more handy.

So it depends very much on you goals. The main point being: Know your
tools, know your goals and then choose the right tool (so you're right
for monte carlo like engines -- the overall design is well-known,
performance is the key, so a language like C (I think, I might prefer
Ada) is quite a good choice).

-- 
Until the next mail...,
Stefan.


pgpUwP5hPBlWe.pgp
Description: PGP signature
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Stuart A. Yeates

On 21/11/2007, Adrian Grajdeanu [EMAIL PROTECTED] wrote:
 Nick, do you know for a fact that a C++ complier will optimize for the
 base case of a virtual function? I was under the impression that it
 doesn't know (as in can't determine at compile time) whether the
 function was overwritten or not so it doesn't favor any of the cases. In
 fact I can't even figure how it would if it wanted to optimize an
 indirect function call.
 I'm not trying to start a war, just to clarify my assumption. As it is I
 generally write code using virtual functions that I most often do
 overwrite. If what you say is true, then I am incurring the penalty most
 of the time and that would be bad...

A C++ compiler can make those kinds of assumptions if the object is
created within the current compilation unit and can not be overwritten
from outside it. There are a whole class of optimizations in Java, C
and C++ which can only be applied under these circumstances, which
rely on concepts of scope. Whether or not a particular compiler uses
these optimizations in a particular case is another matter.

cheers
stuart
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Benjamin Teuber

On Nov 21, 2007 10:22 PM, Stefan Nobis [EMAIL PROTECTED] wrote:

 Hmmm... you are just describing Common Lisp. :)

Man, we really need a complete Common Lisp Go Framework which also has
some fast low-level code to show all these C gurus its true power :)

Maybe we should really think of a project - doesn't have to be the one
I started (now I find most of it ugly..)

Who'd be in?

Cheers,
Ben
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

RE: [computer-go] Drunken sailor on payday

2007-11-21 Thread Ben Lambrechts

 Some chess programmers have told me that this feature works much
 better in Visual C++ than in gcc. It's too bad I am not willing to
 program in Windows to verify it.

I have compiled GNU Go with both GCC and Visual C++ 2008. The binary of
Visual C++ was almost half the size of the GCC one, but 3 times slower.
I think I choose for the speed instead of the size.

Ben

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread wing

 What's to say that a computer program can't code assembly better than
 any human possibly could?  There are a ton of tasks that computers do
 thousands of times better than humans.  I think it makes perfect sense
 that code written in C can execute faster than human-written assembly
 code.

No compiler will ever do *all* of the optimizations
that are possible, because most optimizations are
NP-complete or even much worse. For example the
equivalance of boolean expressions is NP-complete.
Some potential optimizations (such as replacement
of data structures) may not even computable.
This is why humans must choose the algorithms and
data strucures.

Compilers are very good at *small, local optimizations*,
such as putting variables in registers, common
sub-expression elimination, and choosing the fastest
instructions. Compilers almost always
outperform humans on these tasks because compilers
consistently try every trick they know, and they
don't get tired.

Even way back in the 1970s, studies showed that
optimizers consistently outperformed humans on
these tasks, and back then, many people
still practiced doing assembler regularly.

Today, performance combines programmer and compiler
intelligence. Neither can replace the other.
Please use both.

Michael Wing

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

On Nov 21, 2007 5:37 PM, Ben Lambrechts [EMAIL PROTECTED] wrote:
  Some chess programmers have told me that this feature works much
  better in Visual C++ than in gcc. It's too bad I am not willing to
  program in Windows to verify it.

 I have compiled GNU Go with both GCC and Visual C++ 2008. The binary of
 Visual C++ was almost half the size of the GCC one, but 3 times slower.
 I think I choose for the speed instead of the size.

 Ben


I'm not sure about the Visual C++ compiler, but with GCC there are a
number of options for optimization, some sacrificing size for speed,
and others vice versa.  It could just be a matter of compiler options.

Colin
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

On Nov 21, 2007 6:12 PM,  [EMAIL PROTECTED] wrote:
  What's to say that a computer program can't code assembly better than
  any human possibly could?  There are a ton of tasks that computers do
  thousands of times better than humans.  I think it makes perfect sense
  that code written in C can execute faster than human-written assembly
  code.

 No compiler will ever do *all* of the optimizations
 that are possible, because most optimizations are
 NP-complete or even much worse. For example the
 equivalance of boolean expressions is NP-complete.
 Some potential optimizations (such as replacement
 of data structures) may not even computable.
 This is why humans must choose the algorithms and
 data strucures.

 Compilers are very good at *small, local optimizations*,
 such as putting variables in registers, common
 sub-expression elimination, and choosing the fastest
 instructions. Compilers almost always
 outperform humans on these tasks because compilers
 consistently try every trick they know, and they
 don't get tired.

 Even way back in the 1970s, studies showed that
 optimizers consistently outperformed humans on
 these tasks, and back then, many people
 still practiced doing assembler regularly.

 Today, performance combines programmer and compiler
 intelligence. Neither can replace the other.
 Please use both.

 Michael Wing


So this seems to support the idea that C code is potentially faster
than hand-coded assembly, because the more complicated optimizations
can be done by the programmer in C while the optimizations better
suited to a computer are done by the compiler.  Although it would also
be possible to hand-code in assembly and then run a program to
optimize it, but then it seems like there is no advantage over C.  As
far as I can tell, the optimizations that a compiler can't do are
higher-level optimizations that can be done in C and wouldn't require
the programmer to write assembly, or am I wrong about this?

Colin
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread wing

  No compiler will ever do *all* of the optimizations
  that are possible, because most optimizations are
  NP-complete or even much worse. For example the
  equivalance of boolean expressions is NP-complete.
  Some potential optimizations (such as replacement
  of data structures) may not even computable.
  This is why humans must choose the algorithms and
  data strucures.
 
  Compilers are very good at *small, local optimizations*,
  such as putting variables in registers, common
  sub-expression elimination, and choosing the fastest
  instructions. Compilers almost always
  outperform humans on these tasks because compilers
  consistently try every trick they know, and they
  don't get tired.
 
  Even way back in the 1970s, studies showed that
  optimizers consistently outperformed humans on
  these tasks, and back then, many people
  still practiced doing assembler regularly.
 
  Today, performance combines programmer and compiler
  intelligence. Neither can replace the other.
  Please use both.

 So this seems to support the idea that C code is potentially faster
 than hand-coded assembly, because the more complicated optimizations
 can be done by the programmer in C while the optimizations better
 suited to a computer are done by the compiler.  Although it would also
 be possible to hand-code in assembly and then run a program to
 optimize it, but then it seems like there is no advantage over C.  As
 far as I can tell, the optimizations that a compiler can't do are
 higher-level optimizations that can be done in C and wouldn't require
 the programmer to write assembly, or am I wrong about this?

To extend your thought: well-written code in any HLL (like C, C++,
Java, Fortran, D, etc.) will in-general out-perform assembler,
because the programmer can do better algorithms and data structures,
and compilers are better at assembler.

There is one major exception. I have seen several apps where
programmers wrote a few functions in assembler for speed,
for example to use the SIMD instructions. But, that was only
a few functions out of an entire app.

Data structures and algorithms are very important. Given the
success of MC and UCT, there seems to be a lot of enthusiasm for
performance. But, even improving performance by a factor of
10 by using assembler will not make MC and UCT play professional
level go on 19*19. We still need to find much better algorithms
and data structures.

Michael Wing


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

2007-11-21 Thread Christoph Birk



On Nov 21, 2007, at 12:16 PM, Raymond Wold wrote:


This assumes that to be cutting edge, cycles matter. If your  
algorithms

are such that doubling the execution time available means a 0.01%
increase in wins (this is *obviously* not true for a Monte Carlo-heavy
program, but might be for others), then giving up clarity is not worth
it. And if that 0.01% increase means you'll spend weeks extra
programming, because you have to recode something from scratch instead
of using a simple refactoring, the high-level language IS a fine  
choice.


Do you seriously believe that any good Go- (or any other complex game)
programm can be written that could not be improved by faster hardware?

Christoph

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday



Raymond Wold wrote:
 On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote:
   
 Experience in a language is a factor,  but nobody refutes that properly
 coded C is fastest (next to properly code assembly) and if performance
 is your goal,  then anything else accepts some compromise. That
 compromise may work well for a particular individual and may even
 produce a stronger program for them,  but it's still a handicap. 
 

 Do you have anything to back this up? I was under the impression that
 most decent assembly programmers agreed that they can't compete with the
 best C compilers. Assembly is for when you *need* to be in touch with
 the very lowest level, which in most cases you don't, because lots and
 lots of other assembly programmers have been there before you and
 distilled their knowledge into really really smart compilers that know
 more, and can try out more, than you ever could in a lifetime.
   
I know that there are assembler programmers who specialize in the skills
requires to beat C code.However, there is no need to back this up.  
You can express any C program in assembler and better C compilers do
this better and they continue to improve.  Until C compilers are
perfect,  then it will always be possible to express a (non-trivial)
program in more efficient assembler code.



   
 For example,  Mogo probably could be coded in Java and still (probably)
 be the best 9x9 program.   If so, then it would be the best despite the
 fact that it was coded in Java, not because of it.   They would have had
 to overcome a good bit of performance handicap.  
 

 Because its algorithms are well suited for more cycles.

   
 My feeling is that the engineer who starts his GO programming project in
 a high level language is not going to be able to compete with the C
 programmer, even if he is given the extra hardware to equalize.I say
 this because he has already proven (in some sense) that he can't make
 good decisions and you can be reasonably sure that he will make more bad
 decisions.For example  you can be relatively sure that he will not
 favor doing things fast if he has to write ugly code - after all he has
 already made choices that indicates he values high level thinking and
 nice code over low level efficiency.In fact it would be rather silly
 if he used a high level language, but then resorted to performance tricks.
 

 See, the thing about (most) high-level languages is that the ugly
 optimization is a myth. In a high-level language, the optimizers will
 work best with *correct* code, coded as the language was intended, and
 programmers who try to optimize invariably /slow down/ their code.
   
Perhaps in the general case.   Perhaps most humans will fail.   But
skillful humans can find ways to optimize the code by doing unnatural or
ugly things - it's just getting more difficult.



 I don't say this to be ugly or to be critical of java or other
 programmers.   These languages are fine choices as long as you don't
 believe you are writing a cutting edge high performance go program.  
 

 This assumes that to be cutting edge, cycles matter. 
Of course it does - that is my assumption and I stated it.

 If your algorithms
 are such that doubling the execution time available means a 0.01%
 increase in wins (this is *obviously* not true for a Monte Carlo-heavy
 program, but might be for others), then giving up clarity is not worth
 it. And if that 0.01% increase means you'll spend weeks extra
 programming, because you have to recode something from scratch instead
 of using a simple refactoring, the high-level language IS a fine choice.
   
This is my opinion but if your program is such that it doesn't benefit
from increased cycles, then your code is written wrong - certainly you
have hit a dead end by definition.


   
 I am rather curious,  which CGOS program that is NOT in C/C++ or
 assembler is highest rated?   Despite all the hype about expressibility
 and code maintainability I would guess that the best programs are in C, 
 then perhaps Java (since it's relatively fast) and that the weakest are
 in the highly productive dynamic programming languages that are slow.
 

 This is because, at the current point in time, Monte Carlo programs
 dominate. *This* *can* *change*.

   
It changes practically every day.None of these programs are the same
and some don't even use UCT now.  

Even the non-scalable programs are scalable now - they are just hard
coded for a given platform.   The programmer has to make some changes
and recompile them to work right on the next faster machine. They
usually tweak and optimize at the same time, but that in itself is not
scalability. 

- Don



 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

   
___
computer-go mailing list
computer-go@computer-go.org

Re: [computer-go] Drunken sailor on payday



Colin Kern wrote:
 On Nov 21, 2007 3:36 PM, Petr Baudis [EMAIL PROTECTED] wrote:
   
 On Wed, Nov 21, 2007 at 09:16:48PM +0100, Raymond Wold wrote:
 
 On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote:
   
 Experience in a language is a factor,  but nobody refutes that properly
 coded C is fastest (next to properly code assembly) and if performance
 is your goal,  then anything else accepts some compromise. That
 compromise may work well for a particular individual and may even
 produce a stronger program for them,  but it's still a handicap.
 
 Do you have anything to back this up? I was under the impression that
 most decent assembly programmers agreed that they can't compete with the
 best C compilers. Assembly is for when you *need* to be in touch with
 the very lowest level, which in most cases you don't, because lots and
 lots of other assembly programmers have been there before you and
 distilled their knowledge into really really smart compilers that know
 more, and can try out more, than you ever could in a lifetime.
   
 I guess that you could say the original statement holds but humans
 generally can't properly code assembly anymore. ;-)

 

 What's to say that a computer program can't code assembly better than
 any human possibly could?  There are a ton of tasks that computers do
 thousands of times better than humans.  I think it makes perfect sense
 that code written in C can execute faster than human-written assembly
 code.
   
I hope you are right.   I don't want to code in assembly. 

But you are probably wrong because ansi C is platform portable and there
are some things that might be done in assembler that cannot be naturally
expressed in C.One example of this is an operation to find the
leftmost or rightmost bit in a 32 or 64 bit word.  Many processors have
instructions for this,  but there is no such instruction in C. Of
course not all processors implement this efficiently, but we can assume
that there might be some that do,   or perhaps other instructions like
this that ARE implemented efficiently with a single instruction in
assembly, but require many in C.

Of course you could argue that a super-clever C compiler may someday
recognize what is going on and substitute the appropriate processor
instruction for the C function. But that would take a truly amazing
compiler that could do this in the general case.   When that day comes, 
compilers may decide to completely reorganize your code, choosing more
efficient algorithms!

- Don





 Colin
 ___
 computer-go mailing list
 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/

Re: [computer-go] Drunken sailor on payday

On Nov 21, 2007 7:24 PM, Don Dailey [EMAIL PROTECTED] wrote:


 Raymond Wold wrote:
  On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote:
 
  Experience in a language is a factor,  but nobody refutes that properly
  coded C is fastest (next to properly code assembly) and if performance
  is your goal,  then anything else accepts some compromise. That
  compromise may work well for a particular individual and may even
  produce a stronger program for them,  but it's still a handicap.
 
 
  Do you have anything to back this up? I was under the impression that
  most decent assembly programmers agreed that they can't compete with the
  best C compilers. Assembly is for when you *need* to be in touch with
  the very lowest level, which in most cases you don't, because lots and
  lots of other assembly programmers have been there before you and
  distilled their knowledge into really really smart compilers that know
  more, and can try out more, than you ever could in a lifetime.
 
 I know that there are assembler programmers who specialize in the skills
 requires to beat C code.However, there is no need to back this up.
 You can express any C program in assembler and better C compilers do
 this better and they continue to improve.  Until C compilers are
 perfect,  then it will always be possible to express a (non-trivial)
 program in more efficient assembler code.


But the point is that humans are also not perfect, and so they too
can't automatically write the optimal assembly code.  The question is
whether the massively superior processing power of a computer gives it
an advantage over the creative ability of a human.

Colin
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Drunken sailor on payday

My mind is open on this.   I'm not a lisp programmer but I have
considered learning it at some point and I'm sure I will.

- Don


Benjamin Teuber wrote:
 On Nov 21, 2007 10:22 PM, Stefan Nobis [EMAIL PROTECTED] wrote:

   
 Hmmm... you are just describing Common Lisp. :)
 

 Man, we really need a complete Common Lisp Go Framework which also has
 some fast low-level code to show all these C gurus its true power :)

 Maybe we should really think of a project - doesn't have to be the one
 I started (now I find most of it ugly..)

 Who'd be in?

 Cheers,
 Ben
 ___
 computer-go mailing list
 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/

Re: [computer-go] Drunken sailor on payday