ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[Gurr, David (MED, self)]

> From: Travis Bemann:
> On Mon, Jul 29, 2002 at 10:13:24AM +0200, Nicolas Cannasse wrote:
> > > I agree that the C interface is pretty nice. However,
> > > how do would you use SIMD math instructions on the
> > > x86? Would you always call C-routines just to make use
> > > of SIMD or multimedia-instructions? What is the
> > > overhead for calling a function that is executing a
> > > few assembly instructions? Is it even possible to
> > > create a solid division line between "low-level" and
> > > "high-level" code?
> >
> > Yes it is.
> > Actually if you need to perform alot of SIMD instructions each frame
> > (involving zounds of C calls), you can try to group them in 
> one-C-call that
> > will do the job in one time. That's matter of architecture 
> and choices...
> > not always obvious :)
> 
> Note that most C or C++ compilers won't do this either, with the
> exception of some specialized vector parallelizing compilers (such as
> those used to compile code on vector supercomputers).  If you really
> need SIMD instructions, you'd probably need to hand-code it in
> assembly, no matter what language you're using.

IMHO:

High performance numerical code esp using SIMD or multiprocessor is
beyond the reach of hand written assembly or hand written C.  Very
heavy template based C++ almost works but odds are you will run into
C++ compiler bugs.  The best thing known at the present are special
purpose optimizing compilers.  The best known of these is fftgen, the
compiler that underlies FFTW and it is written in ocaml.  Others like
it are Atlas and Spiral.  Of special note is a versions of FFTW that
generates SIMD code for AMD Athlons:
http://www.complang.tuwien.ac.at/skral/fftwgel.html
Perhaps Dr Kral could explain more about fftwgel and the merits of
writting 
high performance code using ocaml.

About memory allocation, real time code should not be doing memory
allocation in the real time section.  For many things that you need
to do in realtime, the ocaml code does not allocate so allocation
is not issue.  If you need allocation control, write a C allocator.
You lose some of the safety of ocaml but it is better than writting
the whole thing in C.  And there is the possiblity of GC-free functional
programming as done in MLKit4.  This is SML not ocaml.  I would imagine
that the technique could be used in ocaml.

-D 
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[Travis Bemann]

[-- Attachment #1: Type: text/plain, Size: 3618 bytes --]

On Tue, Jul 30, 2002 at 12:58:02PM -0500, Gurr, David (MED, self) wrote:
> 
> 
> 
> > From: Travis Bemann:
> > On Mon, Jul 29, 2002 at 10:13:24AM +0200, Nicolas Cannasse wrote:
> > > > I agree that the C interface is pretty nice. However,
> > > > how do would you use SIMD math instructions on the
> > > > x86? Would you always call C-routines just to make use
> > > > of SIMD or multimedia-instructions? What is the
> > > > overhead for calling a function that is executing a
> > > > few assembly instructions? Is it even possible to
> > > > create a solid division line between "low-level" and
> > > > "high-level" code?
> > >
> > > Yes it is.
> > > Actually if you need to perform alot of SIMD instructions each frame
> > > (involving zounds of C calls), you can try to group them in 
> > one-C-call that
> > > will do the job in one time. That's matter of architecture 
> > and choices...
> > > not always obvious :)
> > 
> > Note that most C or C++ compilers won't do this either, with the
> > exception of some specialized vector parallelizing compilers (such as
> > those used to compile code on vector supercomputers).  If you really
> > need SIMD instructions, you'd probably need to hand-code it in
> > assembly, no matter what language you're using.
> 
> About memory allocation, real time code should not be doing memory
> allocation in the real time section.  For many things that you need
> to do in realtime, the ocaml code does not allocate so allocation
> is not issue.  If you need allocation control, write a C allocator.
> You lose some of the safety of ocaml but it is better than writting
> the whole thing in C.  And there is the possiblity of GC-free functional
> programming as done in MLKit4.  This is SML not ocaml.  I would imagine
> that the technique could be used in ocaml.

Note that there is no such thing as a C allocator in OCaml, even
though you can have "custom blocks" that have custom C finalization
code (and which are also not looked inside by OCaml itself).  In OCaml
there's three classes of allocated data structures - small blocks,
large blocks, and custom blocks, all of which are handled differently
by the OCaml garbage collector; also note that custom blocks have data
on non-heap resources which is used to influence the garbage collector
in how often it garbage collects such blocks.

