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 AAA20408; Sun, 4 May 2003 00:03:56 +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 AAA18231 for ; Sun, 4 May 2003 00:03:54 +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 h43M3qT25088 for ; Sun, 4 May 2003 00:03:52 +0200 (MET DST) Received: (qmail 97016 invoked by uid 0); 3 May 2003 22:11:19 -0000 Received: from unknown (HELO 195.174.169.185) (exa@kablonet.com.tr@195.174.169.185) by 0 with SMTP; 3 May 2003 22:11:19 -0000 From: Eray Ozkural Reply-To: erayo@cs.bilkent.edu.tr Organization: Bilkent University CS Dept. To: Lauri Alanko , caml-list@inria.fr Subject: Re: [Caml-list] Efficiency of 'a list Date: Sun, 4 May 2003 01:03:03 +0300 User-Agent: KMail/1.5.9 References: <200305022227.20136.exa@kablonet.com.tr> <20030503211343.GC700@la.iki.fi> In-Reply-To: <20030503211343.GC700@la.iki.fi> MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200305040103.04121.exa@kablonet.com.tr> X-Spam: no; 0.00; eray:01 ozkural:01 caml-list:01 lauri:01 alanko:01 immutable:01 mattias:01 allocates:01 ocaml's:01 deque:01 overwritten:01 doubly:01 locality:01 erayo:01 bilkent:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sunday 04 May 2003 00:13, Lauri Alanko wrote: > It's easy to commit performance genocide with any data structure if you > use it for things for which it is not efficient. Singly linked immutable > lists have some nice characteristics: O(1) for cons, head and tail, all > purely functionally so you can safely share structure between multiple > lists. For example, lists are perfect for representing several alternate > paths in a path search. OK. So as Mattias said it is the same thing as LISP lists. > > For the second line I think you mean either > a.(i) <- x :: a.(i) > or > a.(i) <- [x] @ a.(i) > *blush* yes I meant the former. > Both of these are O(1). The first allocates a single cell, the second > theoretically two (one of which is discarded immediately) unless the > compiler is smart. > > If you really need to add stuff to both ends of a data structure, > ocaml's primitive lists aren't the thing. You might consider some sort > of a deque. > Hmm. I'm just trying to understand if ocaml lists would be adequate for representing adjacency lists. I thought it'd be easier for programmers to deal with it than something else that I might write. [And since such a thing is likely to pervade my library I should decide early :) ] I also wanted to learn if the compiler went to any length in optimization when it can determine that a mutable field is being overwritten like in a.(i) <- a.(i) @ [x] --- Of course here it is obvious that there is no reference count associated with objects, and another structure might be sharing the list, etc. so there is probably no room for optimization. BTW, we don't have imperative lists in the standard library...I wonder if something like a really simple doubly linked list or non-shared singly linked list would be worthwhile (wasn't that an exercise in ocaml book?) > However, the copying garbage collector is quite likely to enhance > locality of lists when it runs. Someone more knowledgeable can probably > tell more on this. I understand that garbage collectors are pretty smart nowadays. Maybe it might be attempting to compact memory in a way. Happy hacking, -- 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