Re: [computer-go] Effective Go Library v0.101
On 2/17/07, Luke Gustafson [EMAIL PROTECTED] wrote: Lukasz, any chance you can access the assembly to see how the compiler optimized it differently? That is a strange result. All that I could think of is, if you have several places where the function is called, and the compiler used to be inlining it, it may be faster (for cache reasons) to make it a function call instead of inlining. Inlining is not always fastest! There was only one place and no inlineing :) So it was pure difference static/dynamic call. And I did immediately look at the asm, the difference was very small. exactly static / dynamic call :) So I don't get it. But I don't won't to get it. Is to much for me. I.e. too absorbing :) Regarding function pointers--from Agner Fog's guide: 3.7 Indirect jumps (all processors except PM and Core2) Indirect jumps, indirect calls, and returns may go to a different address each time. The prediction method for an indirect jump or indirect call is, in all processors except PM and Core2, simply to predict that it will go to the same target as last time it was executed. The first time an indirect jump or indirect call is seen, it is predicted to go to the immediately following instruction. (The Pentium M Core2 have more sophisticated indirect jump prediction) I tested on PM, so this may be an explanation. But anyway this is so small *detail* that I prefer to concentrate in different places. For instance I just implemented UCT and I want to publish it asap.:) Lukasz So, if a function pointer always points to the same function, all processors will predict the branch correctly! I am doubtful function objects would be much faster, except that they may be more likely to be inline-able. Also I disagree that well-designed code should cause function objects to be predicted at compile time--it seems to me that their purpose is for run-time polymorphism! I will just tell You about my experiences: - allmost all code of benchmark in Ego library is inlined (remove_stone is not) - function pointer are usually inefficient, because jump prediction works poorly - when I introduced a parameter to simple_playout::run: function pointer that replaced play_one and always put address of play_one there, then the code was slightly faster. I have *no idea* why it was so. - and most important: KISS Lukasz On 2/16/07, Darren Cook [EMAIL PROTECTED] wrote: trouble. Also, the alternative is usually function pointers which have atleast 50 times the overhead of a function object. Correct me if I'm wrong. function objects really cannot be 50 times more efficient as function pointer are rather efficient with very little overhead. With well-designed code, function objects (functors) should be compiled inline, and have zero overhead. Function pointers are never inlined (unless modern compilers are getting *really* clever), so they always have some overhead. Functors are therefore divide-by-zero-times more efficient (I don't know where Nick got the 50 times figure from :-). (If the functor is large enough to not be inlined then it is execution time that dominates and function call overhead is not important.) Using functors might cause more code, so less code fits in cache. I don't know how that affects overall performance. Darren ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
Lukasz, any chance you can access the assembly to see how the compiler optimized it differently? That is a strange result. All that I could think of is, if you have several places where the function is called, and the compiler used to be inlining it, it may be faster (for cache reasons) to make it a function call instead of inlining. Inlining is not always fastest! Regarding function pointers--from Agner Fog's guide: 3.7 Indirect jumps (all processors except PM and Core2) Indirect jumps, indirect calls, and returns may go to a different address each time. The prediction method for an indirect jump or indirect call is, in all processors except PM and Core2, simply to predict that it will go to the same target as last time it was executed. The first time an indirect jump or indirect call is seen, it is predicted to go to the immediately following instruction. (The Pentium M Core2 have more sophisticated indirect jump prediction) So, if a function pointer always points to the same function, all processors will predict the branch correctly! I am doubtful function objects would be much faster, except that they may be more likely to be inline-able. Also I disagree that well-designed code should cause function objects to be predicted at compile time--it seems to me that their purpose is for run-time polymorphism! I will just tell You about my experiences: - allmost all code of benchmark in Ego library is inlined (remove_stone is not) - function pointer are usually inefficient, because jump prediction works poorly - when I introduced a parameter to simple_playout::run: function pointer that replaced play_one and always put address of play_one there, then the code was slightly faster. I have *no idea* why it was so. - and most important: KISS Lukasz On 2/16/07, Darren Cook [EMAIL PROTECTED] wrote: trouble. Also, the alternative is usually function pointers which have atleast 50 times the overhead of a function object. Correct me if I'm wrong. function objects really cannot be 50 times more efficient as function pointer are rather efficient with very little overhead. With well-designed code, function objects (functors) should be compiled inline, and have zero overhead. Function pointers are never inlined (unless modern compilers are getting *really* clever), so they always have some overhead. Functors are therefore divide-by-zero-times more efficient (I don't know where Nick got the 50 times figure from :-). (If the functor is large enough to not be inlined then it is execution time that dominates and function call overhead is not important.) Using functors might cause more code, so less code fits in cache. I don't know how that affects overall performance. Darren ___ 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] Effective Go Library v0.101
The library is just a bunch of code and You can do whatever You want with it. I'm realistic, what matters is: what You have learned, does Your program works. So just get the code and hack it as fast as You can to get some effect asap, to feed Your motivation, to get more effect fast, etc... Concerning new versions ... it should be no big deal i guess. You can just copy some files and hack the copies. Another option is getting whole repository, so You can commit and branch locally: hg clone http://www.mimuw.edu.pl/~lew/hg/ cd libego here is Your hacking hg commit (this is local commit) hg pull (then whenever You want to check for new version) But repository-solution may be too much for a less than few weeks of work, it will be just a burden. So just grab the source, do something and be happy :) Lukasz On 2/14/07, Heikki Levanto [EMAIL PROTECTED] wrote: On Wed, Feb 14, 2007 at 10:57:38PM +0100, ?ukasz Lew wrote: Basically I wanted to implement a board in a hope that more people get attracted to Computer Go. But now this is more or less accomplished. So I decided to implement some kind of set canonical algorithms. But only those most common, I do not intend to make another GnuGo :) I just started UCT, as majority voted for it. Maybe patterns will come next. If You have something to propose, just go ahead :) I have a question about your philosophy. Do you mean us - the users of your library - to take the current version of the code, and start modifying it to our needs? Or do you want us to link with the library, so that we can upgrade to a later version without branching? I am asking because I would need a bit different playout routine. I could easily hack the library to do what I want, but that would in effect be a branch, and lead to maintenance problems later if/when you release a better version. I could also inherit from your classes, and override what I need. That would probably require a new header file, or something. Or I could abstract my needs into a more general interface, submit that as a patch, hope you accept it, and then use that. To get down to earth, I would like to look at the board at the end of each playout, calculate something more than just win/loss, and pass that info back to who ever called playout. One way to do that would be to pass a function pointer and a (void?) pointer to playout, and have it call back the function with the board, winner, and the void pointer. If that sounds more like C than C++, it is because I am a C programmer. If some other C++ idiom could do the same thing, all the better. Also, you have implemented the mercy rule in the playout code. If the library should be used without duplicating the code, this might be better left as a settable parameter. Like I said, I could easily write my own playout. But then I'd have to modify the gtp code to call that, and probably change a bit more here and there. In the end I would have forked your code, and when you release the next version, I would have to merge the changes in, and/or decide to go our separate ways. Perhaps I am worrying too much at such early state. I am just about considering to start my own project. But I'd like to do the right thing from the beginning. What do you think? Heikki -- 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] Effective Go Library v0.101
On Thu, Feb 15, 2007 at 11:23:57AM +0100, ?ukasz Lew wrote: I'm realistic, what matters is: what You have learned, does Your program works. So just get the code and hack it as fast as You can to get some effect asap, to feed Your motivation, to get more effect fast, etc... Ok, I do that. Actually I have already started, and if my experiment shows anything, I will report here some day soon. Need a few spare days first to do the main part of the hacking, but (as usual) I am busy with work, life, universe, and everything... Thanks again for a good library! -Heikki -- 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] Effective Go Library v0.101
Heikki Levanto wrote: To get down to earth, I would like to look at the board at the end of each playout, calculate something more than just win/loss, and pass that info back to who ever called playout. One way to do that would be to pass a function pointer and a (void?) pointer to playout, and have it call back the function with the board, winner, and the void pointer. If that sounds more like C than C++, it is because I am a C programmer. If some other C++ idiom could do the same thing, all the better. If you're going for more of a C++ library feel, function objects are the way to go. Function objects impose extra overhead but add a potential for a more generic adapter around other code that uses it. I have yet to convince myself of the benefit of C++ function objects for most applications. C++'s support for them is just too clunky in comparison to other C++ language features (or equivalent ones in other languages with built-in support). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
C++ function objects have overhead? This is news to me... Any decent compiler can optimize these as well as a direct function call. Also because of the way that the code is generated using templates (as in machine language isn't generated until the actual call is reached), function bodies are visible to the compiler at compile time a larger percentage of the time which allows for better optimization. Ofcourse there are ways to break this rule, but it is like anything in C++, if you don't know how to use it for speed, you can get yourself into trouble. Also, the alternative is usually function pointers which have atleast 50 times the overhead of a function object. Correct me if I'm wrong. - Nick On 2/15/07, Jason House [EMAIL PROTECTED] wrote: Heikki Levanto wrote: To get down to earth, I would like to look at the board at the end of each playout, calculate something more than just win/loss, and pass that info back to who ever called playout. One way to do that would be to pass a function pointer and a (void?) pointer to playout, and have it call back the function with the board, winner, and the void pointer. If that sounds more like C than C++, it is because I am a C programmer. If some other C++ idiom could do the same thing, all the better. If you're going for more of a C++ library feel, function objects are the way to go. Function objects impose extra overhead but add a potential for a more generic adapter around other code that uses it. I have yet to convince myself of the benefit of C++ function objects for most applications. C++'s support for them is just too clunky in comparison to other C++ language features (or equivalent ones in other languages with built-in support). ___ 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] Effective Go Library v0.101
2007/2/16, Nick Apperson [EMAIL PROTECTED]: trouble. Also, the alternative is usually function pointers which have atleast 50 times the overhead of a function object. Correct me if I'm wrong. - Nick function objects really cannot be 50 times more efficient as function pointer are rather efficient with very little overhead. Besides unless unless function object is small enough to be inlined it will be compiled as function pointer in many cases so there cannot be any efficiency difference - well unless function object get inlined that is. Petri ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
Functors if known at compile time will usually be inlines, but if they are too big to be inlined then a regular (not indirect) function call will be made so like call foo instead of like call [EDX] but when you use a function pointer instead of a template function, this is what happens: if all of the following conditions are met then we will get a direct call (like we do with templates) 1) function body of the function that takes a function pointer as a parameter is avaliable in current compilation unit (possible) 2) the function that takes a function pointer as a parameter is small enough to inline (possible, but for what we are talking about not the case probably) 3) the compiler has to be smart enough to know how to do this type of substitution (many compilers don't) with templates, the template code must be avaliable in a header (like condition #1 above) and the function is generated from that function and the functor will be compiled as a direct call. There are obviously 2 downsides. First, you have to use templates and have the template function body avaliable in the header (but this is a standard deal with templates). Second, if there are multiple possibilities for what the functor or callback could be (not the case in what we are talking about) this could lead to code bloat. As far as indirect calls being inefficient. I know it seems counterintuitive since they are so low level and I use them in certain instances (and I love them), but the reality is that indirect function calls are one of the worst things for performance because the decoding of instructions is done considerably ahead of time and the processor needs to predict branches in code to keep the pipeline of decoded instructions full. If it comes to a branch that is 2 way, it has a 50% chance and with recent processors this has been optimized so that if it guesses wrong it isn't the end of the world, but with an indirect call, it has no good way to guess the location (the most likely is supposed to be placed as an unconditional jump after the indirect call on intel platforms) and it can't spread its resources across all possible locations it could jump to because there are millions of possibilities. If a function is getting called many times and it is a small function, most of the resources are devoted to this overhead. I know they have made some strides with the core 2 duo, but this is a really hard to deal with problem. And all this is irrelevent if this aspect isn't the bottleneck. Anyway, this is kind of off topic... Point is, templates and functors are going to be faster and they certainly are cleaner so I prefer those. That is why the STL uses them. - Nick On 2/16/07, Petri Pitkanen [EMAIL PROTECTED] wrote: 2007/2/16, Nick Apperson [EMAIL PROTECTED]: trouble. Also, the alternative is usually function pointers which have atleast 50 times the overhead of a function object. Correct me if I'm wrong. - Nick function objects really cannot be 50 times more efficient as function pointer are rather efficient with very little overhead. Besides unless unless function object is small enough to be inlined it will be compiled as function pointer in many cases so there cannot be any efficiency difference - well unless function object get inlined that is. Petri ___ 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] Effective Go Library v0.101
?ukasz Lew wrote: Generally http://en.wikipedia.org/wiki/Disjoint-set_data_structure In my program it's a tree for each group of stones. In the root is number of pseudoliberties. Joining is cheap and checking group membership is cheap. Look at chain_t class. in board.cpp Best, ?ukasz Lew I had done similar once upon a time in my bot and later moved away from the disjoint set approach because of the headache that undo created. Out of curiosity, is this library intended to support MC clients specifically or other types of searches (such as alpha-beta that tends to back up its search frequently? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
On Wed, Feb 14, 2007 at 10:57:38PM +0100, ?ukasz Lew wrote: Basically I wanted to implement a board in a hope that more people get attracted to Computer Go. But now this is more or less accomplished. So I decided to implement some kind of set canonical algorithms. But only those most common, I do not intend to make another GnuGo :) I just started UCT, as majority voted for it. Maybe patterns will come next. If You have something to propose, just go ahead :) I have a question about your philosophy. Do you mean us - the users of your library - to take the current version of the code, and start modifying it to our needs? Or do you want us to link with the library, so that we can upgrade to a later version without branching? I am asking because I would need a bit different playout routine. I could easily hack the library to do what I want, but that would in effect be a branch, and lead to maintenance problems later if/when you release a better version. I could also inherit from your classes, and override what I need. That would probably require a new header file, or something. Or I could abstract my needs into a more general interface, submit that as a patch, hope you accept it, and then use that. To get down to earth, I would like to look at the board at the end of each playout, calculate something more than just win/loss, and pass that info back to who ever called playout. One way to do that would be to pass a function pointer and a (void?) pointer to playout, and have it call back the function with the board, winner, and the void pointer. If that sounds more like C than C++, it is because I am a C programmer. If some other C++ idiom could do the same thing, all the better. Also, you have implemented the mercy rule in the playout code. If the library should be used without duplicating the code, this might be better left as a settable parameter. Like I said, I could easily write my own playout. But then I'd have to modify the gtp code to call that, and probably change a bit more here and there. In the end I would have forked your code, and when you release the next version, I would have to merge the changes in, and/or decide to go our separate ways. Perhaps I am worrying too much at such early state. I am just about considering to start my own project. But I'd like to do the right thing from the beginning. What do you think? Heikki -- 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] Effective Go Library v0.101
Does anyone know what find-union algorithms Lukasz is referring to in the README file? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
On 2/13/07, Heikki Levanto [EMAIL PROTECTED] wrote: On Sun, Feb 04, 2007 at 02:13:33PM +0100, ?ukasz Lew wrote: Optimizing and refactoring became my hobby, but it's too absorbing :) It's time to add some features now. Just one question: Is the gtp support sufficient to play against other machines (if we ignore the rather trivial genmove code :-)? If not, adding the missing commands, even as dummies, would be a help for beginning programmers. Yes it is. Also, I notice that I can not use quarry (graphical interface for Go and Try GoGui. other games) to play against 'engine_opt'. Presumably it needs a few more gtp commands implemented. I will look into this, because if I am to write any sort of engine, I will want to be able to play agaist it. Will make a good warming-up exercise. Thanks again for a good, useful library. I have started to look into it, and once I got aroundthe namespaces and short names within, it looks reasonably clear. I will experiment with some ideas, and if anything useful comes out of them, I let you know. If I run into obvious improvements, I may even send a patch. Thanks :) Łukasz Regards Heikki -- 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] Effective Go Library v0.101
On 2/7/07, steve uurtamo [EMAIL PROTECTED] wrote:
And of course don't forget about this no_variable_in_for thing...
i'll have to read up on what you're describing.
The following pseudocode block
for (int i = 0; i 10; ++i) {
... code ...
}
// i's lifetime ends after the for loop does
is valid in just about any version of C++ and in the 1999 ISO C standard
(also known as C99), but it is not valid in most older C standards. (Some
older versions of gcc would accept this code but assign the wrong lifetime
(according to the standard) to variable i. If you want to test this code
with gcc, then use the -std=c99 flag, which, as of quite recently at least,
was not enabled by default.) There are at least a couple other C++-isms --
offhand, the // single-line comment form and variable declarations in the
middle of code blocks come to mind -- that are also valid in C99 but invalid
in at least some of the older C standards.
I'm not trying to run off on a language standards tangent! I just feared
that we might be headed towards one anyway, and I wanted to make sure the
information in it was not 8 years out of date.
Sorry, now back to go (I hope)...
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
has anyone tried writing a C interface to these functions? any suggestions about how to start? i love the idea of the library, but do not love the idea of writing C++. thanks, s. - Original Message From: Łukasz Lew [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Monday, February 5, 2007 2:41:23 AM Subject: Re: [computer-go] Effective Go Library v0.101 Effective Go Library: http://www.mimuw.edu.pl/~lew/ Don't pick lemons. See all the new 2007 cars at Yahoo! Autos. http://autos.yahoo.com/new_cars.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
There is nothing inherently cplusplusic, You can change class to struct (provided that Your compiler supports functions in structs). Add prefix player_ to every function in player:: namespace. And of course don't forget about this no_variable_in_for thing... Of course no printing on streams, etc etc etc. A lot of pain. A LOT. Maybe You prefer D? Łukasz On 2/5/07, steve uurtamo [EMAIL PROTECTED] wrote: has anyone tried writing a C interface to these functions? any suggestions about how to start? i love the idea of the library, but do not love the idea of writing C++. thanks, s. - Original Message From: Łukasz Lew [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Monday, February 5, 2007 2:41:23 AM Subject: Re: [computer-go] Effective Go Library v0.101 Effective Go Library: http://www.mimuw.edu.pl/~lew/ Don't pick lemons. See all the new 2007 cars at Yahoo! Autos. http://autos.yahoo.com/new_cars.html ___ 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] Effective Go Library v0.101
Hi, EGB 0.101 is the last performance release: 50 kpps on 1.4 GHz and 80 kpps on 2.2 GHz. Optimizing and refactoring became my hobby, but it's too absorbing :) It's time to add some features now. I consider 3 things: - liberties tracing - UCT tree search - pattern tracing Which feature You would like to see implemented? Do You have any idea how to implement liberties efficiently? Best Regards, Łukasz ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
UCT. Cheers, David On 4, Feb 2007, at 5:13 AM, Łukasz Lew wrote: It's time to add some features now. I consider 3 things: - liberties tracing - UCT tree search - pattern tracing Which feature You would like to see implemented? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
Effective Go Library: http://www.mimuw.edu.pl/~lew/ On 2/4/07, David Doshay [EMAIL PROTECTED] wrote: UCT. Cheers, David On 4, Feb 2007, at 5:13 AM, Łukasz Lew wrote: It's time to add some features now. I consider 3 things: - liberties tracing - UCT tree search - pattern tracing Which feature You would like to see implemented? ___ 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/
