Author: Eugene Nalimov
Date: 10:21:35 11/29/00
Go up one level in this thread
On November 29, 2000 at 09:28:11, Dieter Buerssner wrote:
>On November 29, 2000 at 04:38:33, Eugene Nalimov wrote:
>
>>On November 29, 2000 at 02:53:42, Jeremiah Penery wrote:
>>
>>>On November 28, 2000 at 23:59:14, Ed Schröder wrote:
>>>
>>>>Especially multiplies has been improved dramatically in the latest
>>>>generation of processors. Nowadays it is hardly an issue anymore. I
>>>>still use << where ever I can but I have no problems to use * so now
>>>>and then.
>>>
>>>It seems like compilers should produce the same assembly code for things like
>>>a<<1 and a*2, but of course I'm not sure if they do. Ditto for a>>1 and a/2.
>>>(and also <<2 = *4, etc.)
>
>The compilers I checked indeed produce the same code for unsigned integral
>values. Also note, that sometimes shift is not the fastest. for 2*a add can
>be faster, or even neither shift, mul or add are needed at all on x86. I.e.
>
> size_t a;
> int *p
> ...
> p[2*a] = 0;
>
>the last expression can be translated to one assembler statement, when p
>and a are allready in an register. (Something like mov 0, (eax,edx,8))
>
>>Of course a>>1 and a/2 should generate different code (hint: check value of both
>>expressions for a == -1).
>
>It can also be noted, that right shifting of negative values is implementation
>defined in C (and probably also C++, but I cannot check right now). So
>you cannot know in advance (without reading the compiler specific documantation)
>what the result will be, and it will yield in unportable code.
>
>But even with signed integral values, the compiler sometimes can produce
>the same code.
>
>int foo(int value)
>{
> if (value > 0)
> value /= 4; /* Produces the same code as value >>= 2; */
> return value;
>}
>
>If you have to scale signed integral values down, and you do not care
>about the possible differences of / (2**n) and >>n, this is probably the
>only example, where you can gain something by using the shift operator.
>In many cases, using unsigned integral quantaties where appropriate,
>will make the compiler produce better code for division and modulo.
>
>Regards,
>Dieter
First, behavior of signed right shift is really implementation-dependend, but
*any* C programmer will expect that he/she will get "proper" arithmetic signed
shift. I believe that almost any large C program relies on this. Yes, by doing
so those programs violate the standard, but unfortunately, compiler writers have
to implement not only standard, but also "general expectations regarding
behavior".
Second, can you imagine the implementation where result of the division will be
different depending on the second operand being constant or not? So we cannot
blindly replace all the signed divisions by power of 2 by shifts.
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)
E.g. on x86 you can divide signed register EAX by 2 using following code
sequence:
cdq
and edx, 1
add eax, edx
shr eax, 1
But my original point is still valid -- compiler have to emit different code for
division by power of 2 and right shift.
Eugene
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.