From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA06424; Wed, 4 Jun 2003 22:33:58 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA06364 for ; Wed, 4 Jun 2003 22:33:57 +0200 (MET DST) Received: from escargot.exelixis.com (shaker.exelixis.com [65.209.203.254]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h54KXsT13380 for ; Wed, 4 Jun 2003 22:33:54 +0200 (MET DST) Received: from quasar.ipa.nw.ru (dhcp-172-29-16-184.exelixis.com [172.29.16.184]) by escargot.exelixis.com (8.8.8/8.8.8/GNAC-GW-2.1) with ESMTP id NAA17666; Wed, 4 Jun 2003 13:33:41 -0700 (PDT) Message-ID: <3EDE572C.2010707@quasar.ipa.nw.ru> Date: Wed, 04 Jun 2003 13:31:40 -0700 From: "Alexander V. Voinov" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.4b) Gecko/20030507 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Stefano Zacchiroli CC: caml-list@inria.fr Subject: Re: [Caml-list] Re: yet another benchmark: List.map vs tail recursive map References: <20030604120011.GA12262@fistandantilus.takhisis.org> <20030604.171327.37652101.debian00@tiscali.be> <20030604202317.GF18515@fistandantilus.takhisis.org> In-Reply-To: <20030604202317.GF18515@fistandantilus.takhisis.org> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; voinov:01 quasar:01 caml-list:01 troestler:01 recursion:01 slower:01 callback:01 christophe:01 alexander:01 bytecode:01 terribly:01 0200,:01 benchmark:02 ipa:02 compile:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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 ------------------- To unsubscribe, mail caml-list-request@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