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 OAA03999; Sun, 4 May 2003 14:56:57 +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 OAA03594 for ; Sun, 4 May 2003 14:56:55 +0200 (MET DST) Received: from eposta.kablonet.com.tr ([62.248.102.66]) by nez-perce.inria.fr (8.11.1/8.11.1) with SMTP id h44CurT15686 for ; Sun, 4 May 2003 14:56:54 +0200 (MET DST) Received: (qmail 75966 invoked by uid 0); 4 May 2003 13:04:21 -0000 Received: from unknown (HELO 195.174.169.185) (exa@kablonet.com.tr@195.174.169.185) by 0 with SMTP; 4 May 2003 13:04:21 -0000 From: Eray Ozkural Reply-To: erayo@cs.bilkent.edu.tr Organization: Bilkent University CS Dept. To: Neel Krishnaswami , "caml Mailing List'" Subject: Re: [Caml-list] Efficiency of 'a list Date: Sun, 4 May 2003 15:56:06 +0300 User-Agent: KMail/1.5.9 References: <3EB4922A.A69C2038@PublicPropertySoftware.com> <16052.61901.189814.21042@h00045a4799d6.ne.client2.attbi.com> In-Reply-To: <16052.61901.189814.21042@h00045a4799d6.ne.client2.attbi.com> MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200305041556.06626.exa@kablonet.com.tr> X-Spam: no; 0.00; eray:01 ozkural:01 caml-list:01 neel:01 krishnaswami:01 iterating:01 ocaml's:01 compacting:01 floats:01 unbox:01 occupies:01 misses:01 modifies:01 pointers:01 erayo:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sunday 04 May 2003 13:56, Neel Krishnaswami wrote: > > 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. Now, we're getting some performance talk :) To be precise, comparing an int list and int array we'll see that list occupies twice the same memory and therefore will generate more cache misses. But as the size of 'a in 'a list grows the difference will be negligible. However, if one modifies the elements of an array, in FORTRAN style, won't really be storing huge records inside elements of the array. He will likely split things up in parallel arrays where necessary, and if there are records they will be stored in a private heap and pointers will be stored in the array, etc. Cheers, -- Eray Ozkural (exa) Comp. Sci. Dept., Bilkent University, Ankara KDE Project: http://www.kde.org www: http://www.cs.bilkent.edu.tr/~erayo Malfunction: http://mp3.com/ariza GPG public key fingerprint: 360C 852F 88B0 A745 F31B EA0F 7C07 AE16 874D 539C ------------------- 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