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
}
Let's generate some test data to use.
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.
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.
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.
# 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.
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.
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.
# 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
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?"
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.
# 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:
let generate_people_array n =
Array.init n (fun i -> generate_person ())
As you can see, the performance gain here is tremendous.
# 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.
Top comments (0)