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 MAA01102; Sun, 4 May 2003 12:52:32 +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 MAA01716 for ; Sun, 4 May 2003 12:52:30 +0200 (MET DST) Received: from h00045a4799d6.ne.client2.attbi.com (h00045a4799d6.ne.client2.attbi.com [65.96.179.155]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h44AqTT13628 for ; Sun, 4 May 2003 12:52:30 +0200 (MET DST) Received: by h00045a4799d6.ne.client2.attbi.com (Postfix, from userid 500) id 513762A29F; Sun, 4 May 2003 06:56:13 -0400 (EDT) From: Neel Krishnaswami MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16052.61901.189814.21042@h00045a4799d6.ne.client2.attbi.com> Date: Sun, 4 May 2003 06:56:13 -0400 To: "caml Mailing List'" Subject: Re: [Caml-list] Efficiency of 'a list In-Reply-To: References: <3EB4922A.A69C2038@PublicPropertySoftware.com> X-Mailer: VM 7.04 under 21.4 (patch 8) "Honest Recruiter" XEmacs Lucid X-Spam: no; 0.00; neel:01 krishnaswami:01 neelk:01 caml-list:01 recursively:01 iterating:01 ocaml's:01 compacting:01 floats:01 unbox:01 arrays:01 ocaml:01 garbage:01 writes:01 exception:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Ville-Pertti Keinonen writes: > > I've done a little timing of things, and according to my results: > > If you care about efficiency and use OCaml, you should use lists > > fairly often, ie if you are always looping and accessing the elements > > in order. OCaml can iterate through a list (recursively) about twice as > > fast as it can iterate through an array. It can iterate through a > > list about as fast as or maybe even a little faster than C or C++ can > > iterate through an array. > > Don't trust microbenchmarks too far over what your knowledge of how > things should work tell you. Iterating over arrays is certainly > going to be much more cache-and TLB-friendly. This is not be as true you think. Ocaml's garbage collector is a compacting, copying GC, so it's very likely that lists will end up in in continuous blocks of memory. This will end up being nearly as cache-friendly as an array is. The big exception is with arrays of floats -- Ocaml unboxes arrays of floats, but doesn't unbox lists of them. -- Neel Krishnaswami neelk@alum.mit.edu ------------------- 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