CL implementation speed (Re: [computer-go] Drunken sailor on payday)

[William Harold Newman]

On Fri, Nov 23, 2007 at 12:30:01AM +0100, Benjamin Teuber wrote:
> 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=all&lang=all
> might give you an idea (oh shame, Java seems faster there).

There are two kinds of compiler speed. 

The first kind of speed is how fast the compiled program runs after it
has been compiled. SBCL didn't lose much of that speed in the fork
from CMU CL, and since then it has been at least as actively developed
as as CMU CL has been, so it generally hasn't fallen behind. While
it's probably not hard to find benchmarks where CMU CL beats SBCL, I
believe it's fair to say the speed of SBCL's compiled code is
basically at least competitive with that of CMU CL's compiled code.

(And generally I'd expect CMU CL and SBCL to produce the fastest
compiled code, OpenMCL to be next, and CLISP to be significantly
slower on any code where its lack of native compilation (only byte
code) creates a bottleneck.)

The second kind of speed is how fast the compiler translates source
code into compiled programs. SBCL was originally notoriously slow at
that compared to CMU CL (which was, incidentally, my fault personally,
due to choices I made in the fork from CMU CL to SBCL). These days,
though, SBCL's speed at that is more nearly competitive with that of
CMU CL (mostly thanks to work of others, not me). For some benchmarks
on compilation speed in bad-old-days SBCL, reasonably-recent SBCL, and
CMU CL, see
  
http://jsnell.iki.fi/blog/archive/2007-02-07-compilation-speed-in-sbcl-over-the-years.html


> On Nov 22, 2007 10:54 PM, Don Dailey <[EMAIL PROTECTED]> wrote:
> > 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'll punt on "state of CL," and answer the other two questions
separately.


Re: What is fastest CL compiler for X86?

Here's my rough guess; take it for what it's worth. (I know a lot
about SBCL and CMU CL and Lisp in general, to the point where I'm
likely biased. and I have only ever put serious effort into optimizing
performance of one sizable piece of CL code, and that was in CMU CL
back in the last millennium.)

In many cases the free compilers SBCL and/or CMU CL will be fastest.
They are sufficiently closely related that if one is the fastest, it's
fairly likely that the other one will be second fastest. (And the
commercial "scieneer" compiler is also related, but I haven't heard
much about that for years.)

In many cases the commercial compiler Allegro CL will be fastest. In
particular, Allegro apparently compiles Common Lisp Object System code
using a rather different scheme than SBCL and CMU CL do, one which is
supposed to be generally more clever. (SBCL and CMU CL use the old
public reference implementation of CLOS-in-CL plus years of tweaking;
Allegro CL uses a CLOS-in-native-code which was apparently written
independently from scratch.) If you write an arbitrary representative
piece of code where object allocation and/or method dispatch are the
bottleneck, I'd expect Allegro to be faster.

I really don't know much about the rest of Allegro's general compiler
design or how heavily it's been tweaked in practice, so I can't guess
where else its performance might be better. I'd be surprised, though,
if it's generally much better. (As an SBCL fan, I was tickled to run
across an Allegro advocate listing many bullet points in its favor ---
various impressive libraries, e.g. --- but not general performance.:-)

Probably in a few cases the free CLISP byte-compiler will be fastest.
It labors under the handicap of being a byte-compiled language, but in
a calculation which spends most of its time in libraries, that
handicap can be overcome by better library performance. And CLISP's
huge-integer library routines, in particular, are supposed to be very
good in some ways, so it wouldn't surprise me if CLISP could win in
various number-theory-related calculations (like public-key crypto).

There may also be other subclasses of program, and contenders for
fastest-CL-on-X86, which I don't happen to know about.


Re: How does it (CL in general, and on X86 in particular) compare to C
in performance?

