English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Comparison of OCaml and MLton for numerics
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2007-05-31 (05:50)
From: Yuanchen Zhu <yzhu@f...>
Subject: Comparison of OCaml and MLton for numerics

I've been using Ocaml for implementing computer graphics algorithms.
One of the algorithms that I implemented was:

Li etal, "Compressing and Companding High Dynamic Range Images with
Subband Architectures"

For intellectual entertainment, I next converted the code to SML, and
got some interesting performance numbers on Ocaml and MLton. Since the
implementation is not a trivial micro benchmark, I thought I'd share
it with the group. I also have some questions regarding the future of

The most expensive part of the algorithm is image convolution. The
convolution kernel is separable, so the actual computation is done for
one horizontal/vertical strip at a time, i.e., it is 1-d convolution.

For rapid prototyping and easier maintenance, I used high-order
functions a lot in my code. For example, the horizontal convolution
routine looks something like the following:

let hconvolve kern (img:t) r =
  let ac y x s (kx, ky) = s +. ky *. getReflected img y (x + kx) 1.0 r in
    mapi (fun y x _ -> Array.fold_left (ac y x) 0.0 kern) img

Where the mapi function is basically a 2D version of Array.mapi.

The code is compiled using ocamlopt with arguments: -inline 4 -S
-ffast-math -unsafe. Next I translated the Caml code to Standard ML
and compiled using MLton with no additional arguments.

The performance numbers were as following:

Ocaml (unsafe) : user: 39.674s, real: 41.356s
MLton (safe):  user:  17.981s, real: 21.968s

Note that I didn't find an option that turns off array bound-checking
for MLton, so the MLton version is safe.

Clearly polymorphic function application in the inner-loop is killing
Ocaml. So I recoded the convolution function using for-loops. The code
is now much uglier:

let hconvolve kern (img:t) r =
  let sup = Array.length kern - 1 in
  let img' = create (size img) in
    for y = 0 to height img - 1 do
      for x = 0 to width img - 1 do
        let s = ref 0.0 in
          for i = 0 to sup do
            let (kx, ky) = kern.(i) in
              s := !s +. ky *. getReflected img y (x + kx) 1.0 r
          img'.(y).(x) <- !s;

The new running time is:

Ocaml (unsafe) : user: 21.477s, real: 23.366s

which is much in line with MLton:

MLton (safe):  user:  17.981s, real: 21.968s

Although note that the MLton version has array-bound check enabled and
used the two-line high order function version of hconvolve.

So the moral of the story: To use Ocaml for numerically intensive
work, code in C style in the inner loops.

This brings me to the next question: is there any plan to implement
type specialization optimization for ocamlopt? For numerics, this is
really crucial if you want write both in an elegant functional style
and get good performance. Also, I remember reading somewhere that the
current code base of Ocaml is ill-suited for implementing this kind of
optimization. May I ask what exactly needs to be done to the current
code base in order to support that? I have some compiler-writing
background and this sounds like an interesting project to work in my
past time.