Author: Matt Taylor
Date: 23:56:31 01/06/03
Go up one level in this thread
On January 07, 2003 at 01:03:41, Russell Reagan wrote:
>On January 06, 2003 at 23:25:57, Nathan Thom wrote:
>
>>But im sure it could be much faster in assembler, i just dont know how.
>
>You are headed down the wrong path here. Don't worry about writing it in
>assembler. Worry about using a good algorithm. For example, the code you posted
>will potentially do 64 iterations through the loop to count a single bit, and
>that is very innefficient. Try something like this:
>
>int count (bitboard b) {
> int c = 0;
> while (b) {
> b &= b - 1;
> c++;
> }
> return c;
>}
>
>That will do N iterations, where N is the number of bits set. So if there are 5
>bits set in 'b', it will go through the loop 5 times. Your version might go
>through the loop 50 or 60 times depending on which bits are set.
>
>You are assuming that your function is inefficient, and it is. Then you are
>assuming that writiing it in assemler is the solution, which is an incorrect
>assumption.
>
>If your bitboards are not densely populated, just use this function I gave. If
>they are more densely populated most of the time, there are other more efficient
>methods of getting a population count. I don't know any off hand, but surely
>someone else can post something.
>
>I use this function (above) in my program and my program is fairly fast (fast
>enough, anyway). I believe Crafty also uses that function. Don't sweat this kind
>of stuff. Just find an efficient algorithm (doesn't have to be the absolute most
>efficient thing known to man) and move on to more important things. No program
>ever won the world championship because it had a fast popcount.
>
>Russell
If his program does population counts often, he may as well use an assembly
routine. He doesn't need to write it himself; others have done that.
Beside that, a better algorithm is described in the AMD optimization manual and
on the assembly gems link that someone else posted.
FYI Crafty's population count and LSB/MSB scan routines are in assembly. Refer
to X86.s and vcline.h
-Matt
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.