DEV Community


Posted on • Originally published at

Efficient OCaml

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.

type height = {
  feet : int;
  inches : int

type person = {
  age : int;
  height : height;
  weight : int
Enter fullscreen mode Exit fullscreen mode

Let's generate some test data to use.

let generate_person () = {
  age = 99;
  height = {
    feet = 7;
    inches = 12
  weight = 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 []
Enter fullscreen mode Exit fullscreen mode

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

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
Enter fullscreen mode Exit fullscreen mode

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.

let dont_1 () =
  |> List.filter (fun p -> p.age >= 18)
  |> (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
Enter fullscreen mode Exit fullscreen mode

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.

# benchmark_1 ();;
- : float = 0.492262787773328825
Enter fullscreen mode Exit fullscreen mode

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.

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 () =
  |> (fun p -> p.height.feet * 12 + p.height.inches)
  |> average
Enter fullscreen mode Exit fullscreen mode

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.

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 :=
        |> (fun p -> p.height.feet * 12 + p.height.inches)
        |> average;
      recompute_average := false;
    else !cached_avg

let () = Height.set_data people

let do_2 () = Height.avg

let benchmark_2 () = timer 100 do_2 /. timer 100 dont_2
Enter fullscreen mode Exit fullscreen mode

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.

# benchmark_2 ();;
- : float = 3.17598111349897812e-05
Enter fullscreen mode Exit fullscreen mode

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

let rec fib1 n =
  if n = 1 || n = 2
  then 1
  else fib1 (n-1) + fib1 (n-2)
Enter fullscreen mode Exit fullscreen mode

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?"

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)
  if n = 1 || n = 2
  then 1
  else run ~acc:(1, 1) 3
Enter fullscreen mode Exit fullscreen mode

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

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

# timer 1 (fun () -> fib2 40);;
- : float = 6.198883056640625e-06
Enter fullscreen mode Exit fullscreen mode

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:

let generate_people_array n =
  Array.init n (fun i -> generate_person ())
Enter fullscreen mode Exit fullscreen mode

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

# benchmark_generate_people ();;
- : float = 46.0630876811840153
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)