Author: Alessandro Damiani
Date: 13:00:41 09/15/99
Go up one level in this thread
On September 15, 1999 at 15:29:38, Tim Mann wrote:
>> I think the table look up is the fastest way (on a 32-bit machine).
>
>Modern processors are so fast compared with memory that it is often faster to
>recompute something like this than to use table lookup, even if it takes a few
>more instructions. It's also important to use straight-line code if possible,
>because conditional branches that can go either way with nearly equal
>probability will often be mispredicted by the hardware, causing a slowdown.
>
>For instance, on an older Alpha that can't just do it in one instruction,
>the fastest known way to find the leftmost 1 in a 64-bit word is a sequence of
>about 22 instructions with no table lookups or branches. Current versions of
>the C compiler will emit this sequence inline if you call _leadz() and are
>compiling for a processor version that needs it.
>
>I wouldn't be surprised if some such sequence was fastest on the Pentium III
>and Athlon as well, even though they don't have 64-bit arithmetic units so more
>instructions would be needed...
>
> --Tim
Thank you for the information. But your post has a consequence to me: what
should I do now? Should I keep my table look-up? I have tried yesterday this one
(PLEASE NOTE: I don't use a routine called LastOne(.), so the easiest way to
test was to put the new code into the FirstOne(.) routine):
union twil {
unsigned long t[2];
BitBoard d;
};
int FirstOne (BitBoard b) {
register union twil x;
x.d= b;
if (x.t[0]) return 64-ffs(x.t[0]);
return 32-ffs(x.t[1]);
}
And on my Celeron it was faster than the table look-up. Any comments?
Alessandro
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.