single-precision floats, etc.

single-precision floats, etc.

[Chris Hecker]

[je ne parle pas francais...I think that's how you say it! :)]

Hi, I'm looking into the feasibility of using Caml for some high-performance numerically intensive video game stuff, and I had a couple questions:

Most importantly, is there any way to make the "float" type compile to single precision floating point numbers?  I looked briefly at the compiler source, but I didn't see the obvious "#define FLOAT_TYPE double" anywhere.  All of the asm generators seem to have 8 byte floats hard coded in to them.  The best thing would be to have a float32 built in type so I could still use doubles when necessary (rarely), but in lieu of that, just switching the float type to single precision when I compiled the compiler would be fine.  Has anybody looked at doing this, and/or do the compiler authors have any idea how hard this would be?  How hard-coded are doubles into the compiler?

Another question, which is not as important, was the size limitation on arrays.  The biggest float array one can have is around 699000 elements.  That's pretty small on today's machines.  I know there are bigarray packages, but from looking at the comments, it's unclear to me how well they're integrated.  It also looks like the accessor functions, because they're external, would be function calls and not inlined, which would hurt any inner loop doing math on the array.  Is the size limitation fixed, or is there any chance of increasing it?

Finally, why aren't simple arrays of ints unboxed, like the arrays of floats?  Would that be a hard change to make as well?

Thanks for a cool language, and I hope I can use it for games,
Chris

Re: single-precision floats, etc.

[Pierre.Boulet]

Hello Chris,

> Most importantly, is there any way to make the "float" type compile
> to single precision floating point numbers?
> ...
> Another question, which is not as important, was the size limitation
> on arrays. 
> ...
> Finally, why aren't simple arrays of ints unboxed, like the arrays
> of floats?  Would that be a hard change to make as well?

I think that maybe what you are looking for is the bigarray library
that appeared with ocaml 3.00. It provides unboxed arrays of float32,
float64 and many int variants without any size limitation... and with
the choice of Fortran or C layout. I have not yet tested it but I was
really pleased to see it because it means ocaml can now be used for
scientific computing also (as well as for games :-) ).


-- 
Pierre.Boulet@lifl.fr -  http://www.lifl.fr/~boulet

     In theory, practice and theory are the same, 
     but in practice they are different. -- Larry McVoy

Re: single-precision floats, etc.

[Chris Hecker]

>I think that maybe what you are looking for is the bigarray library
>that appeared with ocaml 3.00.

I looked at that, but I really wanted to do the actual operations in caml code, not in a library (if possible).  So, I'd like to write an LU decomposition routine in caml that's as fast as C code (or close enough), for example.  Going out to another language is inconvenient at best, compared to just writing down the code you want (like you would in C).

Chris

Re: single-precision floats, etc.

[Xavier Leroy]

> Hi, I'm looking into the feasibility of using Caml for some
> high-performance numerically intensive video game stuff, and I had a
> couple questions:

You might be interested in François Pessaux's OCamlDoom and OCamlQuake
programs, available and described at
        http://guinness.cs.stevens-tech.edu/~fpessaux/
OCamlDoom is a purely software-based renderer for "pseudo 3D" scenes
as found in Doom.  OCamlQuake is a renderer for more general 3D scenes
as found in Quake, using the Glide library to leverage the hardware
support provided by 3DFX Voodoo cards.  Both deliver very decent
performance.

> Most importantly, is there any way to make the "float" type compile
> to single precision floating point numbers?  I looked briefly at the
> compiler source, but I didn't see the obvious "#define FLOAT_TYPE
> double" anywhere.  All of the asm generators seem to have 8 byte
> floats hard coded in to them.  The best thing would be to have a
> float32 built in type so I could still use doubles when necessary
> (rarely), but in lieu of that, just switching the float type to
> single precision when I compiled the compiler would be fine.  Has
> anybody looked at doing this, and/or do the compiler authors have
> any idea how hard this would be?  How hard-coded are doubles into
> the compiler?

