[Caml-list] OCaml optimization

[Caml-list] OCaml optimization

[Mark Hayden]

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

Below are two ways to write array summation in OCaml, sum0 and sum1.  Both of them use recursive functions.  ’sum0' allocates a closure on each call but I think is more natural.  ‘sum1’ does do any allocation, but is awkward to write.  Is there a compiler flag or other way to get the OCaml native compiler to avoid closure allocation in functions in the form of ‘sum0’?

best, Mark


Running each function 1000 times show sum0 is allocating 6 words on each call.

% ocamlopt -o loop0 -S -inline 10 -unsafe loop0.ml
./loop0
sum0:6029
sum1:23



open Printf ;;

(* Allocates
 *)
let sum0 a =
  let len = Array.length a in
  let rec loop ofs sum =
    if ofs < len then (
      loop (succ ofs) (sum + a.(ofs))
    ) else (
      sum
    )
  in
  loop 0 0
;;


let rec sum1_help a len ofs sum =
  if ofs < len then (
    sum1_help a len (succ ofs) (sum + a.(ofs))
  ) else (
    sum
  )
;;

(* Does not allocate
 *)
let sum1 a =
  let len = Array.length a in
  sum1_help a len 0 0
;;


let test which sum =
  let a = Array.make 123 123 in

  let minor0 = (Gc.stat ()).Gc.minor_words in
  
  for ofs = 0 to 1000 do
    ignore (sum a)
  done ;

  let minor1 = (Gc.stat ()).Gc.minor_words in

  printf "%s:%.0f\n" which (minor1 -. minor0) ;
;;

let _ =
  test "sum0" sum0 ;
  test "sum1" sum1 ;
;;







[-- Attachment #2: Type: text/html, Size: 5266 bytes --]

Re: [Caml-list] OCaml optimization

[Nicolas Ojeda Bar]

Dear Mark,

I would like to suggest a third way to write array summation which
1) avoids the closure allocations, 2) is very natural, and 3) does not require much cleverness from the compiler.

Additionally, this form plays well with the float unboxing heuristics in the compiler (in the case when you are adding floats):

let sum2 a =
  let s = ref 0 in
  for i = 0 to Array.length a - 1 do
    s := !s + a.(i)
  done;
  !s

Best wishes,
Nicolas

----- Original Message -----
From: "Mark Hayden" <markghayden@yahoo.com>
To: caml-list@inria.fr
Sent: Sunday, 29 November, 2015 7:16:57 PM
Subject: [Caml-list] OCaml optimization

Below are two ways to write array summation in OCaml, sum0 and sum1.  Both of them use recursive functions.  ’sum0' allocates a closure on each call but I think is more natural.  ‘sum1’ does do any allocation, but is awkward to write.  Is there a compiler flag or other way to get the OCaml native compiler to avoid closure allocation in functions in the form of ‘sum0’?

best, Mark


Running each function 1000 times show sum0 is allocating 6 words on each call.

% ocamlopt -o loop0 -S -inline 10 -unsafe loop0.ml
./loop0
sum0:6029
sum1:23



open Printf ;;

(* Allocates
 *)
let sum0 a =
  let len = Array.length a in
  let rec loop ofs sum =
    if ofs < len then (
      loop (succ ofs) (sum + a.(ofs))
    ) else (
      sum
    )
  in
  loop 0 0
;;


let rec sum1_help a len ofs sum =
  if ofs < len then (
    sum1_help a len (succ ofs) (sum + a.(ofs))
  ) else (
    sum
  )
;;

(* Does not allocate
 *)
let sum1 a =
  let len = Array.length a in
  sum1_help a len 0 0
;;


let test which sum =
  let a = Array.make 123 123 in

  let minor0 = (Gc.stat ()).Gc.minor_words in
  
  for ofs = 0 to 1000 do
    ignore (sum a)
  done ;

  let minor1 = (Gc.stat ()).Gc.minor_words in

  printf "%s:%.0f\n" which (minor1 -. minor0) ;
;;

let _ =
  test "sum0" sum0 ;
  test "sum1" sum1 ;
;;







-- 
Caml-list mailing list.  Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] OCaml optimization

[Mark Shinwell]

The forthcoming version of OCaml (4.03) with the flambda optimization
passes can compile the example "sum0" to code that does not allocate.
(The particular optimization that enables that probably won't be
enabled by default in 4.03, though.)

Mark

On 29 November 2015 at 18:16, Mark Hayden <markghayden@yahoo.com> wrote:
> Below are two ways to write array summation in OCaml, sum0 and sum1.  Both
> of them use recursive functions.  ’sum0' allocates a closure on each call
> but I think is more natural.  ‘sum1’ does do any allocation, but is awkward
> to write.  Is there a compiler flag or other way to get the OCaml native
> compiler to avoid closure allocation in functions in the form of ‘sum0’?
>
> best, Mark
>
>
> Running each function 1000 times show sum0 is allocating 6 words on each
> call.
>
> % ocamlopt -o loop0 -S -inline 10 -unsafe loop0.ml
> ./loop0
> sum0:6029
> sum1:23
>
>
>
> open Printf ;;
>
> (* Allocates
>  *)
> let sum0 a =
>   let len = Array.length a in
>   let rec loop ofs sum =
>     if ofs < len then (
>       loop (succ ofs) (sum + a.(ofs))
>     ) else (
>       sum
>     )
>   in
>   loop 0 0
> ;;
>
>
> let rec sum1_help a len ofs sum =
>   if ofs < len then (
>     sum1_help a len (succ ofs) (sum + a.(ofs))
>   ) else (
>     sum
>   )
> ;;
>
> (* Does not allocate
>  *)
> let sum1 a =
>   let len = Array.length a in
>   sum1_help a len 0 0
> ;;
>
>
> let test which sum =
>   let a = Array.make 123 123 in
>
>   let minor0 = (Gc.stat ()).Gc.minor_words in
>
>   for ofs = 0 to 1000 do
>     ignore (sum a)
>   done ;
>
>   let minor1 = (Gc.stat ()).Gc.minor_words in
>
>   printf "%s:%.0f\n" which (minor1 -. minor0) ;
> ;;
>
> let _ =
>   test "sum0" sum0 ;
>   test "sum1" sum1 ;
> ;;
>
>
>
>
>
>