It seems to me that it is often pretty easy to make CL code approach
the performance of C code within a factor of three or so. The main
exception in my experience is when you wander into a niche where CL's
machine model is a particularly poor fit to the underlying CPU
capabilities. For me, on the X86 target you asked about, by far the
biggest such niche is passing around globally-visible floating point
numbers (as opposed to numbe

Re: [computer-go] Drunken sailor on payday

[Christoph Birk]

On Nov 25, 2007, at 10:52 AM, Ian Osgood wrote:



On Nov 25, 2007, at 10:29 AM, Ian Osgood wrote:



Folks might be interested in the Common Lisp chess program  
"Symbolic" by Steven J. Edwards (of PGN fame). From his ICC  
description:


Symbolic is a C++/Lisp chessplaying program written by S. J.  
Edwards. Symbolic's C++ source is fully ANSI/POSIX compliant and  
portable. Symbolic includes a ChessLisp interpreter for running  
its Lisp code. Neither source nor object code is publically  
available. One day, all interesting chess programs will be written  
in Lisp. Bit twiddling is not a pathway to Artificial Intelligence.


Did he just use the current chess programming algorithms and re-write
them in Lisp?
If yes, I don't see his approach as a "pathway to AI" either.

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

[Ian Osgood]

On Nov 25, 2007, at 10:29 AM, Ian Osgood wrote:



Folks might be interested in the Common Lisp chess program  
"Symbolic" by Steven J. Edwards (of PGN fame). From his ICC  
description:


Symbolic is a C++/Lisp chessplaying program written by S. J.  
Edwards. Symbolic's C++ source is fully ANSI/POSIX compliant and  
portable. Symbolic includes a ChessLisp interpreter for running its  
Lisp code. Neither source nor object code is publically available.  
One day, all interesting chess programs will be written in Lisp.  
Bit twiddling is not a pathway to Artificial Intelligence.


More information on Symbolic can be found in the Computer Chess  
Club archives, where Steven made regular progress reports.


Ian


His most recent progress reports are on his blog:

  http://chessnotation.livejournal.com/

Also, this isn't strictly Common Lisp. He uses his own dialect called  
"Chess Lisp", which contains optimized domain primitives such as  
bitboard operations.


Ian

___
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

[Ian Osgood]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1


On Nov 22, 2007, at 1:17 PM, 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.

--  
Until the next mail...,

Stefan.


Folks might be interested in the Common Lisp chess program "Symbolic"  
by Steven J. Edwards (of PGN fame). From his ICC description:


Symbolic is a C++/Lisp chessplaying program written by S. J. Edwards.  
Symbolic's C++ source is fully ANSI/POSIX compliant and portable.  
Symbolic includes a ChessLisp interpreter for running its Lisp code.  
Neither source nor object code is publically available. One day, all  
interesting chess programs will be written in Lisp. Bit twiddling is  
not a pathway to Artificial Intelligence.


More information on Symbolic can be found in the Computer Chess Club  
archives, where Steven made regular progress reports.


Ian
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.7 (Darwin)

iD8DBQFHSb77HDwFgzc3zyIRAtyAAKDtVYJwpyLbJ4BfxOmN2eb2JH9RFgCgwwW3
kE3+PFh4sYzcxvkkLRmD+4w=
=/y7n
-END 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 Nobis]

Don Dailey <[EMAIL PROTECTED]> writes:

> 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?

Oh, one additional comment: There are also implementations like ECL
(integration with plain C) and ABCL (integration with Java). Both may
be worth having a look (especially ECL), but I don't know very much
about them.

http://ecls.sourceforge.net/

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


pgp0cDxIiZJ8R.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 Nobis]

Don Dailey <[EMAIL PROTECTED]> writes:

> 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?

Huh, I don't have a really good overview, sorry. I only know, that the
performace characteristics of the different implementations are quite
different. So one is very good at integer performance, one at
floats. Something like that. The best overall performance? I'm not
sure. I would bet/test SBCL (free, open source), Corman (shareware?),
Lispworks (commercial), Allegro Common Lisp (commercial).

Both commercial compiler have free trials (unlimited use time, but
some restrictions in allocatable heap and the like) and very good
IDEs.

It also depends heavily on the platform you are targeting. For example
SBCL for windows is still very experimental (as far as I know) and
true multithreading support is (last time I had a look) only available
on Linux (I think the rest is port in progress). CMUCL and SBCL have
type inference engines build in and from them you get information
about possible performance penalties. Lispworks has one of
the best multi platform graphics library (and speed is good on any
platform, as far as I read about it). Corman is Windows only but has
native multithreading and (AFAIK) really good performance.

BTW: Some free Lisp IDEs:

* Emacs + SLIME (one of the best feature-wise)
* Eclipse + CUSP
* VisualCLisp (Windows only, based on the implementation CLisp)

And some pointers:

http://openmap.bbn.com/%7Ekanderso/performance/
http://www.cl-user.net/
http://eksl-www.cs.umass.edu/lisp-resources/index.html
http://www.lisperati.com/casting.html
http://www.lisperati.com/
http://www.gigamonkeys.com/book/

Now to Scheme: I'm not very proficient or experienced with scheme, so
it's all hearsay. AFAIK some of the Scheme compilers are very good and
performance wise Scheme may be the better choice. Some implementation
I heard quite good things about are Stalin (performance wise one of
the best, I think), PLT Scheme (AFAIK one of most mature
implementations), Bigloo. Maybe here a some schemers correcting my
uninformed hearsay.

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


