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 RAA30467; Wed, 4 Jun 2003 17:09:38 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA30485 for ; Wed, 4 Jun 2003 17:09:37 +0200 (MET DST) Received: from abel.swapping.umh.ac.be (nat.umh.ac.be [193.190.193.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h54F9aH14819 for ; Wed, 4 Jun 2003 17:09:37 +0200 (MET DST) Received: from abel.swapping.umh.ac.be ([127.0.0.1] helo=localhost ident=trch) by abel.swapping.umh.ac.be with esmtp (Exim 3.36 #1 (Debian)) id 19NZx9-00025H-00; Wed, 04 Jun 2003 17:13:27 +0200 Date: Wed, 04 Jun 2003 17:13:27 +0200 (CEST) Message-Id: <20030604.171327.37652101.debian00@tiscali.be> To: zack@bononia.it Cc: caml-list@inria.fr Subject: [Caml-list] Re: yet another benchmark: List.map vs tail recursive map From: Christophe TROESTLER In-Reply-To: <20030604120011.GA12262@fistandantilus.takhisis.org> References: <20030604120011.GA12262@fistandantilus.takhisis.org> Organization: None X-Spook: bank Mena number key Fortezza White Water Noriega ANZUS USCODE Ceridian world domination X-Mailer-URL: http://www.mew.org/ X-Operating-System: GNU/Linux (http://www.linux.org/) X-Blessing: Om Ah Hum Vajra Guru Pema Siddhi Hum X-Mailer: Mew version 3.3rc1 on Emacs 21.2 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Multipart/Mixed; boundary="--Next_Part(Wed_Jun__4_17:13:27_2003_021)--" Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; troestler:01 tiscali:99 bononia:01 overflows:01 slower:01 400000:99 discourage:01 bagley:01 printf:01 chris:01 christophe:01 explicitely:01 ocaml:01 bytecode:01 rec:01 X-Attachments: name="map.ml" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk ----Next_Part(Wed_Jun__4_17:13:27_2003_021)-- Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit On Wed, 4 Jun 2003, Stefano Zacchiroli 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 ----Next_Part(Wed_Jun__4_17:13:27_2003_021)-- Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="map.ml" (* You need the Benchmark module (http://www.bagley.org/~doug/ocaml/benchmark/). *) let map' f l = (* tail recursive version of map *) let rec aux acc = function | [] -> List.rev acc | hd :: tl -> aux (f hd :: acc) tl in aux [] l let map2 f l = (* Crazy way... *) Array.to_list(Array.map f (Array.of_list l)) let () = let f x = succ x in (* simple fun, so its cost should be unimportant *) let bench n = let l = Array.to_list (Array.init n (fun x -> x)) in Printf.printf ">>> LIST LENGTH = %i\n" n; let res = Benchmark.throughputN 20 [("List.map", List.map f, l); ("tail_rec", map' f, l); ("crazy", map2 f, l) ] in Benchmark.tabulate res in bench 100; bench 1000; bench 10_000; bench 100_000; bench 400_000 ----Next_Part(Wed_Jun__4_17:13:27_2003_021)---- ------------------- 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