Re: [Caml-list] OCaml troll on Slashdot

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

From: brogoff <brogoff@speakeasy.net>
> On Wed, 16 Mar 2005, Jacques Garrigue wrote:
> > From: Yoann Padioleau <padiolea@irisa.fr>
> > > Jon Harrop <jon@ffconsultancy.com> writes:
> > > > In OCaml, non-tail-recursive functions are often faster than their tail
> > > > recursive equivalents for small inputs (e.g. short lists).
> > >
> > > really ? why ?
> >
> > Because tail-recursive versions do some extra work to ensure
> > tail-recursiveness. For instance building a list in reverse order, and
> > converting it back with List.rev at the end. This only pays off for
> > huge lists.
> 
> No doubt the implementors will want me guillotined for bringing this
> up again, but using the (still functional!) set_cdr! tail recursive
> functions, which do *not* reverse the list, are always faster than
> the non tail recursive list functions, even for small lists, at
> least in my experience. So I suspect that your "for instance" is in
> fact the only reason for the disparity. I'd welcome a
> counterexample.
>
> Those Obj based List functions are what ExtLib provides, I think,
> and there are even ways to get this optimization neatly into ML
> style languages. Maybe in ML 20XY this will be addressed.

I beg to differ on performance. 
Here are the results of a micro-benchmark comparing List.map and
ExtLib.List.map.

With List.map
l10*10000: 0.117188s
l100*1000: 0.132812s
l1000*100: 0.195312s
l10000*10: 0.859375s
l100000*1: 3.328125s

With ExtLib.List.map
l10'*10000: 0.187500s
l100'*1000: 0.203125s
l1000'*100: 0.304688s
l10000'*10: 1.382812s
l100000'*1: 1.937500s

So you can see that the tail-recursive version only gets faster
somewhere between 10000 and 100000 elements. Hardly typical use of
lists. On the other hand, there are cases where the non tail-recursive
version will blow-up your stack, so you have no choice but to go with
the possibly slower tail-recursive one.

Jacques Garrigue

Code used:

let rec genlist n = if n > 0 then n :: genlist (n-1) else []

let l10 = genlist 10
let l100 = genlist 100
let l1000 = genlist 1000
let l10000 = genlist 10000
let l100000 = genlist 100000

let time f n =
  let t0 = (Unix.times ()).Unix.tms_utime in
  f n;
  (Unix.times()).Unix.tms_utime -. t0

let call_map l n =
  for i = 1 to n do ignore (List.map succ l) done

let call_extmap l n =
  for i = 1 to n do ignore (ExtList.List.map succ l) done

let process l =
  List.iter
    (fun (name, f, n) ->
      Gc.full_major ();
      let t = time f (n*100) in
      Printf.printf "%s*%d: %fs\n" name n t;
      flush stdout)
    l

let () =
  process
    [ "l10", call_map l10, 10000;
      "l100", call_map l100, 1000;
      "l1000", call_map l1000, 100;
      "l10000", call_map l10000, 10;
      "l100000", call_map l100000, 1;
      "l10'", call_extmap l10, 10000;
      "l100'", call_extmap l100, 1000;
      "l1000'", call_extmap l1000, 100;
      "l10000'", call_extmap l10000, 10;
      "l100000'", call_extmap l100000, 1; ]