Efficient OCaml
Tags: ocaml, efficiency, functional
Published: 2019-11-10 22:59:36

I am often asked if functional programming is inefficient. The truth is that like all programming paradigms, functional programming can be inefficient, but with a few rules of thumb you can keep your code performant, clean, readable, and functional. Here are a few simple examples of making functional code more efficient.

Before diving in, let's first setup some data to work with. We will work with people, and measure each person in age, height, and weight.

```ocaml
type height = {
  feet : int;
  inches : int
}

type person = {
  age : int;
  height : height;
  weight : int
}
```

Let's generate some test data to use.


```ocaml
let generate_person () = {
  age = Random.int 99;
  height = {
    feet = Random.int 7;
    inches = Random.int 12
  };
  weight = Random.int 250
}

let rec generate_people n acc =
  if List.length acc < n
  then generate_people n (generate_person () :: acc)
  else acc

let people = generate_people 10_000 []
```

Also, let's setup a simple function to benchmark efficiency gains for each rule.


```ocaml
let rec call_n_times ?(count = 0) n f =
  if count < n
  then (f (); call_n_times ~count:(count + 1) n f)
  else ()

let timer n f =
  let start_time = Unix.time () in
  call_n_times n f;
  let end_time = Unix.time () in
  end_time -. start_time
```

**Rule 1 - Don't mix filters and maps together in separate steps, combine them when possible.**

This will help with general performance of your code, and also looks much cleaner. In the first function **dont_1**, we first find all people who are 18 or older, and then calculate their height. We are iterating over the list twice, which is clearly not good.

In the second function **do_1**, we combine the filter and map into a single step. We then only append to the list **acc** if the person is 18 or older.


```ocaml
let dont_1 () =
  people
  |> List.filter (fun p -> p.age >= 18)
  |> List.map (fun p -> p.height.feet * 12 + p.height.inches)

let do_1 () =
  List.fold_left (fun acc p ->
    if p.age >= 18
    then p.height.feet * 12 + p.height.inches :: acc
    else acc
  ) [] people

let benchmark_1 () = timer 10_000 do_1 /. timer 10_000 dont_1
```

The performance gains between the two functions are large - the fold version only takes 49% of the time that the filter + map version takes, which is exactly what we would expect if we iterate over one list instead of two.


```ocaml
# benchmark_1 ();;
- : float = 0.492262787773328825
```

**Rule 1.1 - Combine multiple maps into a single function for speed & cleanliness**

This is really just a subset of rule 1, but will make your code much cleaner to read, and also more performant.

**Rule 2 - Use modules to cache data and avoid re-running the same calculation**

Assume that you want to calculate the average height of your population. A quick but naieve way to achieve this is to build a function that will be called each time you want to compute the average. This works, but is drastically less efficient than using a module to cache your population data and average height, then only re-computing the average height when necessary.

Here is a quick way to implement the average height calculation. You can calculate the average by calling **dont_2**.


```ocaml
let sum =
  List.fold_left (fun acc x -> x + acc) 0

let average (l : int list) =
  (float_of_int @@ sum l) /. (float_of_int @@ List.length l)

let dont_2 () =
  people
  |> List.map (fun p -> p.height.feet * 12 + p.height.inches)
  |> average
```

A much more efficient way to calculate the population average is to create a module that will hold a list of people with their average height, and only calculate the average height of the list of people if the list of people changes.


```ocaml
module Height : sig
  val avg : float
  val set_data : person list -> unit
end = struct
  let data = ref []
  let recompute_average = ref true
  let cached_avg = ref 0.0
  let set_data new_data =
    data := new_data;
    recompute_average := true
  let avg =
    if !recompute_average
    then (
      cached_avg :=
        people
        |> List.map (fun p -> p.height.feet * 12 + p.height.inches)
        |> average;
      recompute_average := false;
      !cached_avg
    )
    else !cached_avg
end

let () = Height.set_data people

let do_2 () = Height.avg

let benchmark_2 () = timer 100 do_2 /. timer 100 dont_2
```

The difference here is so extreme if you don't update the data that it's not even worth running the benchmark, but here it is anyway.


```ocaml
# benchmark_2 ();;
- : float = 3.17598111349897812e-05
```

**Rule 3 - Use an accumulator**

Building a Fibonacci Sequence is a classic interview question, I used to use it often in two stages.

First, as a softball warmup to set the tone of the interview and allow the candidate to ease into the interview and get comfortable before diving into more challenging topics, "Can you build a function to calculate the nth Fibonacci number?".

This is pretty easy, and should look something like this


```ocaml
let rec fib1 n =
  if n = 1 || n = 2
  then 1
  else fib1 (n-1) + fib1 (n-2)
```

This function works fine for small values of n, but really starts to slow down for n >= 40. So as a follow up, I would pose the question.

"Can you build this same function so that it is not susceptible to a stack overflow?"


```ocaml
let rec fib2 n =
  let rec run ~acc i =
    if i = n
    then fst acc + snd acc
    else run ~acc:(snd acc, fst acc + snd acc) (i + 1)
  in
  if n = 1 || n = 2
  then 1
  else run ~acc:(1, 1) 3
```

The function **fib2** works much better, and you can clearly see a performance difference if you compare the two implementations for n = 40.


```ocaml
# timer 1 (fun () -> fib1 40);;
- : float = 3.35294890403747559

# timer 1 (fun () -> fib2 40);;
- : float = 6.198883056640625e-06
```

**Rule 4 - Don't abuse lists**

The function we created above **generate_people** is a perfect example of this rule. If we are going to generate a sequence of people, we can use an array instead of a list and get a significant performance boost.

Building a function to generate an array of people is extremely simple:


```ocaml
let generate_people_array n =
  Array.init n (fun i -> generate_person ())
```

As you can see, the performance gain here is tremendous.


```ocaml
# benchmark_generate_people ();;
- : float = 46.0630876811840153
```

I hope that you find these quick examples useful. I think that these are some of the most common opportunities for performance gains that you will come across in functional programming on a daily basis.