Browse thread
tip for tail recursive map
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2009-11-02 (23:29) |
From: | Jon Harrop <jon@f...> |
Subject: | Re: [Caml-list] tip for tail recursive map |
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