Re: [Caml-list] tip for tail recursive map

[Jon Harrop <jon@ffconsultancy.com>]

On Monday 02 November 2009 20:00:31 Christophe Raffalli wrote:
> List of size 10000, 10000 times with standard map : 7.564473s
> List of size 10000, 10000 times with map with rev : 15.452965s
> List of size 10000, 10000 times with map with prelist : 12.672792s
> List of size 10000, 10000 times with map with obj : 11.572724s

Note that standard "map" is still very fast on this list length.

> List of size 100000, 1000 times with standard map : 33.018063s
> List of size 100000, 1000 times with map with rev : 42.142634s
> List of size 100000, 1000 times with map with prelist : 22.161385s
> List of size 100000, 1000 times with map with obj : 20.801299s

Standard map is now relatively slower but only because it is O(n^2). Look at 
page 152 figure 7.4 of OCaml for Scientists to see this effect clearly. It is 
caused by the periodic traversal of the O(n) deep stack by the GC and it 
slows everything down (you get a similar effect with hash tables because the 
GC traverses arrays of pointers, like the spine, atomically).

> standard map with size 1000000 segfaults on my machine
> List of size 1000000, 100 times with map with rev : 55.211450s
> List of size 1000000, 100 times with map with prelist : 23.549472s
> List of size 1000000, 100 times with map with obj : 21.777361s

You can use ulimit to get a bigger function call stack and keep running the 
ordinary "map" as far as you want.

> Conclusion : dirty map wins for large lists, Standard map wins for small
> lists...

I think you can do a lot better than this and I think Xavier's recommendation 
stands (Obj is a horiffically bad idea unless you wrote the compiler and 
run-time *and* have the memory of an elephant ;-). Specifically, you just 
need to get rid of the O(n^2) behaviour by bounding the stack depth, perhaps 
using a trampoline.

IIRC, this was discussed on this list many years ago. One notable observation 
was that adding a depth accumulator does not degrade performance. Another 
alternative is to convert the list into an array rather than reversing it and 
use the array as a kind of alternative to the function call stack (I think F# 
does this).

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e