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 VAA19855; Fri, 2 May 2003 21:27:52 +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 VAA19914 for ; Fri, 2 May 2003 21:27:50 +0200 (MET DST) Received: from eposta.kablonet.com.tr ([62.248.102.66]) by concorde.inria.fr (8.11.1/8.11.1) with SMTP id h42JRkH21805 for ; Fri, 2 May 2003 21:27:47 +0200 (MET DST) Received: (qmail 52112 invoked by uid 0); 2 May 2003 19:35:17 -0000 Received: from unknown (HELO 195.174.169.185) (exa@kablonet.com.tr@195.174.169.185) by 0 with SMTP; 2 May 2003 19:35:17 -0000 From: Eray Ozkural Reply-To: erayo@cs.bilkent.edu.tr Organization: Bilkent University CS Dept. To: "Ocaml Mailing List" Subject: [Caml-list] Efficiency of 'a list Date: Fri, 2 May 2003 22:27:20 +0300 User-Agent: KMail/1.5.9 MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Message-Id: <200305022227.20136.exa@kablonet.com.tr> X-Spam: no; 0.00; eray:01 ozkural:01 topological:01 incarnations:01 model:01 erayo:01 bilkent:01 ankara:01 kde:01 malfunction:01 ariza:01 linked:01 ocaml:01 sci:01 lisp:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Hi there, In my maniacal pursuit of efficiency I figured that I don't truly understand the performance of ocaml lists. Could somebody please point to an explanation of ocaml linked list implementation or summarize its performance characteristics? This might seem like a trivial question but having used many functional languages I know that it's easy to commit performance genocide using linked lists. For instance, a naive implementation of an optimal comparison sorting algorithm in LISP almost invariably results in an O(n^2logn) routine :) Therefore, it would be a good start to explain whether ocaml lists are in fact LISP lists and if not in what aspects they differ. The motivation for this question comes from trying to understand the use of linked lists in an efficient algorithm, such as graph algorithms (say we are implementing topological sort) Assume I'm using the following structure that is far from handsome: type x = (int list) array Let a's type be x. Consider codes as the following a.(i) <- a.(i) @ [x;y;z] a.(i) <- [x] :: a.(i) What travesty results in execution of such codes with i coming from an arbitrary sequence? Do using such constructs result in unholy incarnations of space leaks or gross inefficiencies? Another question, does ocaml make any effort to place members of a list close to each other? Or, more naturally, the list element is allocated using a global model and then simply linked inside the structure? These questions may sound weird but I'm hoping it will make sense to somebody! Regards, -- 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