Double-precision floats are hard-coded in a number of places in the
OCaml implementation, such as the native-code generators, but also
parts of the run-time system (e.g. the serializer and deserializer).
Substituting single-precision floats everywhere is feasible, but a
major undertaking.

I'm curious to why you need single floats.  It's certainly not for
speed, because most processors nowadays do not compute over single
floats any faster than over double floats.  Indeed, they convert
single floats to double or extended precision at load time, and do
all their arithmetic in double or extended precision.

So, the only reason for using single floats is to reduce the size of
large arrays or matrices of floating-point numbers, and this dovetails
into your next question:

> Another question, which is not as important, was the size limitation
> on arrays.  The biggest float array one can have is around 699000
> elements.  That's pretty small on today's machines.  I know there
> are bigarray packages, but from looking at the comments, it's
> unclear to me how well they're integrated.  It also looks like the
> accessor functions, because they're external, would be function
> calls and not inlined, which would hurt any inner loop doing math on
> the array.  Is the size limitation fixed, or is there any chance of
> increasing it?

The size limit for float arrays is 2^21-1 elements for a 32-bit
processor, and 2^54-1 elements for a 64-bit processor.  This is due to
the representation of heap blocks in the OCaml runtime system, where
each block has a one-word header containing 8 bits of "tag", 2 bits
for GC use, and the remaining 22 (or 54) bits for the size in words of
the block.

If you need larger arrays of numerical types, then the Bigarray
library is exactly what you need.  Not only it supports arbitrarily
large arrays (by allocating the data part outside the Caml heap), but
it also supports arrays of single-precision floating-point numbers
in addition to double floats and various integer types, all stored as
compactly as possible.

Bigarray accesses are a bit slow under the bytecode interpreter, but
the native-code compiler is able to inline and specialize accesses to
bigarrays of dimensions 1, 2 and 3 when their type and layout are
statically known.  For instance, my FFT benchmark runs at about the
same speed (+/- 10%) when using 1-dimensional bigarrays of double
floats and when using regular "float arrays".  So, don't dismiss
bigarrays on performance grounds!

> Finally, why aren't simple arrays of ints unboxed, like the arrays
> of floats?  Would that be a hard change to make as well?

Integers (type "int") are not boxed, just tagged, so a special
treatment of "int array" wouldn't make a significant speed difference.

Hope this helps,

- Xavier Leroy

Re: single-precision floats, etc.

[Stephan Houben]

On Wed, 18 Oct 2000, Chris Hecker wrote:
> >I think that maybe what you are looking for is the bigarray library
> >that appeared with ocaml 3.00.
> 
> I looked at that, but I really wanted to do the actual operations in caml code, not in a library (if possible).  So, I'd like to write an LU decomposition routine in caml that's as fast as C code (or close enough), for example.  Going out to another language is inconvenient at best, compared to just writing down the code you want (like you would in C).

But even 32 bit floats cannot be represented as an unboxed ML value, since
you need at least 1 other bit to tell you that it's not a pointer. (Otherwise
the precise GC will get confused.) This could of course be remedied if
Caml switched to a conservative GC, but then GC performance would
go down the drain.

-- 
ir. Stephan H.M.J. Houben
tel. +31-40-2474358 / +31-40-2743497
e-mail: stephanh@win.tue.nl

Re: single-precision floats, etc.

[Xavier Leroy]

> >I think that maybe what you are looking for is the bigarray library
> >that appeared with ocaml 3.00.
> 
> I looked at that, but I really wanted to do the actual operations in
> caml code, not in a library (if possible).  So, I'd like to write an
> LU decomposition routine in caml that's as fast as C code (or close
> enough), for example.  Going out to another language is inconvenient
> at best, compared to just writing down the code you want (like you
> would in C).

I don't understand your point.  The bigarray library provides support
for large numerical arrays with the associated operations, but you
still write the code that use these arrays in Caml.  Indeed, the code
is almost the same as if you'd used the standard array type; you just
write b.{x} and b.{x,y} instead of a.(x) and a.(x).(y).

*You* are not "going out to another language"; the system might, in
order to implement some of the bigarray operations (and some of the
regular array operations as well!), but why should you care?

