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

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

[Stefano Zacchiroli]

[-- 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

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

[Christophe TROESTLER]

[-- 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

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

[Stefano Zacchiroli]

On Wed, Jun 04, 2003 at 05:13:27PM +0200, Christophe TROESTLER wrote:
> 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

My point is not having speed, but rather having tail recursion. In many
cases lists are the correct data structure even for "a lot of elements".

I've always thought that tail recursive version of map would have been
terribly slower than not tail recrusive one due to the additional
reversal. But since this is not the case (or at least the shown figures
don't fit my idea of "terribly"), why keep on using the not tail
recursive one?

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

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

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

[Alexander V. Voinov]

Hi Stefano,

Stefano Zacchiroli wrote:

>On Wed, Jun 04, 2003 at 05:13:27PM +0200, Christophe TROESTLER wrote:
>  
>
>>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
>>    
>>
>
>My point is not having speed, but rather having tail recursion. In many
>cases lists are the correct data structure even for "a lot of elements".
>
>I've always thought that tail recursive version of map would have been
>terribly slower than not tail recrusive one due to the additional
>reversal. 
>
A year ago I 'benchmarked' almost exactly the alternatives you discuss 
within some real application. The difference was substantial, and I had 
to work with 'lots of elements'. List.rev took significant time, you 
can't neglect this. I even thought about implementing List.map as a C 
extension which calls the first argument as a callback and use pointer 
operations to build the list without consuming the stack. Not sure if 
it's a _proper-way-to-go_ :-).

Alexander


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

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

[Brian Hurt]

On Wed, 4 Jun 2003, Stefano Zacchiroli wrote:

> 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?

I think so.  ExtLib even has a non-reversing, tail-recursive version.  
Along with other usefull libraries.

http://sourceforge.net/projects/ocaml-lib/

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

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

[Alan Post]

In article <3EDE572C.2010707@quasar.ipa.nw.ru>, Alexander V. Voinov wrote:
>
> A year ago I 'benchmarked' almost exactly the alternatives you discuss 
> within some real application. The difference was substantial, and I had 
> to work with 'lots of elements'. List.rev took significant time, you 
> can't neglect this. I even thought about implementing List.map as a C 
> extension which calls the first argument as a callback and use pointer 
> operations to build the list without consuming the stack. Not sure if 
> it's a _proper-way-to-go_ :-).

Have you seen the List.map provided by the extlib guys?

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/ocaml-lib/extlib-dev/extList.ml


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

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

[Alexander V. Voinov]

Hi Alan,

Alan Post wrote:

>Have you seen the List.map provided by the extlib guys?
>
>http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/ocaml-lib/extlib-dev/extList.ml
>  
>
Yes-yes, I do and probably will switch to it if it's reasonably stable. 
(the site says no releases available yet :-)

Thank you!

Alexander


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

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

[Brian Hurt]

On Wed, 4 Jun 2003, Alexander V. Voinov wrote:

> Hi Alan,
> 
> Alan Post wrote:
> 
> >Have you seen the List.map provided by the extlib guys?
> >
> >http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/ocaml-lib/extlib-dev/extList.ml
> >  
> >
> Yes-yes, I do and probably will switch to it if it's reasonably stable. 
> (the site says no releases available yet :-)
> 

The library as a whole is still unstable (witness Enum).  *That* module is 
stable.  And, in my opinion, 1.0 ready.  There's a known problem with the 
psqueue module-  I'm working on it.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

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

[Nicolas Cannasse]

> >Have you seen the List.map provided by the extlib guys?
> >
>
>http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/ocaml-lib/extlib-dev/extList
.ml
> >
> >
> Yes-yes, I do and probably will switch to it if it's reasonably stable.
> (the site says no releases available yet :-)

The library has not been released yet because mainly we need to add some
documentation and we're planning to include more modules.
But you can consider that 90% of the library (including the current List
tail-rec operations) is stable.
Actually I think it's quite difficult to write unstable code with OCaml :-).

Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners