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