Author: Bas Hamstra
Date: 02:46:24 04/26/01
Go up one level in this thread
On April 25, 2001 at 19:20:28, Shane Hudson wrote:
>On April 25, 2001 at 16:53:56, Bas Hamstra wrote:
>>On April 25, 2001 at 14:53:00, Dann Corbit wrote:
>>>On April 25, 2001 at 14:38:48, Bas Hamstra wrote:
>>>>On April 25, 2001 at 14:31:27, Bas Hamstra wrote:
>
>[stuff snipped]
>
>>>This works fairly well (which is {I suspect}) what is in your table:
>>>
>>>static int inbits[256] = {
>>> 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
>....
>>> 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
>>>};
>>>
>>>int Count(const BITBOARD B)
>>>{
>>> return inbits[(unsigned char) B] +
>>> inbits[(unsigned char) (B >> 8)] +
>>> inbits[(unsigned char) (B >> 16)] +
>>> inbits[(unsigned char) (B >> 24)] +
>>> inbits[(unsigned char) (B >> 32)] +
>>> inbits[(unsigned char) (B >> 40)] +
>>> inbits[(unsigned char) (B >> 48)] +
>>> inbits[(unsigned char) (B >> 56)];
>>>}
>>
>>Yes, that's how my code works as well.
>>
>>>You might want to time this in comparison to your routine. For that matter, I
>>>have a collection of bit counting routines found here:
>>>ftp://cap.connx.com/pub/bitcount/BITC.ZIP
>>>
>>>That might prove useful. A benchmark routine is included. They are for 32
>>>bits, but the techniques easily generalize to larger integers.
>>
>>Thanks, I will certainly take a look because I use it all the time and I am not
>>quite satisfied with the current performance.
>>
>>Best regards,
>>Bas.
>
>Some time ago I profiled a number of bit-counting routines (on 32-bit
>numbers, and for file system bitmap lookup code instead of chess, but
>the techniques are similar for 64 bits) and found that for random inputs,
>the "folding" method (it may have a real name, I don't know) with no
>array lookups or branches was clearly the fastest, even beating lookups
>of 256-element tables (like you have) or 65536-element tables. Here is
>the folding method for 32 bits (it assumes unsigned longs are 32 bits):
>
>int
>bitcount (unsigned long x)
>{
> x = ((x & 0xAAAAAAAAUL) >> 1) + (x & 0x55555555UL);
> x = ((x & 0xCCCCCCCCUL) >> 2) + (x & 0x33333333UL);
> x = ((x & 0xF0F0F0F0UL) >> 4) + (x & 0x0F0F0F0FUL);
> x = ((x & 0xFF00FF00UL) >> 8) + (x & 0x00FF00FFUL);
> x = ((x & 0xFFFF0000UL) >> 16) + (x & 0x0000FFFFUL);
> return (int) x;
>}
>
>The 64-bit equivalent has only one more "x = ...." expression, so it
>scales logarithmically. I have it in a file somewhere...
>
>However, when got curious and I modified crafty's PopCnt() to use this
>method, I found no improvement -- which was surprising until I checked
>the inputs and found the input value was almost always below 3, and
>was 0 about 70% of the time. So the best method depends highly on
>the distribution of input values.
>
>Cheers,
>Shane
Hi Shane,
I use PopCnt all the time, for (I think) more populated bitmaps than Crafty, so
I am going to try this (though I don't understand howq it works yet). However
for 32 bit cpu's it is probably faster to do two 32 bit counts than modify the
routine like you suggested. Bitshifts on 64 bit numbers are not so efficient, I
think.
Interesting stuff, thanks!
Bas.
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.