Author: Gerd Isenberg
Date: 10:13:53 12/22/05
Go up one level in this thread
On December 22, 2005 at 11:42:43, Tord Romstad wrote:
>On December 21, 2005 at 17:09:02, Andreas Guettinger wrote:
>
>>I agree in sense of portability asm code is bad, I don't like it too.
>
>In my very subjective opinion, the problem is not only portability,
>but also aesthetics. When I find myself having to use assembly
>language in order to achieve good performance, I usually decide
>that I should use a different data structure or a different
>programming language.
>
>>Crafty
>>falls back to plain C code for FirstOne(), LastOne() if no inline_asm or
>>inline_ppc is used. For the G4 I found the speedup to use cntlzw instead
>>neglectable (maybe 5%). Surprisingly this seems to be different for 64bit.
>>Crafty seems to rely heavily on these bitcounting function, but that may be
>>different for other engines and they may not profit a lot from the asm code.
>
>I'm afraid it would be the same thing for Glaurung. I use a lot of loops
>through the non-zero bits of a bitboard, and I use bit counting for
>mobility evaluation.
>
>>Additionally the C lookup table approach of crafty that replaces the asm
>>functions might be not the fastest for ppc. There was a thread some time ago
>>where different algorithms where compared (magic bitscan, table, gerd, eugene,
>>etc. ) I still have the source for them lying around somwhere.
>
>I use the following one in Glaurung:
>
>const uint32 BitTable[64] = {
> 0,1,2,7,3,21,16,35,4,49,22,52,17,66,36,80,5,33,50,70,23,86,53,96,18,55,67,
> 102,37,98,81,113,119,6,20,34,48,51,65,71,32,69,85,87,54,101,97,112,118,19,
> 39,64,68,84,100,103,117,38,83,99,116,82,115,114
>};
>
>inline uint32 first_1(bitboard_t b) {
> return BitTable[((b&-b)*0x218a392cd3d5dbfULL)>>58];
>}
>
>The last time I checked, it was faster than the other non-assembly language
>alternatives on my G5. The code was posted by Gerd, I think.
Yes, posted a lot of times, but not with that strange indizes ;-)
The original source is:
Charles E- Leiserson, Harald Prokop and Keith H. Randelll from MIT
"Using de Bruijn Sequences to index a 1 in a Computer Word"
http://supertech.csail.mit.edu/papers/debruijn.pdf
Some additional stuff:
http://hornid.com/cgi-bin/ccc/topic_show.pl?pid=356337;hl=De%20Bruijn#pid356337
A faster De Bruijn Generator:
http://hornid.com/cgi-bin/ccc/topic_show.pl?pid=411355;hl=DeBruijn#pid411355
0x218a392cd3d5dbfULL is reserverd for you, Tord ;-)
Gerd
>
>Tord
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.