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