Re: [computer-go] Drunken sailor on payday
-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
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
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/
CL implementation speed (Re: [computer-go] Drunken sailor on payday)
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=alllang=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 numbers in private
Re: [computer-go] Drunken sailor on payday
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 these
Re: [computer-go] Drunken sailor on payday
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
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
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
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
terry mcintyre wrote: A bird's-eye view of computer-Go programming: a large part of what a Go program does will probably be some sort of analysis of a deep tree of possible moves, involving the exploration of millions of possible positions. The guts of this should be as optimal as possible. A slower language such as Ruby or Perl is not a good fit for such efforts - but that's a strawman argument, of little practical relevance. Higher-level optimizations can provide far more remarkable speed gains than the choice of implementation language. This is obviously true and a well known principle, but when you compare languages for speed, the assumption is that you are using the same algorithms - anything else is just unfair. When you talk about Lukasz Lew and his very fast implementation, you will notice also that he chose C to write his library. I don't think this is a wild coincidence.It's a mentality and Lukasz has the right mentality. The kind of person who writes such a library is concerned about each single percent of execution speed because he knows they add up.He is not going to immediately start the project with a stupid decision. If he were willing to do that, chances are good that he would be willing to take other non-optimal choices. Of course I'm not saying that you can't do what Lukasz did using a different language. You could start with any constraints you want and then be disciplined from that point on - but you wouldn't end up with the same amazing results Lukasz did. He could have chosen Ruby, a far more expressive language.Perhaps it it would be a better choice for him because Ruby's amazing freedom of expression would unlock his mind and let him soar to new heights, but somehow Lukasz suffered along in C. - Don When Lukasz Lew wrote libego, I believe he recast the algorithms a few times in order to extract maximum performance, as he discovered more about how his chosen language ( C++ ) is compiled into assembler, and how that affects performance. Improvements to move ordering algorithms can enable reductions in the breadth of trees, which greatly reduce the size of the tree. Improvements in the quality of playouts result in vast improvements to the quality of the evaluations, which can lead to reductions in evaluation times. Several have noted that fast mersenne twister algorithms improve the speed and quality of random playouts. Ways to refactor, to incorporate higher-level knowledge, and otherwise increase the performance of our programs will be discovered as we learn more about the demands of computer Go. Better algorithms can improve program performance by factors of tens, hundreds, even thousands. Some future improvements will surely lead to increases of hundreds of elo points in ratings, given the same hardware and implementation language. Some of us will find ways to wring lots of elo points from multiple processors. Some of these improvements may be much more easily expressed in higher-level languages than in C. I cut my teeth on FORTRAN and C and assembler, having written hundreds of thousand lines in such languages, as well as piles of scripts in Perl, Ruby, Python, R, and other languages. I've chosen to study Lisp again ( which I last tinkered with in the 70s ) because I think I see interesting ways to take advantage of the unique properties of Lisp. I could write C equivalents to these capabilities - but I'd rather use a language where where my ideas are a more natural fit. There's a saying that any sufficiently sophisticated program will eventually include a buggy implementation of the Lisp eval loop. My efforts may use C libraries for some speed-intensive task; it may be all Lisp; too early to make that judgment. When humans explain how they play Go, their algorithms rarely require the investigation of millions of potential positions. A good program need not follow the same methods as a good human player, but it just might be that human play still offers a few very high-level optimizations. Fuel for thought. Be a better sports nut! Let your teams follow you with Yahoo Mobile. Try it now. http://us.rd.yahoo.com/evt=51731/*http://mobile.yahoo.com/sports;_ylt=At9_qDKvtAbMuh1G1SQtBI7ntAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
C is the one true language and must be indented with the one true brace style :-) - Don Stefan Nobis wrote: Benjamin Teuber [EMAIL PROTECTED] writes: Man, we really need a complete Common Lisp Go Framework which also has some fast low-level code to show all these C gurus its true power :) I think so, too. :) I don't want to say CL is the one and only language (for me surely it is), I only try to emphasize that C is not the only choice. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
Benjamin Teuber [EMAIL PROTECTED] writes: Man, we really need a complete Common Lisp Go Framework which also has some fast low-level code to show all these C gurus its true power :) I think so, too. :) I don't want to say CL is the one and only language (for me surely it is), I only try to emphasize that C is not the only choice. -- Until the next mail..., Stefan. pgpza4eWVxwnP.pgp Description: PGP signature ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
Stefan, What is the state of common lisp these days?What is fastest compiler for X86 and how does it compare to C code in performance? I was either going to experiment with Forth or lisp in the near future. I will get around to both eventually. - Don Stefan Nobis wrote: Benjamin Teuber [EMAIL PROTECTED] writes: Man, we really need a complete Common Lisp Go Framework which also has some fast low-level code to show all these C gurus its true power :) I think so, too. :) I don't want to say CL is the one and only language (for me surely it is), I only try to emphasize that C is not the only choice. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
I'm also curious about scheme compilers and the quality of code they generate. Does anyone have the dirt on these? - Don Stefan Nobis wrote: Benjamin Teuber [EMAIL PROTECTED] writes: Man, we really need a complete Common Lisp Go Framework which also has some fast low-level code to show all these C gurus its true power :) I think so, too. :) I don't want to say CL is the one and only language (for me surely it is), I only try to emphasize that C is not the only choice. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
AFAIK, CMUCL is the fastest free lisp available. But I would rather stick with its offspring, SBCL, which might be a bit slower, but it is being worked on actively, it is quite portable (http://sbcl.sourceforge.net/platform-table.html) and it supports native threads (CMUCL just has green threads). Of course it's not easy to compare speed of different languages, but e.g. http://shootout.alioth.debian.org/gp4/benchmark.php?test=alllang=all might give you an idea (oh shame, Java seems faster there). Cheers, Ben On Nov 22, 2007 10:54 PM, Don Dailey [EMAIL PROTECTED] wrote: Stefan, What is the state of common lisp these days?What is fastest compiler for X86 and how does it compare to C code in performance? I was either going to experiment with Forth or lisp in the near future. I will get around to both eventually. - Don Stefan Nobis wrote: Benjamin Teuber [EMAIL PROTECTED] writes: Man, we really need a complete Common Lisp Go Framework which also has some fast low-level code to show all these C gurus its true power :) I think so, too. :) I don't want to say CL is the one and only language (for me surely it is), I only try to emphasize that C is not the only choice. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
Maybe this link is a bit more interesting.. http://shootout.alioth.debian.org/gp4/benchmark.php?test=alllang=sbcllang2=gcc On Nov 23, 2007 12:30 AM, Benjamin Teuber [EMAIL PROTECTED] wrote: Of course it's not easy to compare speed of different languages, but e.g. http://shootout.alioth.debian.org/gp4/benchmark.php?test=alllang=all might give you an idea (oh shame, Java seems faster there). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
On Nov 22, 2007 12:13 PM, Jacques Basaldúa [EMAIL PROTECTED] wrote: I am still waiting to meet the first person who answers affirmatively to the question: Have you ever paid for a program written in Java? *raises hand* You need wait no longer ^.^ - and that was back in the days when Swing sucked. It's much better these days. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
Thanks for a great read there first of all. But... and this is something I see time and again and I must admit I don't really understand. What makes C faster than C++? I feel like C++ is all about you don't pay for what you don't use. Furthermore, I feel that C++ has at least one feature that in a one certain special case will result in faster code. While I generally would say avoid indirect calls where performance is critical (for obvious reasons) thereare certain times when it is faster than climbing through tons of logic. For these cases, if one indirect branch is reasonably likely the optimization most recent x86 chips take with static branch prediction is to assume the [indirect] branch is not taken which might seem wierd but makes sense since the chip can't easily guess this information statically. Good compilers will usually write the most commonly jumped to location after the indirect uncomditional jump instruction s JMP [EBX] JMP default_function is output. Unfortunately, C doesnt' have a way to specify this base case. Trying to code this yourself won't really work either because a C compiler is likely to notice that the branch is unconditional and remove you branch that occurs after anyway Which would be if you were using the low level jumping routines anyhow. There are a couple other features as well. So my question really is, how do you add features to a language (some of which give you opportunities to optimize things you wouldn't be able to) and come out slower? I'm assuming that if you are using C++ you know how to use discretion in feature use ofcourse. I also believe there may genuinely be a reason I don't understand since I see many good programmers picking C over C++. Thanks in advance for any explanation you have. - Nick On Nov 22, 2007 11:07 AM, Don Dailey [EMAIL PROTECTED] wrote: I think we are missing the point of programmer productivity with higher level languages. High level languages MIGHT improve the speed at which you write code, but usually that is a minor concern. In computer GO, what you want is the pathway that gives you the best programs in the least amount of effort. For that, C currently appears to be the best choice.This in not just my opinion, there is empirical evidence to support this claim. Take a close look at the very best GO programs in the world, and I doubt you will see Ruby and Python programs. I doubt you will see Java programs. All of these programming languages, as wonderful as they may be and most of which claim dramatically increased productivity, simply are not producing. Most arguments for using these languages are nonsense.They focus on only one aspect of the total picture - how fast you can write bug-free code.Some languages are clearly better than others at that but the biggest factor by far is the programmer herself. Many say, it's just not worth a few percent speedup to code in a low level language. I hope you realize that few percent is probably in the best case around 50%. We could argue about the exact number, but the fact is that you take a substantial hit programming in Java (for instance) and that is not even a high level language. Computer Go is still in the dark ages but is gradually emerging from it - it's starting to be appreciated that 50% represents a significant strength improvement. That probably means it's low hanging fruit - in other words you are probably going to get the most improvement for your programming time developing and programming in C. And yet many will say, but I would rather spend my time improving the algorithm in a language that makes it easy to express my ideas. I might be throwing away 50%, but I will quickly make up the difference with my vastly improved ability to experiment and express my wonderful ideas. One might even argue that using a low level language like C is actually inhibiting their ability to forge ahead. My experience in computer chess is that the people who think this way, never catch up. I call this the drunken sailor approach. The metaphor is the drunken sailor who blows most of his paycheck the day he gets it. He does this, because it seems to him like a lot of money. When there is a lot of money in your pocket, it's easy to spend it frivolously and then tighten up when you are almost broke. Computers are fast. You don't mind taking the 2 to 1 hit (or whatever it is) for the extra luxury of programming in a high level language. However, this mentality doesn't stop here. If you are thinking this way, chances are that you take other shortcuts for the long term good. The problem is that you never stop taking the hit.You say, in 18 months computers will be 2X faster, so it doesn't matter. This is the stupidest thing I keep hearing. In 18 months you will have a faster computer, but your program will STILL be a crippled program that sucks.
Re: [computer-go] Drunken sailor on payday
On Thu, Nov 22, 2007 at 11:36:58AM +1800, Nick Apperson wrote: Thanks for a great read there first of all. But... and this is something I see time and again and I must admit I don't really understand. What makes C faster than C++? I feel like C++ is all about you don't pay for what you don't use. My personal stance is that the extra cruft and basically mysterious behaviour in some cases (I know many programmers and even some gcc developers, and only one or maybe two who can say that they completely understand identifier lookup mechanism in C++) is not worth the extra features you are getting. I believe C gives you all the constructs you really need and frequently the extra C++ constructs just reduce readability. But this is just question of taste and many people will like the extra C++ features and that's really ok, too. I think C++ is much like Perl. Many oh-so-cool features and constructs, but things can get out of hand real fast. ;-) (And I do like Perl. Including the cool features and constructs. But Perl and C are pretty much _the_ two languages I use and I never had too much motivation to mix the cool features with low level code as in C++.) Furthermore, I feel that C++ has at least one feature that in a one certain special case will result in faster code. While I generally would say avoid indirect calls where performance is critical (for obvious reasons) thereare certain times when it is faster than climbing through tons of logic. For these cases, if one indirect branch is reasonably likely the optimization most recent x86 chips take with static branch prediction is to assume the [indirect] branch is not taken which might seem wierd but makes sense since the chip can't easily guess this information statically. Good compilers will usually write the most commonly jumped to location after the indirect uncomditional jump instruction s JMP [EBX] JMP default_function is output. Unfortunately, C doesnt' have a way to specify this base case. Trying to code this yourself won't really work either because a C compiler is likely to notice that the branch is unconditional and remove you branch that occurs after anyway Which would be if you were using the low level jumping routines anyhow. There are a couple other features as well. This is indeed not standardized but C compilers tend to have their own extensions for this. Many codebases have likely(a) and unlikely(a) macros they use in conditions which are defined to expand to __builtin_expect(!!(a), 1) or 0 respectively in case the code is compiled by gcc. I'd expect MSVC to have some similar way to hint this. (gcc also supports -fprofile-generate and -fprofile-use, which is pretty cool too - gcc will re-optimize the binary based on profiling information gathered from a test run of the program. It can be quite a non-trivial boost.) However, I don't get how is this related to C vs C++? AFAIK C++ does not have an official way to hint the compiler about branching probability either? -- Petr Pasky Baudis We don't know who it was that discovered water, but we're pretty sure that it wasn't a fish. -- Marshall McLuhan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
right... well C++ does have this using virtual methods. I meant to add that part. C++ also has templates which while they theoretically don't add any performance. Practically speaking they add tons because you don't have to split your optimization time between 10 or more versions of the same function. I don't buy the stuff people throw down about programmer productiveity being more important than raw speed, but if you are starting at the same speed and it is easier to optimize you will likely get a faster program. And I totally agree with you that things can get out of hand fast. I'd say C++ is probably one of the hardest languages out there. Templates can make code blazingly fast in the general case, but writing them to work well can be extremely challenging. Multiple inheritence is somewhat easier to me, but it can definately trip people up really quickly if they design their code poorly. There is a saying I think... but yeah C++ is not made for people that aren't really good programmers. No training wheels. On Nov 22, 2007 11:51 AM, Petr Baudis [EMAIL PROTECTED] wrote: On Thu, Nov 22, 2007 at 11:36:58AM +1800, Nick Apperson wrote: Thanks for a great read there first of all. But... and this is something I see time and again and I must admit I don't really understand. What makes C faster than C++? I feel like C++ is all about you don't pay for what you don't use. My personal stance is that the extra cruft and basically mysterious behaviour in some cases (I know many programmers and even some gcc developers, and only one or maybe two who can say that they completely understand identifier lookup mechanism in C++) is not worth the extra features you are getting. I believe C gives you all the constructs you really need and frequently the extra C++ constructs just reduce readability. But this is just question of taste and many people will like the extra C++ features and that's really ok, too. I think C++ is much like Perl. Many oh-so-cool features and constructs, but things can get out of hand real fast. ;-) (And I do like Perl. Including the cool features and constructs. But Perl and C are pretty much _the_ two languages I use and I never had too much motivation to mix the cool features with low level code as in C++.) Furthermore, I feel that C++ has at least one feature that in a one certain special case will result in faster code. While I generally would say avoid indirect calls where performance is critical (for obvious reasons) thereare certain times when it is faster than climbing through tons of logic. For these cases, if one indirect branch is reasonably likely the optimization most recent x86 chips take with static branch prediction is to assume the [indirect] branch is not taken which might seem wierd but makes sense since the chip can't easily guess this information statically. Good compilers will usually write the most commonly jumped to location after the indirect uncomditional jump instruction s JMP [EBX] JMP default_function is output. Unfortunately, C doesnt' have a way to specify this base case. Trying to code this yourself won't really work either because a C compiler is likely to notice that the branch is unconditional and remove you branch that occurs after anyway Which would be if you were using the low level jumping routines anyhow. There are a couple other features as well. This is indeed not standardized but C compilers tend to have their own extensions for this. Many codebases have likely(a) and unlikely(a) macros they use in conditions which are defined to expand to __builtin_expect(!!(a), 1) or 0 respectively in case the code is compiled by gcc. I'd expect MSVC to have some similar way to hint this. (gcc also supports -fprofile-generate and -fprofile-use, which is pretty cool too - gcc will re-optimize the binary based on profiling information gathered from a test run of the program. It can be quite a non-trivial boost.) However, I don't get how is this related to C vs C++? AFAIK C++ does not have an official way to hint the compiler about branching probability either? -- Petr Pasky Baudis We don't know who it was that discovered water, but we're pretty sure that it wasn't a fish. -- Marshall McLuhan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
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
On Nov 21, 2007 1:41 PM, Don Dailey [EMAIL PROTECTED] wrote: (gcc also supports -fprofile-generate and -fprofile-use, which is pretty cool too - gcc will re-optimize the binary based on profiling information gathered from a test run of the program. It can be quite a non-trivial boost.) This puts even more distance between C/C++ and other languages. I have not yet experimented with this, but I look forward to it. It delays the day I will be able to code in D unfortunately! Some chess programmers have told me that this feature works much better in Visual C++ than in gcc. It's too bad I am not willing to program in Windows to verify it. Oh, and I completely agree with everything Don has said. It has taken me years to learn how to use C++ efficiently, but I think these days I write code that is as fast as C, it's organized better... and the STL containers and the std::string class are really nice to have. Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
Hi Nick, When I say C, I really mean C or C++. C is basically a useful subset of C++. C++ may be closer to the ideal HP language than C.To me, the ideal language will let you seamlessly step down to high performance coding in something just as efficient as C but be able to use much higher level language features without getting in the way of performance - which after all is what computers are all about.Even though I personally don't like c++ at least it doesn't invalidate this principle of being higher level without compromising the low level performance.The idea is that high level features should be optional. An interesting language is D. It's basically C with the option to use high level constructs and it's quite nice. It has everything needed to be a C/C++ replacement. It was designed specifically to be easy to optimize (for compilers) and in principle it can be faster than even C according to the website hype. I tend to believe this is true because it's really C code with stuff removed or added to improve (the opportunities for) compiler optimizations. However in practice, it's still noticeably slower (in my tests of GO code, about 1.4 X slower. ) I'm not willing to give up very much performance for things I use C for, so I can't yet use D. But I'm keeping a close eye on it. - Don Nick Apperson wrote: Thanks for a great read there first of all. But... and this is something I see time and again and I must admit I don't really understand. What makes C faster than C++? I feel like C++ is all about you don't pay for what you don't use. Furthermore, I feel that C++ has at least one feature that in a one certain special case will result in faster code. While I generally would say avoid indirect calls where performance is critical (for obvious reasons) thereare certain times when it is faster than climbing through tons of logic. For these cases, if one indirect branch is reasonably likely the optimization most recent x86 chips take with static branch prediction is to assume the [indirect] branch is not taken which might seem wierd but makes sense since the chip can't easily guess this information statically. Good compilers will usually write the most commonly jumped to location after the indirect uncomditional jump instruction s JMP [EBX] JMP default_function is output. Unfortunately, C doesnt' have a way to specify this base case. Trying to code this yourself won't really work either because a C compiler is likely to notice that the branch is unconditional and remove you branch that occurs after anyway Which would be if you were using the low level jumping routines anyhow. There are a couple other features as well. So my question really is, how do you add features to a language (some of which give you opportunities to optimize things you wouldn't be able to) and come out slower? I'm assuming that if you are using C++ you know how to use discretion in feature use ofcourse. I also believe there may genuinely be a reason I don't understand since I see many good programmers picking C over C++. Thanks in advance for any explanation you have. - Nick On Nov 22, 2007 11:07 AM, Don Dailey [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: I think we are missing the point of programmer productivity with higher level languages. High level languages MIGHT improve the speed at which you write code, but usually that is a minor concern. In computer GO, what you want is the pathway that gives you the best programs in the least amount of effort. For that, C currently appears to be the best choice.This in not just my opinion, there is empirical evidence to support this claim. Take a close look at the very best GO programs in the world, and I doubt you will see Ruby and Python programs. I doubt you will see Java programs. All of these programming languages, as wonderful as they may be and most of which claim dramatically increased productivity, simply are not producing. Most arguments for using these languages are nonsense.They focus on only one aspect of the total picture - how fast you can write bug-free code.Some languages are clearly better than others at that but the biggest factor by far is the programmer herself. Many say, it's just not worth a few percent speedup to code in a low level language. I hope you realize that few percent is probably in the best case around 50%. We could argue about the exact number, but the fact is that you take a substantial hit programming in Java (for instance) and that is not even a high level language. Computer Go is still in the dark ages but is gradually emerging from it - it's starting to be appreciated that 50% represents a significant strength improvement.
Re: [computer-go] Drunken sailor on payday
sure thing: -- struct foo { // some stuff gets executed virtual void do_something(somestruct s); // base case executed by default }; struct foo_foo : foo { // some stuff gets executed }; struct foo_bar : foo { // some stuff gets executed virtual void do_something(somestruct s); // special case }; So then if we have say: foo *f; somestruct s; // ... some code that sets f to something and changes s f-do_something(s); So now when the compiler is optimizing the code, it will optimize for the base case of foo::do_something by default unless it has information that is even better. If our code instead read with f as a function pointer, the compiler (assuming it can't determine the value) won't have a base case. On Nov 22, 2007 12:18 PM, Petr Baudis [EMAIL PROTECTED] wrote: On Thu, Nov 22, 2007 at 12:04:53PM +1800, Nick Apperson wrote: right... well C++ does have this using virtual methods. I meant to add that part. I'm sorry, I still don't get this - what do virtual methods have to do with branch prediction? Can you elaborate, please? -- Petr Pasky Baudis We don't know who it was that discovered water, but we're pretty sure that it wasn't a fish. -- Marshall McLuhan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
Hi Raymond, The point I'm making is that you must focus on what's relevant.If you are trying to win the title of world championship go program, then maintainability of code is LOW on the list of what is important. In a corporate environment it moves close to the TOP of the list of what is important. Experience in a language is a factor, but nobody refutes that properly coded C is fastest (next to properly code assembly) and if performance is your goal, then anything else accepts some compromise. That compromise may work well for a particular individual and may even produce a stronger program for them, but it's still a handicap. For example, Mogo probably could be coded in Java and still (probably) be the best 9x9 program. If so, then it would be the best despite the fact that it was coded in Java, not because of it. They would have had to overcome a good bit of performance handicap. There are some tennis players that could beat me with one hand tied behind their back, but that doesn't mean it's the way to go. They would have to beat me despite the fact that one hand was tied behind their back.A player close to my level would not have a chance with this handicap because it is in fact a handicap, no matter how you cast it. My feeling is that the engineer who starts his GO programming project in a high level language is not going to be able to compete with the C programmer, even if he is given the extra hardware to equalize.I say this because he has already proven (in some sense) that he can't make good decisions and you can be reasonably sure that he will make more bad decisions.For example you can be relatively sure that he will not favor doing things fast if he has to write ugly code - after all he has already made choices that indicates he values high level thinking and nice code over low level efficiency.In fact it would be rather silly if he used a high level language, but then resorted to performance tricks. I don't say this to be ugly or to be critical of java or other programmers. These languages are fine choices as long as you don't believe you are writing a cutting edge high performance go program. I am rather curious, which CGOS program that is NOT in C/C++ or assembler is highest rated? Despite all the hype about expressibility and code maintainability I would guess that the best programs are in C, then perhaps Java (since it's relatively fast) and that the weakest are in the highly productive dynamic programming languages that are slow. By the way, I'm a huge advocate of Ruby, one of the slowest languages! I love this language as well as Lua and others. However, common sense must prevail.It's just insane to reach for Ruby to produce a high performance Go program. And to a lesser degree Java. - Don Raymond Wold wrote: Don Dailey wrote: For that, C currently appears to be the best choice.This in not just my opinion, there is empirical evidence to support this claim. The problem with empirical evidence is that you don't get the very much needed all else being equal. The people that code in C (and get great speeds for the algorithms where speed means a skill increase) are people that know C best, that have years of experience in it, and also, people that have a different attitude towards /how/ to solve problems, /what/ algorithms to write. I suspect that Java coders, and especially Haskell, Lisp, etc. coders, are people with significant less experience in those languages; partially because you need a lot less knowledge about programming to get started and get anywhere, but also because these languages have something of the hype about them*, and might be chosen as the language merely for being the latest language, or the highest-level one, learned so far. And you think differently when coding in a higher level language. It might well be that the slightly different mindset of low-level programmers is more suited for go. It might be that we /need/ a domain specific language for go. But none of this means that the /speed of execution/ is the crucial factor, or even an important one. Yes, perhaps the same algorithm in Haskell is ten times as slow as one in assembler. But does that mean that if you give a Haskell coder ten times as powerful hardware, that he'll be able to compete with the C coder? I'm not so sure. The maintainability aspect is not to be laughed at either. Once you get above a certain size in complexity of the program, having it in C from the start will mean a much greater inertia against expanding and experimenting with what you have. And I suspect go programms will have to go above this to beat the current set of algorithms. As seducing as the idea that there's an elegant solution is, I don't think it's realistic. And then we'll need the added clarity of high-level programming. *) Without that meaning they're worse languages for being hyped, or being
Re: [computer-go] Drunken sailor on payday
(gcc also supports -fprofile-generate and -fprofile-use, which is pretty cool too - gcc will re-optimize the binary based on profiling information gathered from a test run of the program. It can be quite a non-trivial boost.) This puts even more distance between C/C++ and other languages. I have not yet experimented with this, but I look forward to it. It delays the day I will be able to code in D unfortunately! - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
One thing that I haven't check into is whether the GDC D compiler has these same options for profiling code and using the profile to further improve the code. If it does, then the performance gap between C and D may not increase. - Don Don Dailey wrote: (gcc also supports -fprofile-generate and -fprofile-use, which is pretty cool too - gcc will re-optimize the binary based on profiling information gathered from a test run of the program. It can be quite a non-trivial boost.) This puts even more distance between C/C++ and other languages. I have not yet experimented with this, but I look forward to it. It delays the day I will be able to code in D unfortunately! - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
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
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
On Nov 21, 2007 1:18 PM, Petr Baudis [EMAIL PROTECTED] wrote: On Thu, Nov 22, 2007 at 12:04:53PM +1800, Nick Apperson wrote: right... well C++ does have this using virtual methods. I meant to add that part. I'm sorry, I still don't get this - what do virtual methods have to do with branch prediction? Can you elaborate, please? I don't know about branch predictions, but virtual functions have additional overhead with figuring out which function to call. They will also prevent function inlining. Both effects can yield a slow down in your code. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
Heikki, Yes, I like your approach of a library and using high level language. One must be careful that it doesn't get in the way. Sometimes, the low level library imposes some constraints so that you still don't quite get the best of both worlds. For example it would be great if you could use inline-perl to do something like this, but it's not easy to use a C data structure with perl, or visa versa. So you might end up with a program that is pretty much a C program with just a few routines (like GTP) and the user interface written in perl or python or whatever high level language you use. They key is that you still want almost all the time (to get ultimate performance) spent in the C library. If 90% of the time is spent in the library, then 99% of the executed code must be in C! That' s because a routine that might be insignificant written in C, might not be so insignificant written in python. Here is an example. Let's say you have a fast C library that can make 80,000 play-outs per second. The python script could call the routine that makes the playouts, but what is overhead from those 80,000 calls? It's not just the calls, but the results must be converted to a python representation if the python program works with it. But if this is not much overhead, do you put the play-outs in the python code too? Perhaps you code the low level routines in C but a Python routine is driving the process of a single random play-out? My guess, is that most of the guts of the program still have to be written in C and that the Python wrapper won't do very much interesting stuff. It's probably fine to do it this way and may save you some time - but you are not really getting much of the benefit of the high level program - you are not doing anything really important in the Python code. Nevertheless, even if you only had a few low level C routines and let Python do a lot of work, you would having something MUCH faster than pure Python and could do most of your experimentation in Python once you had this library.Of course you wouldn't really have a high performance program. It's hard to say just how far you could take and still be able to benefit significantly from using Python or some other high level language. - Don Heikki Levanto wrote: On Wed, Nov 21, 2007 at 12:07:03PM -0500, Don Dailey wrote: My advice when this question comes up (which language for go programmer) is to first ask, what do you hope to achieve?If you want to build a high performance go program, anything other than C or assembler is like tying your hand behind your back. If you do this only as a hobby and have no aspirations (just for fun and pleasure) then by all means, you will be much happier in a high level language. Interesting approach. I like C myself, so even as an amateur just dabbling in the field, I have used it, and will do so again. But of course teh choice is never so black and white. If I had unlimited amount of time (or some student labour available ;-), I would make a good C library available from higher-level languages, so that the parts that matter could be fat and efficient C, and those that don't matter, or where lots of experimentation is useful, could be done in (say) python. There just isn't much point in optimizing much out of the 'list_commands' routine of the gtp interpreter, it is used at msot once per game, and communicating teh result over a network is going to be much slower than what ever is done to find the commands... - Heikki who does not plan to do much more in the language war... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
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
On Wed, Nov 21, 2007 at 09:16:48PM +0100, Raymond Wold wrote: On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote: Experience in a language is a factor, but nobody refutes that properly coded C is fastest (next to properly code assembly) and if performance is your goal, then anything else accepts some compromise. That compromise may work well for a particular individual and may even produce a stronger program for them, but it's still a handicap. Do you have anything to back this up? I was under the impression that most decent assembly programmers agreed that they can't compete with the best C compilers. Assembly is for when you *need* to be in touch with the very lowest level, which in most cases you don't, because lots and lots of other assembly programmers have been there before you and distilled their knowledge into really really smart compilers that know more, and can try out more, than you ever could in a lifetime. I guess that you could say the original statement holds but humans generally can't properly code assembly anymore. ;-) This assumes that to be cutting edge, cycles matter. If your algorithms are such that doubling the execution time available means a 0.01% increase in wins (this is *obviously* not true for a Monte Carlo-heavy program, but might be for others), then giving up clarity is not worth it. And if that 0.01% increase means you'll spend weeks extra programming, because you have to recode something from scratch instead of using a simple refactoring, the high-level language IS a fine choice. I think that's somewhat contrived as well. I don't have that good idea about all the populat computer go algorithsm, do you have example of reasonably performing algorithm with these properties? -- Petr Pasky Baudis We don't know who it was that discovered water, but we're pretty sure that it wasn't a fish. -- Marshall McLuhan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
On Nov 21, 2007 3:36 PM, Petr Baudis [EMAIL PROTECTED] wrote: On Wed, Nov 21, 2007 at 09:16:48PM +0100, Raymond Wold wrote: On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote: Experience in a language is a factor, but nobody refutes that properly coded C is fastest (next to properly code assembly) and if performance is your goal, then anything else accepts some compromise. That compromise may work well for a particular individual and may even produce a stronger program for them, but it's still a handicap. Do you have anything to back this up? I was under the impression that most decent assembly programmers agreed that they can't compete with the best C compilers. Assembly is for when you *need* to be in touch with the very lowest level, which in most cases you don't, because lots and lots of other assembly programmers have been there before you and distilled their knowledge into really really smart compilers that know more, and can try out more, than you ever could in a lifetime. I guess that you could say the original statement holds but humans generally can't properly code assembly anymore. ;-) What's to say that a computer program can't code assembly better than any human possibly could? There are a ton of tasks that computers do thousands of times better than humans. I think it makes perfect sense that code written in C can execute faster than human-written assembly code. Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
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
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
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
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
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
What's to say that a computer program can't code assembly better than any human possibly could? There are a ton of tasks that computers do thousands of times better than humans. I think it makes perfect sense that code written in C can execute faster than human-written assembly code. No compiler will ever do *all* of the optimizations that are possible, because most optimizations are NP-complete or even much worse. For example the equivalance of boolean expressions is NP-complete. Some potential optimizations (such as replacement of data structures) may not even computable. This is why humans must choose the algorithms and data strucures. Compilers are very good at *small, local optimizations*, such as putting variables in registers, common sub-expression elimination, and choosing the fastest instructions. Compilers almost always outperform humans on these tasks because compilers consistently try every trick they know, and they don't get tired. Even way back in the 1970s, studies showed that optimizers consistently outperformed humans on these tasks, and back then, many people still practiced doing assembler regularly. Today, performance combines programmer and compiler intelligence. Neither can replace the other. Please use both. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
On Nov 21, 2007 5:37 PM, Ben Lambrechts [EMAIL PROTECTED] wrote: Some chess programmers have told me that this feature works much better in Visual C++ than in gcc. It's too bad I am not willing to program in Windows to verify it. I have compiled GNU Go with both GCC and Visual C++ 2008. The binary of Visual C++ was almost half the size of the GCC one, but 3 times slower. I think I choose for the speed instead of the size. Ben I'm not sure about the Visual C++ compiler, but with GCC there are a number of options for optimization, some sacrificing size for speed, and others vice versa. It could just be a matter of compiler options. Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
On Nov 21, 2007 6:12 PM, [EMAIL PROTECTED] wrote: What's to say that a computer program can't code assembly better than any human possibly could? There are a ton of tasks that computers do thousands of times better than humans. I think it makes perfect sense that code written in C can execute faster than human-written assembly code. No compiler will ever do *all* of the optimizations that are possible, because most optimizations are NP-complete or even much worse. For example the equivalance of boolean expressions is NP-complete. Some potential optimizations (such as replacement of data structures) may not even computable. This is why humans must choose the algorithms and data strucures. Compilers are very good at *small, local optimizations*, such as putting variables in registers, common sub-expression elimination, and choosing the fastest instructions. Compilers almost always outperform humans on these tasks because compilers consistently try every trick they know, and they don't get tired. Even way back in the 1970s, studies showed that optimizers consistently outperformed humans on these tasks, and back then, many people still practiced doing assembler regularly. Today, performance combines programmer and compiler intelligence. Neither can replace the other. Please use both. Michael Wing So this seems to support the idea that C code is potentially faster than hand-coded assembly, because the more complicated optimizations can be done by the programmer in C while the optimizations better suited to a computer are done by the compiler. Although it would also be possible to hand-code in assembly and then run a program to optimize it, but then it seems like there is no advantage over C. As far as I can tell, the optimizations that a compiler can't do are higher-level optimizations that can be done in C and wouldn't require the programmer to write assembly, or am I wrong about this? Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
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
On Nov 21, 2007, at 12:16 PM, Raymond Wold wrote: This assumes that to be cutting edge, cycles matter. If your algorithms are such that doubling the execution time available means a 0.01% increase in wins (this is *obviously* not true for a Monte Carlo-heavy program, but might be for others), then giving up clarity is not worth it. And if that 0.01% increase means you'll spend weeks extra programming, because you have to recode something from scratch instead of using a simple refactoring, the high-level language IS a fine choice. Do you seriously believe that any good Go- (or any other complex game) programm can be written that could not be improved by faster hardware? Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
Raymond Wold wrote: On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote: Experience in a language is a factor, but nobody refutes that properly coded C is fastest (next to properly code assembly) and if performance is your goal, then anything else accepts some compromise. That compromise may work well for a particular individual and may even produce a stronger program for them, but it's still a handicap. Do you have anything to back this up? I was under the impression that most decent assembly programmers agreed that they can't compete with the best C compilers. Assembly is for when you *need* to be in touch with the very lowest level, which in most cases you don't, because lots and lots of other assembly programmers have been there before you and distilled their knowledge into really really smart compilers that know more, and can try out more, than you ever could in a lifetime. I know that there are assembler programmers who specialize in the skills requires to beat C code.However, there is no need to back this up. You can express any C program in assembler and better C compilers do this better and they continue to improve. Until C compilers are perfect, then it will always be possible to express a (non-trivial) program in more efficient assembler code. For example, Mogo probably could be coded in Java and still (probably) be the best 9x9 program. If so, then it would be the best despite the fact that it was coded in Java, not because of it. They would have had to overcome a good bit of performance handicap. Because its algorithms are well suited for more cycles. My feeling is that the engineer who starts his GO programming project in a high level language is not going to be able to compete with the C programmer, even if he is given the extra hardware to equalize.I say this because he has already proven (in some sense) that he can't make good decisions and you can be reasonably sure that he will make more bad decisions.For example you can be relatively sure that he will not favor doing things fast if he has to write ugly code - after all he has already made choices that indicates he values high level thinking and nice code over low level efficiency.In fact it would be rather silly if he used a high level language, but then resorted to performance tricks. See, the thing about (most) high-level languages is that the ugly optimization is a myth. In a high-level language, the optimizers will work best with *correct* code, coded as the language was intended, and programmers who try to optimize invariably /slow down/ their code. Perhaps in the general case. Perhaps most humans will fail. But skillful humans can find ways to optimize the code by doing unnatural or ugly things - it's just getting more difficult. I don't say this to be ugly or to be critical of java or other programmers. These languages are fine choices as long as you don't believe you are writing a cutting edge high performance go program. This assumes that to be cutting edge, cycles matter. Of course it does - that is my assumption and I stated it. If your algorithms are such that doubling the execution time available means a 0.01% increase in wins (this is *obviously* not true for a Monte Carlo-heavy program, but might be for others), then giving up clarity is not worth it. And if that 0.01% increase means you'll spend weeks extra programming, because you have to recode something from scratch instead of using a simple refactoring, the high-level language IS a fine choice. This is my opinion but if your program is such that it doesn't benefit from increased cycles, then your code is written wrong - certainly you have hit a dead end by definition. I am rather curious, which CGOS program that is NOT in C/C++ or assembler is highest rated? Despite all the hype about expressibility and code maintainability I would guess that the best programs are in C, then perhaps Java (since it's relatively fast) and that the weakest are in the highly productive dynamic programming languages that are slow. This is because, at the current point in time, Monte Carlo programs dominate. *This* *can* *change*. It changes practically every day.None of these programs are the same and some don't even use UCT now. Even the non-scalable programs are scalable now - they are just hard coded for a given platform. The programmer has to make some changes and recompile them to work right on the next faster machine. They usually tweak and optimize at the same time, but that in itself is not scalability. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org
Re: [computer-go] Drunken sailor on payday
Colin Kern wrote: On Nov 21, 2007 3:36 PM, Petr Baudis [EMAIL PROTECTED] wrote: On Wed, Nov 21, 2007 at 09:16:48PM +0100, Raymond Wold wrote: On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote: Experience in a language is a factor, but nobody refutes that properly coded C is fastest (next to properly code assembly) and if performance is your goal, then anything else accepts some compromise. That compromise may work well for a particular individual and may even produce a stronger program for them, but it's still a handicap. Do you have anything to back this up? I was under the impression that most decent assembly programmers agreed that they can't compete with the best C compilers. Assembly is for when you *need* to be in touch with the very lowest level, which in most cases you don't, because lots and lots of other assembly programmers have been there before you and distilled their knowledge into really really smart compilers that know more, and can try out more, than you ever could in a lifetime. I guess that you could say the original statement holds but humans generally can't properly code assembly anymore. ;-) What's to say that a computer program can't code assembly better than any human possibly could? There are a ton of tasks that computers do thousands of times better than humans. I think it makes perfect sense that code written in C can execute faster than human-written assembly code. I hope you are right. I don't want to code in assembly. But you are probably wrong because ansi C is platform portable and there are some things that might be done in assembler that cannot be naturally expressed in C.One example of this is an operation to find the leftmost or rightmost bit in a 32 or 64 bit word. Many processors have instructions for this, but there is no such instruction in C. Of course not all processors implement this efficiently, but we can assume that there might be some that do, or perhaps other instructions like this that ARE implemented efficiently with a single instruction in assembly, but require many in C. Of course you could argue that a super-clever C compiler may someday recognize what is going on and substitute the appropriate processor instruction for the C function. But that would take a truly amazing compiler that could do this in the general case. When that day comes, compilers may decide to completely reorganize your code, choosing more efficient algorithms! - Don Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
On Nov 21, 2007 7:24 PM, Don Dailey [EMAIL PROTECTED] wrote: Raymond Wold wrote: On Wed, 2007-11-21 at 14:11 -0500, Don Dailey wrote: Experience in a language is a factor, but nobody refutes that properly coded C is fastest (next to properly code assembly) and if performance is your goal, then anything else accepts some compromise. That compromise may work well for a particular individual and may even produce a stronger program for them, but it's still a handicap. Do you have anything to back this up? I was under the impression that most decent assembly programmers agreed that they can't compete with the best C compilers. Assembly is for when you *need* to be in touch with the very lowest level, which in most cases you don't, because lots and lots of other assembly programmers have been there before you and distilled their knowledge into really really smart compilers that know more, and can try out more, than you ever could in a lifetime. I know that there are assembler programmers who specialize in the skills requires to beat C code.However, there is no need to back this up. You can express any C program in assembler and better C compilers do this better and they continue to improve. Until C compilers are perfect, then it will always be possible to express a (non-trivial) program in more efficient assembler code. But the point is that humans are also not perfect, and so they too can't automatically write the optimal assembly code. The question is whether the massively superior processing power of a computer gives it an advantage over the creative ability of a human. Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
My mind is open on this. I'm not a lisp programmer but I have considered learning it at some point and I'm sure I will. - Don Benjamin Teuber wrote: On Nov 21, 2007 10:22 PM, Stefan Nobis [EMAIL PROTECTED] wrote: Hmmm... you are just describing Common Lisp. :) Man, we really need a complete Common Lisp Go Framework which also has some fast low-level code to show all these C gurus its true power :) Maybe we should really think of a project - doesn't have to be the one I started (now I find most of it ugly..) Who'd be in? Cheers, Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
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
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/