Re: single-precision floats, etc.

Re: single-precision floats, etc.

[ortmann]

Just curious ... would single-precision floats have been accurate enough
for the ICFP programming contest?

And how fast might they have been?

--
Daniel Ortmann, IBM Circuit Technology, Rochester, MN 55901-7829
ortmann@us.ibm.com / internal 8.553.6795 / external 507.253.6795
ortmann@isl.net home 507.288.7732

"The answers are so simple, and we all know where to look,
but it's easier just to avoid the question." -- Kansas




Chris Hecker <checker@d6.com>@inria.fr on 10/24/2000 10:22:20 PM

Sent by:  Pierre.Weis@inria.fr


To:   Charles Martin <martin@chasm.org>, caml-list@inria.fr
cc:
Subject:  Re: single-precision floats, etc.




>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

Re: single-precision floats, etc.

[Chris Hecker]

>Just curious ... would single-precision floats have been accurate enough
>for the ICFP programming contest?

Most numerical analysis texts point out that you rarely need double precision floating point numbers for accuracy or precision if your algorithm is properly constructed.  Range is a different matter, but I doubt the raytracer world was the size of the solar system.  For any reasonably ranged problem, singles are fine.  Of course, this is like saying 16 bit ints are fine because you can do most algorithms with them if you're careful.  Eventually doubles will replace singles because hey, more range and precision is better, and computers are fast and ram is cheap.  Still, we don't store strings as arrays of 32 bit numbers because a) we don't need to, and b) it's wasteful.  So, I'd assume singles will be around for a long time to come.  Do you really need better than 10e-6 accuracy (that's about unit roundoff for a single).

>And how fast might they have been?

I can't answer that (assuming you were asking me about this in the first place).  Multiplies and adds are the same speed on most CPUs, so cache effects would have been the governing variable here.

Chris

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

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: single-precision floats, etc.

[jean-marc alliot]

David Gurr wrote:

> > 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.
>
> Machines with multimedia instruction sets do compute over single floats
> faster than double floats when the single floats are packed into a 64 bit
> pair of singles or a 128 bit quad of singles.
>

Yes, but there are drawbacks:
1) you have to write anyway something in assembly language to easily get
down to this level. I concede that one (small) problem of ocaml is the fact
that external functions written in assembly or C can not be inlined. This is
mainly what I would ask Xavier to think about, but it is clearly a major
problem.
2) Performances get as high as 4 Gflops on a 1Ghz P-III, but it is only true
when you can have vectorizable code. It is usually not that easy to
vectorize an application, and one multiplication between 2 packed 4-float
vectors on a P-III is not faster than a multiplication between 2 doubles
(well, with the pipelining techniques on the P-III, many things depend on
what is before and after the instruction, but I am probably right on the
whole)
3) float are very often not enough in precision for many applications.


A demonstration of vectorization and precision problems are here :
http://www.recherche.enac.fr/~alliot/mand.html

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.

[David Gurr]

Xavier Leroy:
> 
> 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.

Substituting single floats for double float would be a chore (I tried
and gave up).  But on machines where doubles are 64 bits and a packed
pair of singles is 64 bits, how hard would it be to generalize float
to allow any of the 64 bit arithmetric types (ie double floats,
pairs of single floats, pairs of 32 bit longs, quads of 16 bit shorts,
etc)?  

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

Machines with multimedia instruction sets do compute over single floats 
faster than double floats when the single floats are packed into a 64 bit 
pair of singles or a 128 bit quad of singles.

> Indeed, they convert
> single floats to double or extended precision at load time, and do
> all their arithmetic in double or extended precision.

They dont do conversion for packed floats and twice as many singles 
fit into a cache as do doubles.  
 
-David Gurr

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

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]

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

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

[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]

>precision floats.  Instead of adding single precision floats, I
>wonder if I would rather replace boxed float with "boxed 
>multi-media datatype".

