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:
-- 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.
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;
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.
On Monday, April 30, 2012 12:23:29 PM UTC+2, Andrew Haley wrote:
> tm 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;
> }
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):
> 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.
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.
thomas.mer...@gmx.at wrote:
> On Monday, April 30, 2012 12:23:29 PM UTC+2, Andrew Haley wrote:
>> tm 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;
>> }
> I was not aware of the possibility to use:
> (a<0)^(b<0)
> What about:
> (a<0)!=(b<0)
> Is it faster or slower?
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.
> 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.
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.
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.
thomas.mer...@gmx.at wrote:
> 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]
>> 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;
>> }
>> 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.
> How does this better code for special cases look like?
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())
On Wednesday, May 2, 2012 4:03:02 PM UTC+2, Andrew Haley wrote:
>Thomas Mertes wrote:
> > 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]
> >> 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;
> >> }
> >> 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.
> > How does this better code for special cases look like?
> 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.
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.
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.
