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