Now, it is true that one of the goals of the Bigarray library is to
facilitate interoperability with C and Fortran code: by having the
same array layout as these languages, arrays can be passed back and
forth without copying.  But you may ignore this aspect of the library
for now, and just use it in Caml for working with large, compact arrays
of numbers.

- Xavier Leroy

String.map ?

[Christophe Raffalli]

Why the function String.map (present in string.ml) is not exported in 
string.mli ?

It is usefull ! example (sorry for the height bits chars) :

let transform_char = function
    '!' -> ' '
  | 'é' -> 'e'
  | 'è' -> 'e'
  | 'ê' -> 'e'
  | 'ë' -> 'e'
  | 'à' -> 'a'
  | 'ä' -> 'a'
  | 'ù' -> 'u'
  | 'ü' -> 'u'
  | 'î' -> 'i'
  | 'ï' -> 'i'
  | 'ö' -> 'o'
  | c -> c

let transform_string = 
  String.map transform_char 


-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI

Re: single-precision floats, etc.

[Chris Hecker]

>OcamlDoom etc.

Yeah, I downloaded these a while back, but haven't taken a look yet.  I was happy to find them.  I will mostly be using the OpenGL bindings in my experiments.

> Indeed, the code
>is almost the same as if you'd used the standard array type; you just
>write b.{x} and b.{x,y} instead of a.(x) and a.(x).(y).

Oh, I didn't know about the alternate syntax!  Is that hacked directly into the compiler?  It's not possible to define that sort of thing in the language, is it (it's not in bigarray.mli)?  I also didn't know the functions were inlined from the library...that's key.  I thought bigarray was just a normal library, not a special case.  

Just curious, are any of the other libraries similarly special cased?  In other words, if I wanted to write the library myself without touching the compiler, which libraries in the standard set would I not be able to write?

Chris

Re: single-precision floats, etc.

[Charles Martin]

>I'm curious to why you need single floats.  It's certainly not for
>speed, because most processors nowadays do not compute over single

I would want single floats for space, not speed!  The history of video game 
development is a fight for space on a limited memory processor.  Single 
versus double is a factor of two in the space requirements for vertex data 
and etc.

I, too, am deeply interested in using FP for video game development.  I 
have seen far too many pages and pages of C/C++ code that could have been 
reduced to a few higher-order functions.  I went so far as to drop by ICFP 
in Montreal for a day this year to meet some of the Scheme/OCaml/ML 
implementors.

On the subject of GC, the GC pause times are the obvious first problem with 
FP in video game development, but the space overhead is important as 
well.  I was interested in the earlier thread on memory overhead for 
various GC schemes; Damien Doligez mentioned that OCaml has a 1.42 times 
overhead.  If your average data structure is three words (two-word pairs 
are half of most FP allocations, I recall reading somewhere), with the 
header word you are paying [(3+1)*1.42=5.68] almost a 90% space overhead.

So using double instead of single floats means that your game as a whole 
will require approximately twice as much space as a non-FP 
implementation.  Of course, you will gain since you (presumeably) won't 
have to engage in typical video game coding stunts like allocating large 
data structures at the maximum possible size used by the game, only to have 
the majority of levels or whatever only require half your allocation.  How 
it all balances out in the mix is an open question.

Re: String.map ?

[Anton Moscal]

On Thu, 19 Oct 2000, Christophe Raffalli wrote:

> Why the function String.map (present in string.ml) is not exported in 
> string.mli ?

More general question: why other Array and List function (such as 
Array.fold_xxx, Array.create, Array.init, Array.iter) not exists for
strings?

I think, all collections must have the same interfaces(whenever it
possible).

Regards, Anton

Re: single-precision floats, etc.

[Chris Hecker]

>I would want single floats for space, not speed!

On today's architectures, size == speed.  

Single precision is also still faster for things like divides, sqrts, and whatnot.  And, as someone mentioned, the SIMD instruction sets are single precision only (at least until Wilamette).  But yes, size is the biggest issue.  

I'm going to check out the Bigarray package and see how it performs, though.

Chris