I guess I'd really like to be able to do as much in Caml as possible.  I could definitely write libraries in C for this, but it'd be really cool if Caml itself performed well enough that I didn't need to do that except in the most extreme cases.  I'm doing some simple performance tests now relative to C and I'll post the results when I'm done.

Chris

Re: single-precision floats, etc.

[Chris Hecker]

>I'd be worried about the GC pause times.  They're pretty short, but
>are they short enough for high-performance video game stuff ?

Not sure yet, since I haven't written a large program yet.  It looks like the Gc module gives you some control over this?  How bad does it get in real-sized apps?  A short pause is not bad if I can control when it happens (level load time, etc.).

>> 699000
>Where did you get that number from ?

Oops, sorry, that was (Sys.max_array_length / 2) / 3 for 3D vectors, I forgot that I'd divided by 3.  Anyway, what's the nature of the limitation?  That is, why can't I have an array the size of memory?  I assume you're using bits in the index or the pointer or something?

Any ideas as to how hard it would be to recompile the compiler to generate 32bit floats?

Chris

Re: single-precision floats, etc.

[Fermin Reig]

>From: Damien Doligez <Damien.Doligez@inria.fr>
>
>>From: Chris Hecker <checker@d6.com>
>
>>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:
>
>I'd be worried about the GC pause times.  They're pretty short, but
>are they short enough for high-performance video game stuff ?

I know of one game programming language that is garbage collected:
UnrealScript. It's used in the game Unreal, which a is Doom-style
game.

There's a langauge reference at
http://unreal.epicgames.com/unrealscript.htm (last updated Dec
1998). There, you can read:

     "Garbage collection: All objects and actors in Unreal are
     garbage-collected using a tree-following garbage collector
     similar to that of the Java VM."

Fermin Reig

Re: single-precision floats, etc.

[Remi VANICAT]

Damien Doligez <Damien.Doligez@inria.fr> writes:

> >From: Chris Hecker <checker@d6.com>
> 
> >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:
> 
> I'd be worried about the GC pause times.  They're pretty short, but
> are they short enough for high-performance video game stuff ?

with the caml incremental GC, They're realy pretty short. As far as i
know it, short enought to do realtime music, so i believe it's not
realy a problem for video game stuff.

of course, some test might be usefull.

Also, you may use lablgl, leting the hardware do much of the work.

-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat

Re: single-precision floats, etc.

[David Gurr]

Chris Hecker:
> Most importantly, is there any way to make the "float" type compile to single precision floating point numbers?  

I do mostly DSP stuff for MRI machines and most of the code is single
precision floats.  Instead of adding single precision floats, I
wonder if I would rather replace boxed float with "boxed 
multi-media datatype".  So in Proc and Arch for AltiVec machines the
float registers would be replaced by 128 bit "vector" registers
and float arrays would instead be arrays of 128 bit elements and the
float ops would be replaced by packed int and packed float ops.

On the other hand, most x86 machines have weird multimedia
instruction sets (using the MMX registers precludes using the 
floating point stack, clever).

I suppose that Cmm would be modified to either replace the
float ops with packed ops or extend the float ops with 
packed ops and Selection would do what it could with 
incomplete multimedia instruction sets.

-David Gurr

 

Re: single-precision floats, etc.

[Damien Doligez]

>From: Chris Hecker <checker@d6.com>

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

I'd be worried about the GC pause times.  They're pretty short, but
are they short enough for high-performance video game stuff ?


>Another question, which is not as important, was the size limitation
>on arrays.  The biggest float array one can have is around 699000
>elements.

Where did you get that number from ?  The maximum size of float arrays
is 2097152 elements on a 32-bit machine, and 9007199254740992 elements
on a 64-bit machine (assuming you have enough memory...)


>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 can't give a precise answer to this question, but already the
special treatment of float arrays imposes some overhead on all
polymorphic array operations.  I'm not sure how much worse it would
get with a second kind of special arrays.

-- Damien

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