Syracuse conjecture in OCaml

Question

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.

Answer 1

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.