Author: Eugene Nalimov
Date: 16:50:46 11/30/00
Go up one level in this thread
First, on most modern CPUs even version with branch will be faster than
division.
Second, there are better ways to add the value to the register only if register
is negative. Let's look at the following C code:
t = (x < 0) ? 255 : 0;
x += t;
x >>= 8;
One some CPUs there are 'conditional move' instructions. Examples are IA-64,
Alpha, PentiumPro and up (PII, PIII, PIV). So on PentiumPro and later CPU you
can use
xor edx, edx
test eax, eax
cmovl edx, 255
add eax, edx
shr eax, 8
But you can achieve even better result on plain old 386 or later CPU using
either arithmetic shift right by 31 bit or 'cdq' instruction, i.e.
cdq ; edx will be 0xFFFFFFFF for negative eax, 0 for positive
and edx, 255 ; edx will be 255 for negative eax, 0 for positive
add eax, edx
shr eax, 8
On 486/P5/P6/PII/PIII (and I suppose on PIV) CDQ is fast instruction.
Eugene
On November 30, 2000 at 15:35:21, Dieter Buerssner wrote:
>On November 29, 2000 at 13:21:35, Eugene Nalimov wrote:
>
>>Fortunately, there are code sequences that is almost as fast as original shift,
>>but produce "correct" result and much faster than naive division. For example,
>>you can replace
>> a / b, b is power of 2
>>by
>> (a + ((a >> (sizeof(int)*8-1)) & (b-1))) >> log2(b)
>
>Thanks for posting this.
>I think it is obvious, but just to ensure myself, a is a signed int and
>b is an unsigned int or constant value?
>
>for
>
> int a, b;
>
> b = a/256;
>
>the compiler can produce code as it was written as
>
> if (a < 0)
> a += 255;
> b = a >> 8; /* Assume arithmetic right shift */
>
>which obviously needs a branch. Will your code snippet generally produce
>faster code? Even when the branch is almost allways taken or almost allways not
>taken?
>
>>But my original point is still valid -- compiler have to emit different code for
>>division by power of 2 and right shift.
>
>I hope, my post didn't indicate, that I thought different.
>
>Regards,
>Dieter
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.