Why Array.map is (quite) faster than tail-recursive map?

Question

I write my tail-recursive version of map_tail like this:

let map_tail f l =
  let rec map acc = function
    | [] -> List.rev acc
    | hd::tl -> map (f hd :: acc) tl
  in 
  map [] l

And then an array based map_by_array:

let map_by_array f l =
  Array.of_list l |> Array.map f |> Array.to_list

---

Here is the benchmark code

let ran_list n =
  Random.self_init();
  let rec generate acc i =
    if i = n then acc
    else generate (Random.int 5::acc) (i+1)
  in 
  generate [] 0

let _ =
  let l = ran_list 10000000 in
  let f x = x+1 in
  let t1 = Sys.time() in
  let l1 = map_tail f l in
  let t2 = Sys.time() in
  let l2 = map_by_array f l in
  let t3 = Sys.time() in
  Printf.printf "map_tail: %f sec\nmap_by_array: %f sec\n" (t3-.t2) (t2-.t1)

---

I found that the array based map is faster, which surprises me a bit.

In map_tail, it traversals the list twice while map_by_array traversals list three times, why it is still faster?

Answer 1

It probably depends on the size of the list.

On long lists of size N, map_tail will do 2*N allocations (N during the map, and then N for List.rev), while map_by_array will do N+2 allocations (1 for the Array.of_list, 1 for Array.map and N for Array.to_list, that, actually, could be optimized to do only one allocation too).

Since allocations are probably the most expensive operations in this code, this difference should explain the difference of performance.