pgpsfNA1lXSjT.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

[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

[Benjamin Teuber]

Maybe this link is a bit more interesting..
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=sbcl&lang2=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=all&lang=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

[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=all&lang=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

[Don Dailey]

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

[Don Dailey]

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

[Don Dailey]

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

[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

[Don Dailey]

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.
> 
>
> 
>
> ___
> 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

[steve uurtamo]

> 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?

just take a look at the generated assembly sometime and you'll
see things that you can make faster with little effort.

s.




  

Get easy, one-click access to your favorites. 
Make Yahoo! your homepage.
http://www.yahoo.com/r/hs 
___
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

[Benjamin Teuber]

Full agreement - I'll write more later when I find the time :)
___
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]

Jacques Basaldúa wrote:


Of course, what is "cool" is very subjective debate: Some people
find it cool to depend on runtimes that increase at mega/month rate, 
do what the API already does only much worse, gift the user with "the 
gray rectangle experience" even on a quad-core. After two seconds of 
gray rectangle they paint something that does not properly support 
clipboard operation, replaces the system's file dialogs for dialogs in 
which you have to manually type: *.sgf, *.SGF, *.Sgf, .. (to see all 
your .sgf files), that never remember last folders, etc. All this 
annoyance just because someone bought the "platform independence 
fallacy" from a company (Sun microsystems) that never cared a bit 
about compatibility. 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?"

Simple question, everybody I ever met answers no. Guess why.



Swing (Java's default GUI library) sucks. It's really really really bad. 
And does not reflect on the Java language at all. There are few decent 
GUI libraries for Java, and no really good ones. A go bot does not need 
an integrated GUI.


And my employer has paid for several programs written in Java (no GUI 
programs!), and in turn pay programmers to develop Java 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

[Jacques Basaldúa]

Raymond Wold wrote:


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.


Absolutely NOT. 

"Only" the typical, perhaps 99.9% of the programs, made of: transfers, 
conditionals, integer arithmetic and _non-parallelizable_ floating
point arithmetic are efficient when compiled in C (or Pascal which 
compiles to the same binary and creates the same compatible .obj as C). 
In these cases, writing in assembly is both less efficient (because the 
compiler finds optimizations the programmer won't find) and harder to 
maintain.



BUT

Programs with bitmaps, bit manipulation, masks, etc. Which are really 
useful in go, are (sometimes x4) more efficient written in assembly. The 
same was the case when Chen Zhixing wrote Handtalk in assembly. The same 
happens in any cryptographic, binary image compression/decompression, 
application today and forever etc. Compilers optimize "vulgar" programs, 
because that is what most programs are. Please, understand "vulgar"

as defined above, we all write lots of vulgar programs, it is not
an insult.


Programmers should view the code they are generating and _only_ that 
should tell them what is worth writing in assembly and what isn't. 
The best programming language is the language that lets you write 
assembly language hacks clean and easily using the high level symbols.



It is fine to use "cool feature" languages on the base that your 
priorities are different and you don't care about the binary, but
you shouldn't claim that you can have both "coolfeatureness" and 
efficiency, because that is simply not true.



Of course, what is "cool" is very subjective debate: Some people
find it cool to depend on runtimes that increase at mega/month 
rate, do what the API already does only much worse, gift the user 
with "the gray rectangle experience" even on a quad-core. After 
two seconds of gray rectangle they paint something that does not 
properly support clipboard operation, replaces the system's file 
dialogs for dialogs in which you have to manually type: *.sgf, 
*.SGF, *.Sgf, .. (to see all your .sgf files), that never remember 
last folders, etc. All this annoyance just because someone bought 
the "platform independence fallacy" from a company (Sun microsystems) 
that never cared a bit about compatibility. 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?"

Simple question, everybody I ever met answers no. Guess why.


Jacques.

___
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]

Don Dailey 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.
 

That something is technically possible does not mean that a human can do 
it. A compiler does not have to be perfect to beat a human, because 
humans aren't perfect either.



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.
 

No, it's getting impossible. For a high level language, an "ugly" way to 
optimize is a bug in the language. That optimization should be moved to 
the compiler, so that the "elegant" way of coding that solution end up 
with the optimized code when compiled.



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.
 

Well it's a humongous assumption. The skill benefit per cycle added will 
vary a _lot_ depending on the algorithm. As Dave Dyer said, standard 
alpha-beta will have such a fast-growing three that added cycles will 
add minimally to the skill. This, despite that alpha-beta can 
technically solve the game of go given enough resources. Monte Carlo 
methods will reach such a stage as well. The other added things will 
need to balance. Knowledge-based approaches for instance, often has a 
fixed search, and adding AB search or MC on top of it will add minimally.



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 th

Re: [computer-go] Drunken sailor on payday

[terry mcintyre]

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. 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.

 


  

Get easy, one-click access to your favorites. 
Make Yahoo! your homepage.
http://www.yahoo.com/r/hs ___
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

[Nick Apperson]

Actually, putting all the code in headers helps with function inlining more
than anything.  The virtual function stuff is very complicated because
usually code can be linked in at runtime that adds new functionality (i.e. a
new derived class).

Make no mistake, virtual functions are VERY expensive.  I'm just saying
there are instances where they are a faster than function pointers.  The
reverse is also true sometimes as well.  My point was only that adding new
features to a language that don't incur overhead when they aren't used can't
possibly make a language slower which is why C++ is not a slower language
than C.

As far as the assembler stuff.  I have written assembly code before.  There
are several reasons why compilers are better at it in my opinion:

1) They know the rules of the chip much better than people.
2) The rules change, all that is required is a recompile to optimize for the
new chip.  If you are using direct assembly and you optimized it well for
one chip, it won't be best for the next.
3) Correct optimizing at the machine code level can be calculated very
precisely.  There is much less of an art in organizing instructions and
selecting specific ones.  The reasons why one choice is better than another
are very easy to see, but are extremely computationally intensive.
Computers excel at these types of computations.

