32 bit integers

32 bit integers

[Edwin Young]

Hi,

several people have been requesting features to be included in a
forthcoming O'Caml/O'Labl merge, so I thought I'd add a humble plea for
some support for untagged (presumably boxed) integers. I'm looking
mostly at camlidl, the documentation for which says: "Since the Caml int
type has one bit of tag, the conversion from IDL types int and long
loses the most significant bit on 32-bit platforms". I don't think
that's terribly satisfactory. If there isn't going to be a 32-bit type,
can anyone suggest a workaround (eg can I convince camlidl to map all
ints to floats)?

Thanks,

--
Edwin Young

Re: 32 bit integers

[Xavier Leroy]

> several people have been requesting features to be included in a
> forthcoming O'Caml/O'Labl merge, so I thought I'd add a humble plea for
> some support for untagged (presumably boxed) integers. I'm looking
> mostly at camlidl, the documentation for which says: "Since the Caml int
> type has one bit of tag, the conversion from IDL types int and long
> loses the most significant bit on 32-bit platforms". I don't think
> that's terribly satisfactory.

We all agree on that.  The "int" type will almost certainly remain
unboxed and tagged (i.e. with one fewer bits than the platform's
native integers) in the near future, but additional (boxed, untagged)
integer types are certainly important for foreign-function interface.

See for instance J.-C. Filliatre's "Int32" library,
http://www.lri.fr/~filliatr/ftp/ocaml/int32/
(although I object to the name of that library -- on an Alpha, it
implements 64-bit integers...)

> If there isn't going to be a 32-bit type,
> can anyone suggest a workaround (eg can I convince camlidl to map all
> ints to floats)?

I'm not sure you really want to do it for all ints.  But you can do it
on a function-per-function basis in at least two ways.  Consider a C
function

        int myfunc(int x)

where the two "int" need to be represented as floats in Caml.

The first way to do this is to cheat in the .idl file given to Camlidl:
just declare myfunc as

        double myfunc(double x)

and make sure that the generated C stub code knowns the real prototype
of "myfunc", either by including a header file or by putting an extra
prototype:

        quote(C, "#include <myfunc.h>")
or
        quote(C, "extern int myfunc(int x);")

Then, the stub code generated by Camlidl will treat the argument and
the result of "myfunc" as doubles, but the C compiler will insert the
required int<->double coercions in the actual call to "myfunc" in the
stub code.

