This post is a continuation of the my last post . I did some benchmarking for recursive and non-recursive version of sum function.
open Unix
(* Tail recursive version *)
let min_list_tail lst =
let rec min_tail lst acc =
match lst with
| [] -> acc
| h :: t -> min_tail t (if h < acc then h else acc)
in
match lst with
| [] -> failwith "Empty list"
| h :: t -> min_tail t h
(* Non-tail recursive version *)
let rec min_list_non_tail = function
| [] -> failwith "Empty list"
| [x] -> x
| h :: t ->
let min_tail = min_list_non_tail t in
if h < min_tail then h else min_tail
let generate_large_list size =
List.init size (fun _ -> Random.int 1000000)
(* Benchmarking *)
let benchmark f name lst =
let start_time = gettimeofday () in
let result = f lst in
let end_time = gettimeofday () in
Printf.printf "%s: Time taken = %f seconds, Result = %d\n"
name (end_time -. start_time) result
(* Main benchmarking *)
let () =
Random.self_init ();
let sizes = [100000; 500000; 1000000] in
List.iter (fun size ->
Printf.printf "\nBenchmarking with list size %d\n" size;
let lst = generate_large_list size in
benchmark min_list_tail "Tail recursive" lst;
benchmark min_list_non_tail "Non-tail recursive" lst
) sizes
The code itself is pretty straightforward. It uses built-in Unix.gettimeofday(). This bechmark isn’t exactly ‘scientific’ and just meant to demonstrate the difference between tail-recursive and non tail-recursive versions of the same function.
Results:
I’m running MacBook Pro M1 16 GB and here are the results:
Benchmarking with list size 100000
Tail recursive: Time taken = 0.001656 seconds, Result = 0
Non-tail recursive: Time taken = 0.004719 seconds, Result = 0
Benchmarking with list size 500000
Tail recursive: Time taken = 0.006092 seconds, Result = 0
Non-tail recursive: Time taken = 0.019158 seconds, Result = 0
Benchmarking with list size 1000000
Tail recursive: Time taken = 0.012315 seconds, Result = 0
Non-tail recursive: Time taken = 0.030339 seconds, Result = 0
Summary:
The tail recursive version consistently outperformed the non-tail recursive version across all list sizes.
- For a list of 100,000 elements:
Tail recursive: 0.002 seconds Non-tail recursive: 0.005 seconds The tail recursive version was about 2.8 times faster.
- For a list of 500,000 elements:
Tail recursive: 0.006 seconds Non-tail recursive: 0.019 seconds The tail recursive version was about 3.1 times faster.
- For a list of 1,000,000 elements:
Tail recursive: 0.012 seconds Non-tail recursive: 0.030 seconds The tail recursive version was about 2.5 times faster.
The performance gap between the two versions widened as the list size increased, demonstrating the scalability advantage of tail recursion. Both versions found the minimum value correctly (0 in all cases, likely due to how the test data was generated).
In conclusion, this benchmark clearly shows the performance benefits of using tail recursion, especially for operations on large data sets in OCaml.