That said, there are times when I am programming and I know that my compiler
won't know "the fastest way" to implement something in machine code.  If
there was a good way to implement inline assembly into code, it would be
worth it.  Sadly, inline assembly breaks up the optimization of the code
around it enough that it usually isn't worth it.

Just my thoughts,
Nick

On Nov 22, 2007 9:41 PM, Heikki Levanto <[EMAIL PROTECTED]> wrote:

> On Wed, Nov 21, 2007 at 09:29:42PM +, Stuart A. Yeates wrote:
> > 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.
>
> Aha - that must be why LibEGO includes all source files from the mail
> file,
> instead of compiling each one separately.
>
> -H
>
> --
> 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/
>
___
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 Levanto]

On Wed, Nov 21, 2007 at 09:29:42PM +, Stuart A. Yeates wrote:
> 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.

Aha - that must be why LibEGO includes all source files from the mail file,
instead of compiling each one separately.

-H

-- 
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

[Don Dailey]

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

[Colin Kern]

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

[Don Dailey]

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

[Don Dailey]

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/
>
>

Re: [computer-go] Drunken sailor on payday

[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

[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

[Colin Kern]

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

[Colin Kern]

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

[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

[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

[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

[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

[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

[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

[Colin Kern]

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

[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

[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

[Don Dailey]

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

[Don Dailey]

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

[Don Dailey]

> (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

[Don Dailey]

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'r

Re: [computer-go] Drunken sailor on payday

[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

[Á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

[Don Dailey]

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]
> > 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 

Re: [computer-go] Drunken sailor on payday

[Nick Apperson]

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

[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

[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

[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

[Nick Apperson]

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

[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

[Nick Apperson]

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 compu

[computer-go] Drunken sailor on payday

[Don Dailey]

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.Getting a faster wheelchair doesn't stop you from being
crippled.The drunken sailor borrows money thinking that his next
paycheck will cover these debts but forgets he will have to borrow money
again.

When I develop my go program,  the vast majority of the development time
is spent by the computer, not me.I need to optimize the computers
time, not my time.   Whatever the program can do in 1 minute,  I would
like to see happen in 30 seconds. If I had a network of workstations
my productivity (as measured by program strength) would improve
significantly because I could try a lot more thing in the same amount of
time.But even if I had such a network,   I wouldn't willingly
cripple it by throwing away half the power.  

In fact, the whole concept is not to optimize what YOU do, it's to
optimize what the computer does.   If you are not stingy about the
performance (playing strength) right from the start you are already
starting from the wrong mentality. That's probably why the best
programs are in C or assembler - these programmers see performance as
part of the overall whole - not something that is "in their way."
They don't romanticize their language or the tools they use,  they are
focused on the problem and tend to make the most logical choices, not
the sexiest ones.  

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.


- Don





Raymond Wold wrote:
> Nick Apperson wrote:
>
>> But, to be fair, I totally agree that compiling python or ruby would
>> give
>> you noticable spe