Note that overall, the OCaml garbage collector is a incremental
generational garbage collector, with only *two* generations - new
blocks and old blocks.  The garbage collector only tries to
aggressively garbage collect new blocks, and does not necessarily try
to do all garbage collection at once, which is useful for realtime
performance.

However, there is one thing that particularly disturbs me about OCaml
- the way that it handles floating point values.  In OCaml a floating
point value is always 64 bit, and because only values that are always
the size of a machine word internally are not allocated, floating
point values in OCaml are ALWAYS allocated on the heap!!  Even though
benchmarks of OCaml seem to say that it is pretty damn fast, this
particular aspect keeps me up at night.  I at least hope OCaml has
something like a specialized internal heap for ONLY floating point
values that would keep floating point computations from being horridly
slow...

-- 
Yes, I know my enemies.
They're the teachers who tell me to fight me.
Compromise, conformity, assimilation, submission, ignorance,
hypocrisy, brutality, the elite.
All of which are American dreams.

              - Rage Against The Machine

[-- Attachment #2: Type: application/pgp-signature, Size: 2767 bytes --]

Re: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[Xavier Leroy]

> However, there is one thing that particularly disturbs me about OCaml
> - the way that it handles floating point values.  In OCaml a floating
> point value is always 64 bit, and because only values that are always
> the size of a machine word internally are not allocated, floating
> point values in OCaml are ALWAYS allocated on the heap!!

"Often", but not "always".  Detailed explanations on float boxing are
available here:
        http://caml.inria.fr/ocaml/numerical.html

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[Noel Welsh]

--- "Gurr, David (MED, self)" <David.Gurr@med.ge.com>
wrote:

> IMHO:
> 
> High performance numerical code esp using SIMD or
> multiprocessor is
> beyond the reach of hand written assembly or hand
> written C.  Very
> heavy template based C++ almost works but odds are
> you will run into
> C++ compiler bugs.

There are a least two parallelising C compilers for
the PC: Intel's and CodePlay's.  CodePlay say they do
a better job than Intel.  I imagine Intel hold a
differing opinion.

I'm interested in knowing the deficiencies of these
compilers.  I imagine they run into problems with
dependency analysis on complicated array expressions. 
Similarly, I'm interested in knowing in what areas HPF
and SAC are performant.  It appears to me that a
functional language (where dependency analysis is
simple) with array shape inference should be capable
of creating very array fast code is almost all
situations (and the SAC benchmarks show them beating
HPF).

Cheers,
Noel



__________________________________________________
Do You Yahoo!?
Yahoo! Health - Feel better, live better
http://health.yahoo.com
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[John Max Skaller]

Gurr, David (MED, self) wrote:

>About memory allocation, real time code should not be doing memory
>allocation in the real time section.  
>
Huh? Which parts of a real time interactive game aren't real time??
The whole thing, from gameplay interaction to graphics and sound,
must be done in 'real-time'.

Note that almost no game companies have the faintest idea how
to do real time programming. So it isn't clear worrying about
lag from garbage collection is even an issue. when they can't even
get basic real time operation right. Of course, it doesn't help
when you have to program for an OS not designed to support
real time operations other than basic IO.

Frankly, Ocaml would improve games enormously by allowing
programmers to concentrate on what really matters: algorithms
and programmer structure.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[Damien Doligez]

>From: John Max Skaller <skaller@ozemail.com.au>

>Huh? Which parts of a real time interactive game aren't real time??
>The whole thing, from gameplay interaction to graphics and sound,
>must be done in 'real-time'.

I'd say no part of a real-time interactive game is real-time.  To me,
real-time means something like the Ariane 5 rocket, where you have a
deadline every 36ms for the 12 hours of the mission.  And if you miss
even one deadline your 100M$ rocket will crash.

On the other hand, in something like Unreal Tournament, a half-second
freeze every 10 minutes is no big deal, and the users will not even
complain about it.

With Objective Caml on a fast machine, if you're not doing heap
compaction, GC pauses should be somewhere between 1 and 10
milliseconds.  Quite workable for an interactive game, I'd say, but
then again it's not the future of my company that is at stake.

-- Damien
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[John Max Skaller]

Damien Doligez wrote:

>>From: John Max Skaller <skaller@ozemail.com.au>
>>
>
>>Huh? Which parts of a real time interactive game aren't real time??
>>The whole thing, from gameplay interaction to graphics and sound,
>>must be done in 'real-time'.
>>
>
>I'd say no part of a real-time interactive game is real-time.  To me,
>real-time means something like the Ariane 5 rocket, where you have a
>deadline every 36ms for the 12 hours of the mission.  And if you miss
>even one deadline your 100M$ rocket will crash.
>
Heh! I suppose I have to agree. My Real Time work involved phase control 
lighting systems,
where timing is even tighter than your Ariane's 36ms. Surprisingly, 
switching phase controlled
lighing circuits require precision measured in microseconds -- a single 
machine extra instruction
on a 2Mhz microcontroller can turn an acceptable performance into an 
unacceptable one.

>With Objective Caml on a fast machine, if you're not doing heap
>compaction, GC pauses should be somewhere between 1 and 10
>milliseconds.  Quite workable for an interactive game, I'd say, but
>then again it's not the future of my company that is at stake.
>
Well, games like Diablo freeze for much longer than that: Baal's 
minions, 5-15 second lockup,
fighting Diablo with perspective on, on a 800Mhz machine: frame rate of 
1 frame per second
or worse with a lag of up to 5 seconds. ARGGG!!! Totally unacceptable: 
lag is responsible
for at least half the deaths on the internet servers.

As I commented in another post, Ocaml could only improve the quality of 
these games
by allowing the programmers to actually get the structure of the real time
operation right.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[Alexander V.Voinov]

Hi

There is a concept of 'soft realtime', where one can't ignore the
concept of 'deadlines', but the latter may not be that crucial. For
example, if a database transaction is not completed before such a
deadline, it's just rolled back and a failure is reported. This
failure may not be as disastrous as in the case of a spacecraft, but
you have to face it and process properly at a higher level. This is
very different to an 'ordinary' situation where you don't care at all
how much time it takes to complete the transaction.

If there was a version of OCaml (or a runtime switch) to impose such a
'transaction deadline' on the workings of GC, OCaml would be quite
acceptable for soft realtime.

Alexander

From: John Max Skaller <skaller@ozemail.com.au>
Subject: Re: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.
Date: Fri, 02 Aug 2002 02:38:35 +1000

> Damien Doligez wrote:
> 
> >>From: John Max Skaller <skaller@ozemail.com.au>
> >>
> >
> >>Huh? Which parts of a real time interactive game aren't real time??
> >>The whole thing, from gameplay interaction to graphics and sound,
> >>must be done in 'real-time'.
> >>
> >
> >I'd say no part of a real-time interactive game is real-time.  To me,
> >real-time means something like the Ariane 5 rocket, where you have a
> >deadline every 36ms for the 12 hours of the mission.  And if you miss
> >even one deadline your 100M$ rocket will crash.
> >
> Heh! I suppose I have to agree. My Real Time work involved phase control 
> lighting systems,
> where timing is even tighter than your Ariane's 36ms. Surprisingly, 
> switching phase controlled
> lighing circuits require precision measured in microseconds -- a single 
> machine extra instruction
> on a 2Mhz microcontroller can turn an acceptable performance into an 
> unacceptable one.
> 
> >With Objective Caml on a fast machine, if you're not doing heap
> >compaction, GC pauses should be somewhere between 1 and 10
> >milliseconds.  Quite workable for an interactive game, I'd say, but
> >then again it's not the future of my company that is at stake.
> >
> Well, games like Diablo freeze for much longer than that: Baal's 
> minions, 5-15 second lockup,
> fighting Diablo with perspective on, on a 800Mhz machine: frame rate of 
> 1 frame per second
> or worse with a lag of up to 5 seconds. ARGGG!!! Totally unacceptable: 
> lag is responsible
> for at least half the deaths on the internet servers.
> 
> As I commented in another post, Ocaml could only improve the quality of 
> these games
> by allowing the programmers to actually get the structure of the real time
> operation right.
> 
> -- 
> John Max Skaller, mailto:skaller@ozemail.com.au
> snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
> voice:61-2-9660-0850
> 
> 
> 
> 
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> 
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[Jonathan Coupe]

John Max Skaller <skaller@ozemail.com.au> wrote:


> >Huh? Which parts of a real time interactive game aren't real time??
> >The whole thing, from gameplay interaction to graphics and sound,
> >must be done in 'real-time'.

Actually, front end gui, persistence, and a lot of game logic and AI don't
have to be realtime (e.g. AI's don't have to do pathfinding instantly, they
can hesitate, amortize, etc.)

> Damien Doligez <damien.doligez@inria.fr>
>
> I'd say no part of a real-time interactive game is real-time.  To me,
> real-time means something like the Ariane 5 rocket, where you have a
> deadline every 36ms for the 12 hours of the mission.  And if you miss
> even one deadline your 100M$ rocket will crash.

Hence the terms soft and hard realtime. Games are the first.

> On the other hand, in something like Unreal Tournament, a half-second
> freeze every 10 minutes is no big deal, and the users will not even
> complain about it.

Many of them will. Lots of them will call the help line. Each time one does,
you've lost several dollars - typically the developer's profit per unit
profit margin or more.

Plus: if your product freezes, and the other guy's doesn't - you're toast.
Typically that means you've lost $1.4M-$3M of development money, but it
could be more. Then there's marketing, distribution, etc. And this is real,
not government, money. You need substantial advantage to make up for this
risk. Which is where this started.

- Jonathan



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[Gurr, David (MED, self)]

Noel Welsh:

> There are a least two parallelising C compilers for
> the PC: Intel's and CodePlay's.  CodePlay say they do
> a better job than Intel.  I imagine Intel hold a
> differing opinion.

But do they do a better job than fftwgel or Spiral
or Atlas?

> I'm interested in knowing the deficiencies of these
> compilers.  I imagine they run into problems with
> dependency analysis on complicated array expressions. 
> Similarly, I'm interested in knowing in what areas HPF
> and SAC are performant.  It appears to me that a
> functional language (where dependency analysis is
> simple) with array shape inference should be capable
> of creating very array fast code is almost all
> situations (and the SAC benchmarks show them beating
> HPF).

Is SAC available for public inspection?

> 
> Cheers,
> Noel
 
I have not used either compiler.  From the FFTW, Atlas, etc experience
the only way to get consistently high performance from a C compiler is
to do most of the work for the compiler and carefully feed it code that
it correctly optimizes.  This is a compiler and application specific
trial and error process.  FFTW does the optimization and scheduling for
the C compiler.  Once you do this, it is much less clear what
the value added of the C compiler is.  In particular, the amount of 
refinement that would be needed to get ocamlopt to match C compilers
at this task might be relatively small.  I have not read to code to
fftwgel but if fftwgel could be married to ocamlopt, they might well
produce code superior to intel or codeplay since C is notoriously
difficult to optimize even without SIMD.

-D
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: ocaml, simd, & fftwgel RE: [Caml-list] Caml productivity.

[Noel Welsh]

--- "Gurr, David (MED, self)" <David.Gurr@med.ge.com>
wrote:
> 
> But do they do a better job than fftwgel or Spiral
> or Atlas?

I have no idea :)
 
> Is SAC available for public inspection?

Yeah: http://www.informatik.uni-kiel.de/~sacbase/

I couldn't find a paper that describes how ATLAS is
implemented. I'm guessing the most important
optimisations are blocking (dependant on the cache
size) and condensing consequetive array transversals.
SAC does both these optimisations.

> Once you do this, it is much less
> clear what
> the value added of the C compiler is.  In
> particular, the amount of 
> refinement that would be needed to get ocamlopt to
> match C compilers
> at this task might be relatively small ... since C
> is notoriously
> difficult to optimize even without SIMD.

Yeah, it is kinda ironic that C is famous for
generating such fast C.  The functional model (pure
functional code is essentially an SSA register
machine) is much closer to current hardware than the C
every-has-an-address/stack model.  So it should be
possible to get fast code out of a functional language
with less effort than C.  It is also a bit amusing,
and a bit sad, that Java and .Net both use a stack
model (it's like they want slow code!)

Noel

__________________________________________________
Do You Yahoo!?
Yahoo! Health - Feel better, live better
http://health.yahoo.com
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners