[Caml-list] Array Optimizations

[Caml-list] Array Optimizations

[Christophe TROESTLER]

Hi all,

The following paper (that I found by chance)
http://www.cs.cornell.edu/Courses/cs612/2001SP/projects/ocaml-arrays/OCaml.pdf
describes a set of optimizations that improves array access speed in
Caml _without_loosing_bound_checking_ (contrarily to the -unsafe
option).  The performance gain on their examples looks good, in fact
they even beat gcc in some cases!  In their words:

	The final performance of MMM surpasses even that of the
	best-case baseline kernel --- the linearized 1D Array with
	bounds checking disabled --- yet without sacrificing the
	safety of bounds checking or requiring the programmer to
	linearize accesses.

and

	We conclude that OCaml could be a serious contender against
	languages such as C and Fortran for use in numerically
	intensive computation.

Is there anything like that (to be) implemented into the OCaml
compilers?  I believe many people besides myself will be interested to
have the power of Caml available with extremely good array access
times in loops.

Keep up with the good work!

Cheers,
ChriS


P.S.  As outlined in the paper, the Bigarray library is really slow
(much slower than the standard Array).  Given its (other)
capabilities, it is tempting to use it for numeric processing however.
Until this is solved, shouldn't there be a warning somewhere (in the
manual?).


Related links:
--------------

Array Data Dependence Analysis 
http://www.cs.umd.edu/projects/omega/sectionstar3_1.html

The Omega Project:
http://www.cs.umd.edu/projects/omega/

http://www.cs.cornell.edu/Courses/cs612/2001SP/projects/ocaml-arrays/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] Array Optimizations

[Thorsten Ohl]

Christophe TROESTLER writes:

> P.S.  As outlined in the paper, the Bigarray library is really slow
> (much slower than the standard Array).  Given its (other)
> capabilities, it is tempting to use it for numeric processing
> however.

I never noticed that Bigarray was so much slower, because I only
started to use it after standard Arrays outgrew my memory.  In this
case, the speedup from mapped Bigarrays relative to mildly thrashing
standard Arrays to was dramatic and masked the slowdown completely.

I didn't know that all accesses are going through the general
interface.   Inlining accesses in the native compiler for Arrays with
fixed dimensions could be a tremendous performance boost.

> Until this is solved,

I currently have a program that vitally depends on Bigarrays for
numeric processing.  The runtime is still on the order of hours and I
wouldn't want to rewrite it in Fortran anyway, but a factor 10 speedup
would be really cool :-).

Cheers,
-Thorsten

> The Omega Project:
> http://www.cs.umd.edu/projects/omega/

Darn, somebody used that name before ...
-- 
Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Array Optimizations

[Rolf Wester]

> Hi all,
> 
> The following paper (that I found by chance)
> http://www.cs.cornell.edu/Courses/cs612/2001SP/projects/ocaml-arrays/OCaml.pdf
> describes a set of optimizations that improves array access speed in
> Caml _without_loosing_bound_checking_ (contrarily to the -unsafe
> option).  The performance gain on their examples looks good, in fact
> they even beat gcc in some cases!  In their words:
> 
>  The final performance of MMM surpasses even that of the
>  best-case baseline kernel --- the linearized 1D Array with
>  bounds checking disabled --- yet without sacrificing the
>  safety of bounds checking or requiring the programmer to
>  linearize accesses.
> 
> and
> 
>  We conclude that OCaml could be a serious contender against
>  languages such as C and Fortran for use in numerically
>  intensive computation.
> 
> Is there anything like that (to be) implemented into the OCaml
> compilers?  I believe many people besides myself will be interested to
> have the power of Caml available with extremely good array access
> times in loops.
> 
> Keep up with the good work!
> 
> Cheers,
> ChriS
> 
> 
> P.S.  As outlined in the paper, the Bigarray library is really slow
> (much slower than the standard Array).  Given its (other)
> capabilities, it is tempting to use it for numeric processing however.
> Until this is solved, shouldn't there be a warning somewhere (in the
> manual?).
> 
I my experience with Array and Bigarray the difference isn't so significant
as it is in the above mentioned paper. Nevertheless I would very much 
appreciate Array and Bigarray perfomance comparable to C/C++. In that
case may be I could convince some of my colleagues to use OCaml for
their numerical work. Another approach could be to write a module comparable
to the Python Numpy package. In any case complex numbers in Bigarray
would be fine. 

Rolf Wester

P.S.: At the moment I write a wrapper for interfacing with a subset of FFTW.
I use Bigarray float64 as a complex array with re(i) = v.{2*i} and im(i)=v.{2*i+1}.
Does anybody have a better idea? 

-------------------------------------
Rolf Wester
rolf.wester@ilt.fraunhofer.de
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Array Optimizations

[David McClain]

> P.S.: At the moment I write a wrapper for interfacing with a subset of
FFTW.
> I use Bigarray float64 as a complex array with re(i) = v.{2*i} and
im(i)=v.{2*i+1}.
> Does anybody have a better idea?

FWIW, some time ago (a couple of years perhaps) I was faced with this
decision, and more, in terms of interfacing to foreign numeric code and
Matlab. As it happens, Matlab likes to allocate complex arrays as separate
arrays of real and imaginary components. That may simplify some of their
numeric coding, but I found that on PII and PIII architectures, the
performance suffers tremendously due to cache thrashing. Better to use
adjacent real and imaginary components.

When I did the adjacent real and imaginary components, I did it just like
you ask about above. What I find is that the OCaml performance, even with
this doubling and offset by one, indexing is quite good. Especially
important is to precompute these indices in the event of several array
accesses inside of "for" loops. That helps enormously. My OCaml speeds
indicate performance better than C/C++ coded internals in languages like
RSI/IDL, by almost 2x. One can only wonder about the quality of the C/C++
code against which I was comparing -- that was out of my control.

- David McClain
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr