5
\$\begingroup\$

I am wondering how to optimize the following OCaml simple code.

#load "unix.cma";;
open Unix;;

let time f x =
    let start = Unix.gettimeofday ()
    in let res = f x
    in let stop = Unix.gettimeofday ()
    in let () = Printf.printf "Execution time: %fs\n%!" (stop -. start)
    in res ;;


let syracuse x =
    let rec aux x t =
        match x with
          1 -> t
          |x -> if x mod 2 = 0 then aux (x / 2) (t + 1) else aux (3 * x + 1) (t+1) in
     aux x 0 ;;

let syracuse2 x =
    let rec aux x t =
        if x = 1 then
            t
        else
            if x mod 2 = 0 then aux (x / 2) (t + 1) else aux (3 * x + 1) (t+1)
        in
     aux x 0 ;;


let rec iterate_over n f l  =
     if n = 0 then l else iterate_over (n-1) f ((f n)::l);;

let syracuses n = iterate_over n syracuse [];;
let syracuses2 n = iterate_over n syracuse2 [];;


(time syracuses 100000);;
(time syracuses2 100000);;

I made a first attempt replacing the match with with ifs but it slightly reduced the performance.

Execution time: 1.880309s
Execution time: 1.920133s

I tried to replace the t+1s by succ t but it did not bring anything. I think that there are some redundancies in the operations performed when calling mod 2 and dividing by 2 but I don't know how it can help.

\$\endgroup\$
6
\$\begingroup\$

Okay, so let's forget about syracuses2 because using ifs is indeed slower and let's stop depending on Unix which makes things less portable and slightly more difficult to compile.

let time f x =
    let t = Sys.time() in
    let fx = f x in
    Printf.printf "Execution time: %fs\n" (Sys.time() -. t);
    fx

let syracuse x =
    let rec aux x t =
        match x with
            | 1 -> t
            | x ->
                if x mod 2 = 0 then
                    aux (x / 2) (t + 1)
                else
                    aux (3 * x + 1) (t+1) in
     aux x 0

let rec iterate_over n f l =
     if n = 0 then l else iterate_over (n-1) f ((f n)::l)

let syracuses n = iterate_over n syracuse [] ;; 

time syracuses 100000 ;;

This takes 0.4s on my machine and 0.03s when compiled (ocamlopt syracuse.ml && ./a.out).

Keep in mind that integer arithmetic is about twice as slow as in C because integers in OCaml are tagged. Nothing we can do about this.

syracuse looks fine by itself but iterate_over is highly inefficient because you're computing the same values over and over again. Once you know that a given integer n ends up with a 1, you can remember this. This is called memoization:

open Printf

let time f x =
    let t = Sys.time() in
    let fx = f x in
    Printf.printf "Execution time: %fs\n" (Sys.time() -. t);
    fx

let syracuse n =
    let rec aux x t cache =
        if x < n && Array.get cache x <> 0 then
            Array.get cache x
        else
            match x with
                | 1 -> t
                | x ->
                    if x mod 2 = 0 then
                        aux (x / 2) (t + 1) cache
                    else
                        aux (3 * x + 1) (t + 1) cache in
    let cache = Array.init n (fun x -> 0) in
    for i = 1 to n-1 do
        Array.set cache i (aux i 0 cache)
    done ;;

time syracuse 100000 ;;

This takes 0.035s on my machine and 0.003s when compiled: a 10x speedup! This is a space-time tradeoff. Another optimization allows you get a k-speedup with a 2^k precomputation, but it might not play well with the cache.

Now, to get maximum performance, you probably want to get down to C, given the relative slowness of integer arithmetic in OCaml.

\$\endgroup\$
  • \$\begingroup\$ Thank you ! using the cache was indeed very efficient ! is there any generic implementation of caching in OCaml ? Something as simple as python cache decorators ? \$\endgroup\$ – RUser4512 Aug 26 '16 at 12:08
  • \$\begingroup\$ Sure. Try to write one yourself :) Such implementations usually use Hashtbl to be able to handle any value, while my implementation is specialized for integers where I'm going to fill most of the array. But maybe it would be just as fast with an hash table. \$\endgroup\$ – Quentin Pradet Aug 26 '16 at 12:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.