Determine if two integers have different sign

[thomas...@gmx.at]

I use the following condition, to determine, if a and b have
different signs:

(a>0&&b<0)||(a<0&&b>0)

Cases were a=0 or b=0 hold are handled separate. When twos
complement integers are used, something like

(a^b)<0

would do the same. The second solution is probably faster (but maybe
this assumption is wrong).

Can I assume that a C compiler like gcc does this optimization?

The code above is generated in the backend of the Seed7 compiler.
The type of integer representation is known, so the Seed7 compiler
could decide, which code should be generated.

Does it pay off, to do such low level optimizations, or is it better
to leave them to the C compiler?

The example code above is used by the Seed7 compiler as part of the
modulo (mod) operator. The whole modulo function is implemented
with:

c=a%b,((a>0&&b<0)||(a<0&&b>0))&&c!=0?c+b:c

With the "optimization" above it would be:

c=a%b,(a^b)<0&&c!=0?c+b:c

The mod operator is explained in this chapter:

http://seed7.sourceforge.net/manual/types.htm#integer


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

[Andrew Haley]

thomas...@gmx.at wrote:
> I use the following condition, to determine, if a and b have
> different signs:
>
> (a>0&&b<0)||(a<0&&b>0)
>
> Cases were a=0 or b=0 hold are handled separate. When twos
> complement integers are used, something like
>
> (a^b)<0
>
> would do the same. The second solution is probably faster (but maybe
> this assumption is wrong).
>
> Can I assume that a C compiler like gcc does this optimization?

No, unfortunately.

> The code above is generated in the backend of the Seed7 compiler.
> The type of integer representation is known, so the Seed7 compiler
> could decide, which code should be generated.
>
> Does it pay off, to do such low level optimizations, or is it better
> to leave them to the C compiler?

There isn't any need to depend on two's-completement arithmetic.
I would simply do this:

int div3(int a, int b) {
int sign = (a < 0) ^ (b < 0);
int c = a % b;
if (sign && c != 0)
return c + b;
else
return c;
}

which generates

movl %edi, %edx
movl %edi, %eax
sarl $31, %edx
idivl %esi
xorl %esi, %edi
jns .L16
testl %edx, %edx
setne %al
addl %edx, %esi
testb %al, %al
cmovne %esi, %edx
.L16:
movl %edx, %eax
ret

There is are some other forms that generate better code for special
cases, in particular when it is known a priori that the divisor is
positive. However, I don't think you'll beat this for the general
case.

Andrew.

[thomas...@gmx.at]

On Monday, April 30, 2012 12:23:29 PM UTC+2, Andrew Haley wrote:

I was not aware of the possibility to use:

(a<0)^(b<0)

What about:

(a<0)!=(b<0)

Is it faster or slower?
As I said, the Seed7 compiler knows, which integer representation is
used. So it could use

(a^b)<0

instead of

(a<0)^(b<0)

when two's complement representation is used. Do you think that
(a^b)<0 is faster?

Btw. The Seed7 compiler does not use a function like div3. Instead
it produces inline code. The Seed7 source code:

modResult := dividend mod divisor;

is currently translated to (a little bit simplified):

{
inttype tmp_a;
inttype tmp_b;
inttype tmp_c;
o_1017_modResult=
(tmp_a=o_1015_dividend,
tmp_b=o_1016_divisor,
tmp_c=tmp_a%tmp_b,
((tmp_a>0&&tmp_b<0)||(tmp_a<0&&tmp_b>0))&&
tmp_c!=0?tmp_c+tmp_b:tmp_c);

}

> which generates
>
> movl %edi, %edx
> movl %edi, %eax
> sarl $31, %edx
> idivl %esi
> xorl %esi, %edi
> jns .L16
> testl %edx, %edx
> setne %al
> addl %edx, %esi
> testb %al, %al
> cmovne %esi, %edx
> .L16:
> movl %edx, %eax
> ret
>
> There is are some other forms that generate better code for special
> cases, in particular when it is known a priori that the divisor is
> positive. However, I don't think you'll beat this for the general
> case.

The Seed7 compiler generates special code when dividend or divisor
(or both :-) ) are known at compiler time.

[Andrew Haley]

It's very slightly slower with the current gcc.

> As I said, the Seed7 compiler knows, which integer representation is
> used. So it could use
>
> (a^b)<0
>
> instead of
>
> (a<0)^(b<0)
>
> when two's complement representation is used. Do you think that
> (a^b)<0 is faster?

I am certain that it is not faster for gcc, which generates

xorl a, b
jns

for both. Using (a<0)^(b<0) in C source is better because it makes no
assumptions about integer representation. The generated code is just
the same.

Andrew.

[thomas...@gmx.at]

On Monday, April 30, 2012 12:23:29 PM UTC+2, Andrew Haley wrote:

[regarding the implementation of the Seed7 modulo (mod) operator
(See: http://seed7.sourceforge.net/manual/types.htm#integer ) in C]

How does this better code for special cases look like?

When the divisor is constant the Seed7 compiler generates
special case code for -1, 0, 1 and for powers of two. When
the divisor is not a special case, but positive the C code

c=a%b,a<0&&c!=0?c+b:c

is used. For a negative divisor the C code

c=a%b,a>0&&c!=0?c+b:c

is used. Do you have suggestions for better code?

When the dividend is constant the Seed7 compiler generates
special case code for 0. For the normal case (dividend
constant) and a positive dividend the following C code is
generated

c=a%b,b<0&&c!=0?c+b:c

For a negative dividend the following C code is generated

c=a%b,b>0&&c!=0?c+b:c

Do you know better code for this?

For a dividend of 1 the following experimental code is used:

b<=0?(b==0?error():b+1):(b==1?0:1)

(error() is an int function, which uses longjmp())

Is this code really faster?
Would it make sense to use similar code for other cases?

Thank you in advance, for your effort.

[Andrew Haley]

Like this:

static int div2_int (int _a, int _b)
{
unsigned long long a = _a;
unsigned int b = _b;

if (_a < 0)
a += ((unsigned long long)b) << 32;

return (int)(a%b);
}

You can prove that after the division the modulus is the same, because
you are adding a multiple of the divisor to the dividend.

The efficiency of this depends on your compiler being smart enough to
notice that an unsigned remainder of long % int can be done in a
single instruction. Even recent versions of 32-bit gcc don't do this.

> For a dividend of 1 the following experimental code is used:
>
> b<=0?(b==0?error():b+1):(b==1?0:1)
>
> (error() is an int function, which uses longjmp())
>
> Is this code really faster?

That's impossible to say without measuring.

Andrew.

[thomas...@gmx.at]

On Wednesday, May 2, 2012 4:03:02 PM UTC+2, Andrew Haley wrote:

Why is this situation so hard to recognize for gcc?

BTW. Many thanks for your suggestion of

(a<0)^(b<0)

The new release of the Seed7 compiler uses

c=a%b,a<0^b<0&&c!=0?c+b:c

to implement the mod operator. To honour you I mentioned
you in the release note and in the change log. See:

http://sourceforge.net/projects/seed7/files

Would it make sense to use code which avoids a jump?
Something like

c=a%b,(-(a<0^b<0&&c!=0)&b)+c


Regards,

[Andrew Haley]

thomas...@gmx.at wrote:
> On Wednesday, May 2, 2012 4:03:02 PM UTC+2, Andrew Haley wrote:
>>Thomas Mertes wrote:
>>
>> The efficiency of this depends on your compiler being smart enough to
>> notice that an unsigned remainder of long % int can be done in a
>> single instruction. Even recent versions of 32-bit gcc don't do this.
>
> Why is this situation so hard to recognize for gcc?

I am not sure, but I don't think it is very hard to recognize. It
just hasn't been done.

> BTW. Many thanks for your suggestion of
>
> (a<0)^(b<0)
>
> The new release of the Seed7 compiler uses
>
> c=a%b,a<0^b<0&&c!=0?c+b:c
>
> to implement the mod operator. To honour you I mentioned
> you in the release note and in the change log. See:
>
> http://sourceforge.net/projects/seed7/files
>
> Would it make sense to use code which avoids a jump?
> Something like
>
> c=a%b,(-(a<0^b<0&&c!=0)&b)+c

I think it's pretty marginal. The first version gets you

movl %edi, %eax
cltd
idivl %esi
shrl $31, %edi
movl %esi, %eax
shrl $31, %eax
cmpl %eax, %edi
je .L10
testl %edx, %edx
je .L10
addl %esi, %edx
.L10:
movl %edx, %eax
ret

and the second

movl %edi, %eax
cltd

idivl %esi
xorl %esi, %edi

sarl $31, %edi
xorl %eax, %eax

testl %edx, %edx
setne %al

negl %eax
andl %eax, %edi
andl %esi, %edi
leal (%rdi,%rdx), %eax
ret

I don't know which is best.

You can get a small improvement with

int div3(int a, int b) {
int sign = (a < 0) ^ (b < 0);
int c = a % b;

if (__builtin_expect(sign && c != 0, 0))

return c + b;
else
return c;
}

which moves the function epilogue code inline:

movl %edi, %eax
cltd
idivl %esi
shrl $31, %edi
movl %esi, %eax
shrl $31, %eax
cmpl %eax, %edi
jne .L11
.L10:
movl %edx, %eax
ret
.L11:
addl %edx, %esi
testl %edx, %edx
cmovne %esi, %edx
jmp .L10

This isn't a huge advantage here, but may well be when this is
inlined.

Andrew.