OCaml Optimization Techniques

Question

I am new to OCaml (with some prior knowledge in Haskell). And I want to persuade myself to adopt OCaml. Therefore I tried to compare the performance between C and OCaml. I wrote the following naïve Monte Carlo Pi-finder:

C Version

#include <stdio.h>
#include <stdlib.h>

int main(int argc, const char * argv[]) {

    const int N = 10000000;
    const int M = 10000000;

    int count = 0;
    for (int i = 0; i < N; i++) {
        double x = (double)(random() % (2 * M + 1) - M) / (double)(M);
        double y = (double)(random() % (2 * M + 1) - M) / (double)(M);
        if (x * x + y * y <= 1) {
            count++;
        }
    }

    double pi_approx = 4.0 * (double)(count) / (double)(N);
    printf("pi .= %f", pi_approx);
    return 0;
}

Ocaml Version

let findPi m n = 
    let rec countPi count = function 
        | 0 -> count
        | n ->
            let x = float_of_int (Random.int (2 * m + 1) - m) /. (float_of_int m) in
            let y = float_of_int (Random.int (2 * m + 1) - m) /. (float_of_int m) in
            if x *. x +. y *. y <= 1. then
                countPi (count + 1) (n - 1)
            else
                countPi count (n - 1) in
    4.0 *. (float_of_int (countPi 0 n)) /. (float_of_int n);;

let n = 10000000 in
let m = 10000000 in

let pi_approx = findPi m n in
Printf.printf "pi .= %f" pi_approx

I compiled the C with Clang (Apple LLVM version 5.1) and the OCaml with ocamlopt v4.01.0.

The running time of C is 0.105s. The OCaml one is 0.945s, which is 9 times slower. My target is to reduce the running time of OCaml by 3 times, so that the program can finish within 0.315s.

As I am so new to OCaml, I want to learn some OCaml optimization techniques. Please leave me some suggestions! (Tail-recursion is already applied, or the program will crash with stackoverflow)

Answer 1

Here's what I see if I use the same random number generator in both tests.

Here's a stub for calling random() from OCaml:

#include <stdlib.h>

#include <caml/mlvalues.h>

value crandom(value v)
{
    return Val_int(random());
}

Here's the modified OCaml code:

external crandom : unit -> int = "crandom"

let findPi m n =
    let rec countPi count = function
        | 0 -> count
        | n ->
            let x = float_of_int (crandom () mod (2 * m + 1) - m) /. (float_of_int m) in
            let y = float_of_int (crandom () mod (2 * m + 1) - m) /. (float_of_int m) in
            if x *. x +. y *. y <= 1. then
                countPi (count + 1) (n - 1)
            else
                countPi count (n - 1) in
    4.0 *. (float_of_int (countPi 0 n)) /. (float_of_int n);;

let n = 10000000 in
let m = 10000000 in

let pi_approx = findPi m n in
Printf.printf "pi .= %f" pi_approx

I also copied your C code unchanged.

Here's a session showing the two programs on my Mac (2.3 GHz Intel Core i7):

$ time findpic
pi .= 3.140129
real    0m0.346s
user    0m0.343s
sys     0m0.002s
$ time findpic
pi .= 3.140129
real    0m0.342s
user    0m0.340s
sys     0m0.001s
$ time findpiml
pi .= 3.140129
real    0m0.396s
user    0m0.394s
sys     0m0.002s
$ time findpiml
pi .= 3.140129
real    0m0.395s
user    0m0.393s
sys     0m0.002s

It looks like the OCaml code is around 15% slower.

I didn't try to make it faster at all, I just replaced the random number generator with the one that the C code is using.

Your code actually seems pretty hard to improve (i.e., it's good code).

Edit

(I rewrote the stub to make it faster.)