Author: Robert Hyatt
Date: 08:33:41 09/23/02
Go up one level in this thread
On September 23, 2002 at 05:18:37, Gerd Isenberg wrote:
>On September 22, 2002 at 16:39:53, Robert Hyatt wrote:
>
>>On September 22, 2002 at 11:09:56, scott farrell wrote:
>>
>>>I have a board.Count method in my Java code, and it seems excessively slow. So
>>>much so I had to mostly exclude it from my evaluate function.
>>>
>>>I am coding in java I know, but I dont have any idea how this code even works (I
>>>borrowed it from deja a few months back - it was faster than a loop of 0 to 63).
>>>
>>>I found it was slow even counting a few bits that were on, say for counting the
>>>number of squares a bishop could move to.
>>>
>>>Can someone give me an opinion if these is reasonable code. Or is any sort of
>>>counting in bitboard is fately slow.
>>>
>>>Thanx
>>>Scott
>>>
>>>Here is the code:
>>>
>>>static final long ONES = 0x5555555555555555L;
>>> static final long TWOS = 0x3333333333333333L;
>>> static final int FOURS = 0x0f0f0f0f;
>>>
>>>public static final int count(long set) {
>>> set = (set & ONES) + ((set >>> 1) & ONES);
>>> set = (set & TWOS) + ((set >>> 2) & TWOS);
>>> int result = (int) (set & 0xffffffff) + (int) (set >>> 32);
>>> result = (result & FOURS) + ((result >>> 4) & FOURS);
>>> return (result * 0x01010101) >>> 24;
>>> }
>>
>>
>>A couple of things. The C programs use assembly code (BSF/BSR) to do this
>>very efficiently. Java is going to make that difficult.. :)
>>
>
>Yes, but BSF/BSF is rather inefficient for popcount (much slower than the
> "a & (a-1)" loop in assembler.
Sorry. I was thinking FirstOne() rather than popcount. I think that for
popcount, the fastest approach is the table lookup, using four 16-bit
probes and summing. I've tried 'em all. The above trick is faster on a
64 bit machine (the 4-step mask/and/shift/sum trick) but it didn't go faster
for me on X86.
>
>>Do you expect a lot of 1 bits or just a few? If just a few, then a simple
>>loop with a & (a-1) repeated can be very fast.. If a lot, perhaps a table-
>>lookup will be faster in Java...
>
>Yes, i think the lookup (with 64K table to lookup four 16Bit Words) will be
>fastest in Java.
>
>Regards,
>Gerd
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.