On Wednesday 07 July 2004 15:58, Xavier Leroy wrote:
> ... In your "f" function, you asked for the
> construction of a pair, and you get that pair construction in
> ocamlopt's output.  If you didn't want the pair to be constructed, why
> did you write "f" this way?

Funny you should say that. I've only recently been trying my hand at such 
low-level optimisations in OCaml and, to my surprise, I'm terrible at it (no 
comments, please!).

Specifically, I recalled a post that ocamlopt doesn't do CSE. On the basis of 
this I thought that I could optimise my original code:

      let pivot = (first + last)/2 in
      let sum1=helper (scale+1) (2*entry) first pivot in
      let sum2=helper (scale+1) (2*entry+1) pivot last in
      Array.unsafe_set data2 entry (sum1 -. sum2);
      sum1 +. sum2

by performing some CSE manually, for example:

      let pivot = (first + last)/2 in
      let (sum1, sum2) =
        let scale=scale+1 and entry=2*entry in
        (helper scale entry first pivot, helper scale (entry+1) pivot last)
      in
      Array.unsafe_set data2 entry (sum1 -. sum2);
      sum1 +. sum2

I also tried applying part of the arguments to Array.set to avoid the creation 
of a pair:

      let pivot = (first + last)/2 in
      let set=Array.unsafe_set data2 entry in
      let scale=scale+1 and entry=2*entry in
      let sum1=helper scale entry first pivot in
      let sum2=helper scale (entry+1) pivot last in
      set (sum1 -. sum2);
      sum1 +. sum2

Contrary to my expectations, these revised versions are 30 and 70% slower than 
the original, respectively. In the first case, this is presumably because 
ocamlopt is building the pair which I asked for but don't want. In the second 
case, "set" appears to be very expensive to create and/or apply (forgive my 
avoiding the word "closure" - I'm still not confident that I know its precise 
meaning).

So, in order to optimise OCaml code in this much detail, I guess I need some 
quantifications of the relative costs of such "primitive" operations. Has 
anyone documented this and can anyone give me some hints?

From Evgeny Chukreev's post I'm guessing that constructing any data 
structures, even pairs, can be very costly because it invokes the GC which 
(always?) does a minor collection. Can partially applied functions be more 
efficient if they are applied many times?

(For anyone who's interested, bounds checking only slows this array-intensive 
code down by 9%)

Cheers,
Jon.

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