[Caml-list] Re: yet another benchmark: List.map vs tail recursive map

[Christophe TROESTLER <debian00@tiscali.be>]

[-- Attachment #1: Type: Text/Plain, Size: 1499 bytes --]

On Wed, 4 Jun 2003, Stefano Zacchiroli <zack@bononia.it> wrote:
> 
> Surprisingly enough (for me) the tail recursive version of map seems
> to be a lot (6-7 times) faster than List.map when compiled in _bytecode_.

Not for small/medium lists (<= ~10000 elements).  For lists with
~100000 elements, the tail recursive version is indeed faster but
wthout something like OCAMLRUNPARAM="l=10M" the bytecode stack
overflows (as you said).

> When compiled in native code the tail recursive version seems to be a
> 60% slower than List.map.

I got the same figure for a list with 10000 elements (List.map ~60%
faster).  For a list with 100_000 elements, List.map is "only" ~30%
faster.  But then a "crazy" way to do it (see attached code) is ~10%
faster than List.map...  For really long lists (400000 elements),
List.map looses its advantage while the "crazy" way is a lot (> 50%)
faster than the tail rec function.

Given this, it rather seems that List.map is fine -- for if one really
wants speed, one will compile to native code and the bytecode version
performs well within the default limits.  Actually, the fact that the
documentation explicitely states that List.map is "Not tail-recursive"
should discourage its use for long lists which is good since faster
functions then exist (I suppose the cost of memory allocation then
dominates but I haven't measured this).  Now, if you want to "map" a
lot of elements, it seems you are better off with datastructures other
than lists...

Regards,
ChriS

[-- Attachment #2: map.ml --]
[-- Type: Text/Plain, Size: 829 bytes --]

(* You need the Benchmark module
   (http://www.bagley.org/~doug/ocaml/benchmark/). *)

let map' f l =  (* tail recursive version of map *)
  let rec aux acc = function
    | [] -> List.rev acc
    | hd :: tl -> aux (f hd :: acc) tl
  in
  aux [] l


let map2 f l = (* Crazy way... *)
  Array.to_list(Array.map f (Array.of_list l))

let () =
  let f x = succ x in (* simple fun, so its cost should be unimportant *)
  let bench n =
    let l = Array.to_list (Array.init n (fun x -> x)) in
    Printf.printf ">>> LIST LENGTH = %i\n" n;
    let res = Benchmark.throughputN 20
                [("List.map", List.map f, l);
                 ("tail_rec", map' f, l);
                 ("crazy", map2 f, l)
                ] in
    Benchmark.tabulate res in

  bench 100;
  bench 1000;
  bench 10_000;
  bench 100_000;
  bench 400_000