let make_list n =
let rec iter i l =
if i < n then iter (succ i) (0 :: l)
else l
in
iter 0 []
;;

let test f lst =
let begin_time = Unix.gettimeofday () in
for i = 0 to 1000 - 1 do
f (fun x -> x + 1) lst
done;
let end_time = Unix.gettimeofday () in
end_time -. begin_time
;;

let _ =
let lst = make_list 1000 in
Printf.printf "map1 : %f\n" (test map1 lst);
Printf.printf "map2 : %f\n" (test map2 lst);
Printf.printf "map3 : %f\n" (test map3 lst);
;;

自分の環境 x86 Pen4 2.4CGHz での結果。
map1 : 0.194000
map2 : 0.209000
map3 : 0.298000

でも map1 は make_list 10000 にすると stackover flow で落ちる。