caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* [Caml-list] yet another benchmark: List.map vs tail recursive map
@ 2003-06-04 12:00 Stefano Zacchiroli
  2003-06-04 15:13 ` [Caml-list] " Christophe TROESTLER
  2003-06-04 21:56 ` [Caml-list] " Brian Hurt
  0 siblings, 2 replies; 9+ messages in thread
From: Stefano Zacchiroli @ 2003-06-04 12:00 UTC (permalink / raw)
  To: Inria Ocaml Mailing List

[-- Attachment #1: Type: text/plain, Size: 1516 bytes --]

I've done some benchmarks comparing List.map implementation (not tail
recursive) and the following tail recursive map implementation (which do
an additional traversal on the list to reverse it):

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

[ Disclaimer: I will be very happy to discover that my benchmarks are
  wrong, the challange is to find _where_ the bug is ... ]

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_.

When compiled in native code the tail recursive version seems to be a
60% slower than List.map. The point is that the difference becomes
significative only if you use hundred of times map on short lists,
otherwise List.map segfaults (the bytecode version of the bench was
indeed performed augmenting stack size).

I'm now wondering: is worthwhile to have a List.map implementation
not tail recursive in the standard library? Can we consider to replace
it with a tail recursive implementation?

Benchmarks code and results attached, I'm using OCaml 3.06 and I've not
tried the same with the CVS version.

Cheers.

-- 
Stefano Zacchiroli  --  Master in Computer Science @ Uni. Bologna, Italy
zack@{cs.unibo.it,debian.org,bononia.it}  -  http://www.bononia.it/zack/
"  I know you believe you understood what you think I said, but I am not
sure you realize that what you heard is not what I meant!  " -- G.Romney

[-- Attachment #2: map_bench.txt --]
[-- Type: text/plain, Size: 1556 bytes --]


(* Source code for the bytecode benchmark: one single run on a long list *)

  let l = Array.to_list (Array.init 1000000 (fun x -> x)) in
  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
  in
  let f x = x * x in  (* yes ... it overflows ... who cares? *)
  let test_std () = List.map f l in
  let test_tail_rec () = map' f l in
  match Sys.argv.(1) with
  | "1" -> test_std ()
  | "2" -> test_tail_rec ()
  | a -> raise (Invalid_argument a)

(* Bytecode benchmark *)

  $ export OCAMLRUNPARAM="l=10M"

  $ time ./a.out 1  # non tail recursive version

  real	0m24.106s
  user	0m23.390s
  sys	0m0.290s

  $ time ./a.out 2  # tail recursive version

  real	0m3.627s
  user	0m3.390s
  sys	0m0.100s

(* Source code for the native code benchmark: many runs on a "short" list *)

  let l = Array.to_list (Array.init 120000 (fun x -> x)) in
  let map' f l =
    let rec aux acc = function
      | [] -> List.rev acc
      | hd :: tl -> aux (f hd :: acc) tl
    in
    aux [] l
  in
  let f x = x * x in
  let test_std () = List.map f l in
  let test_tail_rec () = map' f l in
  let repeat = 100 in
  match Sys.argv.(1) with
  | "1" -> for i = 1 to repeat do test_std () done
  | "2" -> for i = 1 to repeat do test_tail_rec () done
  | a -> raise (Invalid_argument a)

(* Native code benchmark *)

  $ time ./a.out 1

  real	0m14.683s
  user	0m14.270s
  sys	0m0.190s

  $ time ./a.out 2

  real	0m23.343s
  user	0m22.950s
  sys	0m0.070s


^ permalink raw reply	[flat|nested] 9+ messages in thread
end of thread, other threads:[~2003-06-05  2:16 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-06-04 12:00 [Caml-list] yet another benchmark: List.map vs tail recursive map Stefano Zacchiroli
2003-06-04 15:13 ` [Caml-list] " Christophe TROESTLER
2003-06-04 20:23   ` Stefano Zacchiroli
2003-06-04 20:31     ` Alexander V. Voinov
2003-06-04 21:58       ` Alan Post
2003-06-04 22:24         ` Alexander V. Voinov
2003-06-04 22:48           ` Brian Hurt
2003-06-05  2:14           ` Nicolas Cannasse
2003-06-04 21:56 ` [Caml-list] " Brian Hurt

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).