[9fans] Integer arithmetic: some lessons

[9fans] Integer arithmetic: some lessons

[tlaronde]

Hello,

Still about integer arithmetic.

In my case, we have strictly the same C89 code (the process is hopefully
deterministic), and the test is on the very same node (very same
machine/cputype): plan9/386, NetBSD/i386.

The implementation of the C library is here not the problem. The problem
involves purely integer arithmetic.

And everything goes OK with gcc/NetBSD, but the most "calculus" program:
METAFONT, fails in some cases on Plan9 (TeX is indeed more a processor
and is simpler: works).

To be short the problem is about the negative integers.

Nothing is mandatory (in C89) about : a / b, only that :
	a == (a / b) * b + a % b;

There is two main types of choices: "translation preserving" and
"negation preserving" i.e. in this later case :
	(-a) div b == -(a div b).

This is "negation preserving" for both gcc and ken-cc.

Furthermore, (a + b) / 2 does not lead---with negative values--- to the
same as (a+b) >> 1: in this later case, we have the "floor", while the
"negation preserving" div leads the "ceil" for negatives.

This is the same with both gcc and ken-cc.

But if I start replacing div by binary shifting (when power of two are
involved), I have varying results with ken-cc, but not with gcc, whether
I set optimization or not.

Conclusion (apparently): gcc always translate div involving power of two
to binary manipulations, while (apparently) ken-cc does not.

Conclusion: I will have to replace in METAFONT all div involving power
of two to binary operations, since if I replace in some places and not
in others, I wreak havoc the algorithms since computations are not done
the same way for combined chunks.

If others have problems porting software to Plan9 (or from Plan9), this
may be a clue.

And I don't think---if I'm correct---that ken-cc is at fault, since the
results of (a+b)/2 and (a+b) >> 1 are not the same, so this is changing
the semantics of a program beyond the reach of the programmer.

[That's probably why there is still need for calculus dedicated
languages, since neither for float nor for integers, general purpose
languages guarantee a lot.]

Do people having worked with the compilers (Charles Forsythe for
example) can infirm/confirm or make the explanations more complete?

Cheers,
--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] Integer arithmetic: some lessons

[geoff]

If you think that shift operators aren't being translated
to shift instructions, you can examine the output of 8c -S.

x/2 is equal to x>>1 for non-negative integer x; for negative x,
the two expressions may yield different values, even if
x is a signed integer.  The book Hacker's Delight, among others,
explores these sorts of optimisations.

Re: [9fans] Integer arithmetic: some lessons

[tlaronde]

On Wed, Apr 21, 2010 at 11:03:06AM -0400, geoff@plan9.bell-labs.com wrote:
> If you think that shift operators aren't being translated
> to shift instructions, you can examine the output of 8c -S.
>
> x/2 is equal to x>>1 for non-negative integer x; for negative x,
> the two expressions may yield different values, even if
> x is a signed integer.  The book Hacker's Delight, among others,
> explores these sorts of optimisations.

Thanks for the reference. Having spent 3 days trying to understand
"generally" what was going on, I will now isolate one drawing that leads
to problem and add trace for gcc and for ken-cc to see where they do not
compute the same values. This will narrow the things and assembly, on
this, will give clues.
--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] Integer arithmetic: some lessons

[Bakul Shah]

On Wed, 21 Apr 2010 15:40:19 +0200 tlaronde@polynum.com  wrote:
> Hello,
>
> Still about integer arithmetic.
	...
> Conclusion (apparently): gcc always translate div involving power of two
> to binary manipulations, while (apparently) ken-cc does not.

gcc may choose to implement / with appropriate shifts and
what not but the result must be equivalent.  It certainly
can't replace %2 with >>1 for negative numbers.

Try this:

    int f(int x) { return x / 2; }
    int g(int x) { return x >> 1; }

    main(int argc, char** argv)
    {
	int x = argc > 1? atoi(argv[1]) : -7;
	printf("%d %d\n", -7/2, -7>>1);
	printf("%d %d\n", f(-7), g(-7));
	printf("%d %d\n", f(x), g(x));
    }

This will give you
    -3 -4
    -3 -4
    -3 -4
I don't have a way to test what kencc does but I would be
surprised if the result is any different....

>> is an arithmetic shift for signed numbers (the sign bit is
replicated).  The clearest way to see this is to compare

    -1/2 and -1>>1

The first gives you 0. The second gives you -1 (on twos
complement machines).

IIRC, Pascal's div operator behaves the same as C's / for
integers.  May be the problem is somehow related to mod?

> Conclusion: I will have to replace in METAFONT all div involving power
> of two to binary operations, since if I replace in some places and not
> in others, I wreak havoc the algorithms since computations are not done
> the same way for combined chunks.

Replacing div 2^N of a signed number by >>N seems like a mistake.

Re: [9fans] Integer arithmetic: some lessons

[tlaronde]

On Wed, Apr 21, 2010 at 04:28:52PM -0700, Bakul Shah wrote:
>
> > Conclusion: I will have to replace in METAFONT all div involving power
> > of two to binary operations, since if I replace in some places and not
> > in others, I wreak havoc the algorithms since computations are not done
> > the same way for combined chunks.
>
> Replacing div 2^N of a signed number by >>N seems like a mistake.

I know (by theory and by test) that for negative numbers:

1) There is no standard behavior;

2) The result is different with div and shift.

The problem is that in METAFONT, Knuth states explicitely that there may
be a problem depending on the way integers (negative integers) are
handled, but in a lot of the algorithms _floor_ is expected: shift gives
you floor, while div does not.

I have tested simply both gcc and ken-cc and they behave the same for
div. Hence, since for the whole program they do not behave the same (gcc
gives the expect result; on some draws (glyphes), ken-cc does not),
there is something going on.

D.E. Knuth is very precise and there are a lot of details. For example,
in some routines, he has called a variable: be_careful, because to avoid
an overflow, it has to be computed the way it is written, and the
compiler must not optimize (change the order of operation, doing an add
before a substract) => I have made so that this is translated to
"volatile int" since, in "Plan 9 C compilers" Ken Thompson specify that
they are "Arithmetic rewrites" (5.4) and that "volatile" is only handled
as "don't do any optimizations". I hope that "arithmetic rewrites" are
disabled too when "volatile" is set, since that may explain the erratic
result in border line (overflow) cases.

I have to search to find exactly what is going wrong and what is done,
to know whether there are no shifts but the algorithm expects "floor",
or there are other volatile expression, order dependant, that are
rewritten and should not.

Note: changing div by power of two some shifts, gcc still gives the same
results (and pass the test), while ken-cc still not, but do not behave
the same.
--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] Integer arithmetic: some lessons

[Steve Simon]

> This will give you
>     -3 -4
>     -3 -4
>     -3 -4
> I don't have a way to test what kencc does but I would be
> surprised if the result is any different....

FWIW 8c gives the same answer.

-Steve