From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 2E3CEBBAF for ; Tue, 3 Nov 2009 00:29:32 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AuIAAJP57krUnwckkGdsb2JhbACCH4JVlmIBAQEBBwsMBxMEsBSQA4EygjhTBA X-IronPort-AV: E=Sophos;i="4.44,670,1249250400"; d="scan'208";a="37430610" Received: from relay.ptn-ipout02.plus.net ([212.159.7.36]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 03 Nov 2009 00:29:31 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AioHAJP57kpUXebq/2dsb2JhbACCH4JVxzaQA4EygjhTBA Received: from relay07.plus.net (HELO fhw-relay07.plus.net) ([84.93.230.234]) by relay.ptn-ipout02.plus.net with ESMTP; 02 Nov 2009 23:29:30 +0000 Received: from [87.113.75.250] (helo=leper.local) by fhw-relay07.plus.net with esmtp (Exim) id 1N56L4-0003Nz-4c for caml-list@yquem.inria.fr; Mon, 02 Nov 2009 23:29:30 +0000 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] tip for tail recursive map Date: Mon, 2 Nov 2009 23:30:21 +0000 User-Agent: KMail/1.9.9 References: <8F7FB895-BC42-49C6-BAB3-4EDDF761C78B@inria.fr> <4AEF3A5F.2060306@univ-savoie.fr> In-Reply-To: <4AEF3A5F.2060306@univ-savoie.fr> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200911022330.21302.jon@ffconsultancy.com> X-Plusnet-Relay: b306f7267c49775f9ea5e15693315f09 X-Spam: no; 0.00; recursive:01 christophe:01 raffalli:01 ocaml:01 hash:01 arrays:01 pointers:01 atomically:01 segfaults:01 ulimit:01 xavier's:01 compiler:01 run-time:01 trampoline:01 iirc:01 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