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

[Stefano Zacchiroli]

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

[Christophe TROESTLER]

On Wed, 4 Jun 2003, Stefano Zacchiroli <za...@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

[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-lis...@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

[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

[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

[Alan Post]

In article <3EDE572C...@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

[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

[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

[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