All this talk of D inspired me to bite the bullet and try it out myself. (I had been curious to check it out in detail for some time)
Sadly, my experience with D is not as shining as others. I tried to take the source of my C++ based bot (housebot) and convert it over. I really like how foreach is handled and the ability to embed unit tests and invariants. I found the contract programming to be more eye candy than practical (but I still used it). On the down side, I noticed a significant lack of documentation and difficult to find get it at my fingertips. Support for an STL equivalent is a few years out of date. minTL seemed the most mature but didn't compile out of the box. The changes to get it to compile seemed minor and it may have been a bad environment set up. On mailing lists, people say that you can use the fancy D arrays for most (but not all) STL containers. The const keyword has been completely removed from the language and makes it hard to force such restrictions on "library users". minTL goes far enough to force a const equivalent by using some template parameters and static if's. Beyond that, there's a few things that just drive me batty like no support for a toString property for enums or how my board class's unit test refused to run until other code instantiated it (both makes some sense actually). It's not a bad language, but I feel like it still rather immature. If the docs were good and a templating library was up to date, I probably would have kept playing around. For now I decided to stop... :( -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Don Dailey Sent: Friday, December 15, 2006 9:17 PM To: Łukasz Lew Cc: computer-go Subject: Re: [computer-go] Fast Board implementation On Sat, 2006-12-16 at 01:47 +0100, Łukasz Lew wrote: > On 12/16/06, Don Dailey <[EMAIL PROTECTED]> wrote: > > Another report on D programming. It appears that D programs are about > > 1.5X slower in general - at least for what I'm doing. > > > > At one point I reported about 7% slower, but that was a mistake on my > > part. > > > > The difference in programming effort and just plain clean code is quite > > large - D was well designed and after doing a lot of programming in D, > > it's a real drag going back to C! > > Is it? > I mean what features of D You've used that make it inconvenient to go back to C? A good part of it is just the extra syntax in C. D isn't expressive like Ruby or Python, but it is expressive enough that you are willing to try something that you might not want to in C without getting a cup of coffee first. Even just the foreach loop, which is a petty thing I admit, but it makes life easier and the code looks cleaner. You can get rid of most of the pointer ugliness. I really like that. My C program is full of functions where you pass pointers to something: MakeMove( position *p, mv_t mv ) p->bd[mv] = 1 + (p->ctm & 1); etc... In D you declare arguments as "in", "out" or "inout" and forget about the pointer syntax such as &x, *x blah blah blah. When you have a lot of complex expressions this gets rather convoluted in C. arrays are real nice - you can slice and dice them. You can sort them without all the setup code of c. You can sort arrays of structs by putting a comparison function right inside the structure. Most of these things can be done in C with extra setup code. You don't need foreach loops, you can add a couple of lines of code and get the same functionality in C. But the author of D payed attention to all the little annoyances of C and fixed many of them. And he fixed a lot of stuff that generates bugs. You can write code a little faster in D, but you can write finished bug-free code a LOT faster. It's a whole like of little things like that. Array concatenation, associative arrays, dynamic arrays, etc. Associative arrays is a killer feature even though every language has libraries - it's not the same as having it built into the language. I probably wouldn't use associate arrays in parts of the program that I expect to port to C, but it's hard to live without associative arrays and I've always wanted them in C. Here is a good page to give a quick comparison with C: http://www.digitalmars.com/d/comparison.html - Don > > > > But it appears that you can have your cake and eat it too by just making > > a low level library in C, and doing most of the other stuff in D. D > > and C are link compatible and there is no effort in making this work - > > it just works. > > > > I have indeed been able to experiment more quickly and easily doing it > > in D, so I have come up with what seems like a nice formula: > > > > 1. Start by doing everything in D. > > 2. Optimize and experiment. > > 3. When you are happy, redo the low level stuff in C. It will > > link > > right in. > > 4. You can still continue to experiment. > > > > Porting to C from D is quite easy because D is pretty much a cleaned up > > version of C. It's easy to make this port when you know exactly what > > you want. > > > > I've been able to do a substantial amount of experimentation using D and > > the D program is now just slightly faster than the old C program due to > > the improved > > data structures. I should be able to get close to 25,000 games per > > second if > > I get the 1.5 X improvement going to C. This is only about 3K of code > > that will > > have to be written in C, where much of the code is identical to C > > anyway. > > > > - Don > > > > > > On Thu, 2006-12-14 at 22:51 -0500, Luke Gustafson wrote: > > > Are you using the union-find algorithm with path compression for joining > > > strings? It's very simple and very fast. > > > http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_f orests > > > > > > The other main thing to consider is reducing branch mispredictions, which > > > (I'm guessing) could very well use more clock cycles on a P4 than performing > > > the actual calculations themselves. I think this is why the next_stone list > > > is faster than using e.g. a recursive algorithm, which involves a lot of > > > if's that cannot be predicted. > > > > > > Compact data I think is unnecessary, although perhaps eliminating the String > > > struct would speed things up a tad. In fact, on a P4, shift operations are > > > slower than L1 cache memory retrievals, so fancy packing of data is not > > > worthwhile. As long as all data fits in the L1 cache it should be max > > > speed. > > > > > > I am working on a program myself, and I will be porting it to assembly at > > > some point; right now I am just experimenting with the algorithm design in > > > C. (Although this happens pretty slowly since I am very busy with work.) I > > > think that this sort of algorithm is perfect for assembly language, where > > > hand-optimization can be much better than compiler optimization. I will let > > > you know how it turns out compared to Lukasz :) > > > > > > >> At the time of Your post I've had it already implemented and regarded > > > >> it like "my sweet secret" :) > > > > > > > > I don't know how sweet this secret is, but it does help. I just > > > > implemented it in Lazarus and I get about a 20% speedup. That's not > > > > bad, but nothing to write home about. To a chess programmer this is > > > > rather enormous! I am guessing that the win would be much greater on > > > > bigger boards. > > > > > > > > In principle it would probably be FAR faster, but it adds extra > > > > complexity, > > > > operations and overhead to executing a move which subtracts some from > > > > the > > > > savings. > > > > > > > > The question is: "what is the best way to implement it?" The problem > > > > is that you now must track pseudo liberty counts for every chain on > > > > the board. This is more complicated obviously. > > > > > > > > Every time a stone is placed or removed, 4 additional entries must be > > > > accessed in order to update the pseudo liberty counts. > > > > > > > > It's still a good trade-off because the testing for whether a move > > > > is a capture or suicide is cheap. > > > > > > > > I'm reviewing my design now and I think I see some ways to improve. > > > > > > > > Here is the current data structure (assuming the 9x9 board): > > > > > > > > 1. A 10x11 board (actually 10x11 plus 1 for diagonal checking.) > > > > 0 = empty > > > > 1 = white > > > > 2 = black > > > > 4 = off-board points. > > > > > > > > 2. Another 10x11 board-like array - if there is a occupied point on > > > > the board this array contains the index (hash key) of a "string" > > > > data type. > > > > > > > > 3. A list of string data types (a struct in C): > > > > 1. stone count > > > > 2. pseudo liberties for the whole string > > > > 3. a reference stone. > > > > > > > > To save time, the list of strings is really more like a hash table, > > > > not a proper list. It's a perfect hash table because the keys will > > > > never collide. I use the reference stone as the key for each string > > > > which is generally the first stone placed in the string. So the hash > > > > key computation is just a table lookup and is the only thing the > > > > second table is used for. > > > > > > > > So to summarize, I really have 3 10x11 arrays, one of them is an array > > > > of structs in C (actually in D) and is viewed as a hash table. > > > > > > > > I could pack all of the information into a single array. Here is one > > > > possible scheme which fits in 32 bits and accommodates all board sizes: > > > > > > > > 3 bits to identify white/black/empty/off-board > > > > 9 bits for the hash key (the reference stone) > > > > 9 bits for pseudo liberty count > > > > 9 bits for stone count > > > > > > > > It's kind of interesting when you think about it. A single array does > > > > triple duty as a: > > > > > > > > 1. Go board. > > > > 2. Hash table. > > > > 3. lookup table - to get the "hash key" (table index) of the data > > > > for > > > > the string that occupies this point. > > > > > > > > The hash table bits in the table are usually irrelevant, it is only > > > > valid for the single point that represent the hash table entry for a > > > > given string. > > > > > > > > So this scheme does no list manipulations and has a fixed size in > > > > memory. It's compact and I think fast. Is there anything obvious I'm > > > > missing that simplifies things? > > > > > > > > By the way, stone count field is helpful but not necessary. But it's > > > > trivial to keep updated and it's convenient. > > > > > > > > Using the compact representation would slow down some of the > > > > operations which are in fast inner loops now, but would probably be a > > > > win overall, perhaps a big win because I'm not manipulating several > > > > different arrays. > > > > > > > > So I will also try this compact implementation unless someone has a > > > > superior scheme to suggest. > > > > > > > > > > > > - Don > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > On Mon, 2006-12-11 at 20:00 +0100, Łukasz Lew wrote: > > > >> At the time of Your post I've had it already implemented and regarded > > > >> it like "my sweet secret" :) , so I was expecting that when You > > > >> published it everybody will appreciate, and start using. But I guess > > > >> it wasn't easy to see benefits. > > > >> I wonder how many really good ideas came through this list unnoticed. > > > >> > > > >> Best Regards, > > > >> Lukasz > > > >> > > > >> > > > >> On 12/11/06, House, Jason J. <[EMAIL PROTECTED]> wrote: > > > >> > Wow. Did some of my early posts on liberties/chains actually get used > > > >> > by someone? Or did the idea of pseudo-liberties and union sets exist > > > >> > before my post(s) on the topic? I remember a lot of negative feedback > > > >> > on pseudo-liberties at the time of my post. > > > >> > > > > >> > -----Original Message----- > > > >> > From: [EMAIL PROTECTED] > > > >> > [mailto:[EMAIL PROTECTED] On Behalf Of Lukasz Lew > > > >> > Sent: Monday, December 11, 2006 1:31 PM > > > >> > To: [EMAIL PROTECTED] > > > >> > Cc: computer-go > > > >> > Subject: Re: [computer-go] Fast Board implementation > > > >> > > > > >> > Pseudo liberties of a group is a sum of liberties of each stone, > > > >> > example: > > > >> > > > > >> > OOOOO > > > >> > OXXXO > > > >> > OX.XO > > > >> > OXXXO > > > >> > OOOOO > > > >> > > > > >> > "X" group have 4 pseudo liberties. > > > >> > > > > >> > If You merge two groups just add pseudo liberties. > > > >> > If PL = 0 then group should be removed. > > > >> > > > > >> > This is simple and sufficient :) > > > >> > > > > >> > Lukasz > > > >> > On 12/11/06, Don Dailey <[EMAIL PROTECTED]> wrote: > > > >> > > > > > >> > > > > > >> > > On Mon, 2006-12-11 at 18:22 +0100, Łukasz Lew wrote: > > > >> > > > - pseudo liberties at top of union-set tree > > > >> > > > > > >> > > > > > >> > > Refresh my memory on this. I remember talking about this a long > > > >> > time > > > >> > > ago. A psuedo liberty is an upper bound on how many liberties there > > > >> > are > > > >> > > for a given string, correct? Sometimes a liberty gets counted twice > > > >> > or > > > >> > > more? > > > >> > > > > > >> > > But if it goes to zero or one it's correct for any given string? > > > >> > > > > > >> > > Is the idea that it's lightning fast to update incrementally? > > > >> > > > > > >> > > - 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/ > > > > > > > > _______________________________________________ > > > > 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/