The second, more general way is to define (using typedef in the .idl
file) a C type int32 synonymous for int, but represented in Caml as float:

  quote(C, "
    static value int32_c2ml(int * input)
    { return copy_double((double) (*input)); }
    static void int32_ml2c(value input, int * output)
    { *output = (int) Double_val(input); }
  ")

  typedef [mltype("float"),c2ml(int32_c2ml),ml2c(int32_ml2c)] int int32;

  int32 myfunc(int32 x);

This approach is more general in that you can use other Caml types
than float, e.g. Filliatre's Int32.t type.  Of course, you have to
provide manually the correct conversion functions (c2ml and ml2c).

Hope this helps,

- Xavier Leroy

Re: 32 bit integers

[Scott Alexander]

Unfortunately, the Int32 library can have bad performance implications.  When
we implemented SHA-1 (which pretty much assumes 32 bit ints), we originally
used Int32 because we wanted to have portability with either Alphas or
Pentiums.  Unfortunately, the performance was unacceptable.  For byte code,
using Int32, to SHA-1 4MB of data takes 86.4s on an Alpha whereas using (63
bit) ints on an Alpha takes only 36.0s.  (Using native code, the numbers are
62.0s versus 2.5s.)  Fortunately for us, we didn't care about the memory
overhead.

My guess was that much of this overhead is due to the fact that ints are
supported directly by the byte code interpreter rather than requiring a call
to a function.  Similarly, I'm guessing that the native code compiler is
using the add instruction instead of arranging a function call.

In any case, while the Int32 package did give us some way of coping with
Pentiums, it wasn't a full solution.

Scott

Re: 32 bit integers

[John Prevost]

Xavier Leroy <Xavier.Leroy@inria.fr> writes:

> See for instance J.-C. Filliatre's "Int32" library,
> http://www.lri.fr/~filliatr/ftp/ocaml/int32/
> (although I object to the name of that library -- on an Alpha, it
> implements 64-bit integers...)

I found this implementation to be terribly slow (even slower than the
bignum stuff in many cases.)  Any idea why this is?  Is it just
because of the extra dereference, or is it because the compiler uses
better code for "primitive" type operations like int addition than it
does for other types?  (This second was my guess.)  Is there any way
to make this kind of extension work better?

John.

Re: 32 bit integers

[Xavier Leroy]

> I found this implementation to be terribly slow (even slower than the
> bignum stuff in many cases.)  Any idea why this is?  Is it just
> because of the extra dereference, or is it because the compiler uses
> better code for "primitive" type operations like int addition than it
> does for other types?

Both, actually.  Boxing is always expensive, not so much because of
the extra dereference, but mostly because of the extra heap allocations.
(There are good reasons why the "int" type is tagged instead of boxed
in OCaml...)  On top of that, all operations on Int32.t are
implemented by C functions, and calling a C function from Caml is
expensive -- more expensive than calling a Caml function, and much
more expensive than open-coding the operations.

> (This second was my guess.)  Is there any way
> to make this kind of extension work better?

There is a way, but it involves modifying the compiler itself
to add special code generation rules for the primitive operations on
the new integer type.

- Xavier Leroy

RE: 32 bit integers

[Juergen Pfitzenmaier]

Xavier Leroy wrote:
> ........................... and calling a C function from Caml is
> expensive -- more expensive than calling a Caml function, and much
> more expensive than open-coding the operations.
>
> > (This second was my guess.)  Is there any way
> > to make this kind of extension work better?
>
> There is a way, but it involves modifying the compiler itself
> to add special code generation rules for the primitive operations on
> the new integer type.

I'm very much interested in adding this kind of special rules to
the compiler. Not for Int32 but for long integer and long floats.
Could you give me a pointer where to start work ?

ciao
pfitzen@informatik.uni-tuebingen

RE: 32 bit integers

[Manuel Fahndrich]

I've been using the Int32 bit library quite a bit in the last months and
although it is a workable solution to getting 32 bit quantities. However,
having used SML earlier in my life, I think providing native 32 bit (even if
boxed) quantities in the OCAML language is a must. Consider for example the
problem that I cannot write 32bit constants into the code. I have to
construct them via strings and a custom conversion function, or predefine
them in C. This makes the code more obscure than necessary.

I advocate introducing a primitive 'word' type which is the full machine
width, along with constants
(e.g. 0wxxxx as in SML) and operators. 

-Manuel


-----Original Message-----
From: Xavier Leroy [mailto:Xavier.Leroy@inria.fr]
Sent: Thursday, October 21, 1999 7:24 AM
To: Edwin Young; 'caml-list@inria.fr'
Subject: Re: 32 bit integers


> several people have been requesting features to be included in a
> forthcoming O'Caml/O'Labl merge, so I thought I'd add a humble plea for
> some support for untagged (presumably boxed) integers. I'm looking
> mostly at camlidl, the documentation for which says: "Since the Caml int
> type has one bit of tag, the conversion from IDL types int and long
> loses the most significant bit on 32-bit platforms". I don't think
> that's terribly satisfactory.

We all agree on that.  The "int" type will almost certainly remain
unboxed and tagged (i.e. with one fewer bits than the platform's
native integers) in the near future, but additional (boxed, untagged)
integer types are certainly important for foreign-function interface.

See for instance J.-C. Filliatre's "Int32" library,
http://www.lri.fr/~filliatr/ftp/ocaml/int32/
(although I object to the name of that library -- on an Alpha, it
implements 64-bit integers...)

> If there isn't going to be a 32-bit type,
> can anyone suggest a workaround (eg can I convince camlidl to map all
> ints to floats)?

I'm not sure you really want to do it for all ints.  But you can do it
on a function-per-function basis in at least two ways.  Consider a C
function

        int myfunc(int x)

where the two "int" need to be represented as floats in Caml.

The first way to do this is to cheat in the .idl file given to Camlidl:
just declare myfunc as

        double myfunc(double x)

and make sure that the generated C stub code knowns the real prototype
of "myfunc", either by including a header file or by putting an extra
prototype:

        quote(C, "#include <myfunc.h>")
or
        quote(C, "extern int myfunc(int x);")

Then, the stub code generated by Camlidl will treat the argument and
the result of "myfunc" as doubles, but the C compiler will insert the
required int<->double coercions in the actual call to "myfunc" in the
stub code.

The second, more general way is to define (using typedef in the .idl
file) a C type int32 synonymous for int, but represented in Caml as float:

  quote(C, "
    static value int32_c2ml(int * input)
    { return copy_double((double) (*input)); }
    static void int32_ml2c(value input, int * output)
    { *output = (int) Double_val(input); }
  ")

  typedef [mltype("float"),c2ml(int32_c2ml),ml2c(int32_ml2c)] int int32;

  int32 myfunc(int32 x);

This approach is more general in that you can use other Caml types
than float, e.g. Filliatre's Int32.t type.  Of course, you have to
provide manually the correct conversion functions (c2ml and ml2c).

Hope this helps,

- Xavier Leroy