The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Determine if two integers have different sign
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 8 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Apr 30 2012, 4:46 am
Newsgroups: gnu.gcc.help
From: thomas.mer...@gmx.at
Date: Mon, 30 Apr 2012 01:46:19 -0700 (PDT)
Local: Mon, Apr 30 2012 4:46 am
Subject: Determine if two integers have different sign
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:

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 30 2012, 6:23 am
Newsgroups: gnu.gcc.help
From: Andrew Haley <andre...@littlepinkcloud.invalid>
Date: Mon, 30 Apr 2012 05:23:29 -0500
Local: Mon, Apr 30 2012 6:23 am
Subject: Re: Determine if two integers have different sign

thomas.mer...@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
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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 30 2012, 7:56 am
Newsgroups: gnu.gcc.help
From: thomas.mer...@gmx.at
Date: Mon, 30 Apr 2012 04:56:21 -0700 (PDT)
Local: Mon, Apr 30 2012 7:56 am
Subject: Re: Determine if two integers have different sign

I was not aware of the possibility to use:

(a<0)^(b<0)

(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

(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);
}

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

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 30 2012, 10:06 am
Newsgroups: gnu.gcc.help
From: Andrew Haley <andre...@littlepinkcloud.invalid>
Date: Mon, 30 Apr 2012 09:06:53 -0500
Local: Mon, Apr 30 2012 10:06 am
Subject: Re: Determine if two integers have different sign

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

>  (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.

To post a message you must first join this group.
You do not have the permission required to post.
More options May 2 2012, 9:24 am
Newsgroups: gnu.gcc.help
From: thomas.mer...@gmx.at
Date: Wed, 2 May 2012 06:24:49 -0700 (PDT)
Local: Wed, May 2 2012 9:24 am
Subject: Re: Determine if two integers have different sign
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?

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options May 2 2012, 10:03 am
Newsgroups: gnu.gcc.help
From: Andrew Haley <andre...@littlepinkcloud.invalid>
Date: Wed, 02 May 2012 09:03:02 -0500
Local: Wed, May 2 2012 10:03 am
Subject: Re: Determine if two integers have different sign

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

> 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.

To post a message you must first join this group.
You do not have the permission required to post.
More options May 7 2012, 12:56 pm
Newsgroups: gnu.gcc.help
From: thomas.mer...@gmx.at
Date: Mon, 7 May 2012 09:56:36 -0700 (PDT)
Local: Mon, May 7 2012 12:56 pm
Subject: Re: Determine if two integers have different sign

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:

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,
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.

To post a message you must first join this group.
You do not have the permission required to post.
More options May 8 2012, 9:58 am
Newsgroups: gnu.gcc.help
From: Andrew Haley <andre...@littlepinkcloud.invalid>
Date: Tue, 08 May 2012 08:58:51 -0500
Local: Tues, May 8 2012 9:58 am
Subject: Re: Determine if two integers have different sign

thomas.mer...@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.

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
.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:
testl   %edx, %edx
cmovne  %esi, %edx
jmp     .L10

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

Andrew.