From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id CDF1DD45F for ; Fri, 4 Nov 2005 00:34:08 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jA3NY8TH001373 for ; Fri, 4 Nov 2005 00:34:08 +0100 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 AAA22017 for ; Fri, 4 Nov 2005 00:34:07 +0100 (MET) Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.206]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jA3NY6Kw028091 for ; Fri, 4 Nov 2005 00:34:07 +0100 Received: by xproxy.gmail.com with SMTP id h30so714145wxd for ; Thu, 03 Nov 2005 15:34:06 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=ftsnlTIIddim4FMiJoYeklXs3jG5XNjOr7szTNhWEwDi4PlzrJtyUSIbFGHgnEjM8fXiUZY6taDJF0wGpNqBzUVz67PQN0jcdgjk3nkSvASSjBv11uKEyHFBi4pdA8lbmpjNc9C5txXsM0orxB3tYagYeNKjaakGyiTH0Dqf4ps= Received: by 10.64.183.17 with SMTP id g17mr1376497qbf; Thu, 03 Nov 2005 15:34:06 -0800 (PST) Received: by 10.65.193.14 with HTTP; Thu, 3 Nov 2005 15:34:06 -0800 (PST) Message-ID: Date: Thu, 3 Nov 2005 17:34:06 -0600 From: "Seth J. Fogarty" To: caml-list Subject: References, compact bollean values (and other questions) MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline X-Miltered: at nez-perce with ID 436A9E70.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 436A9E6E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; ocaml:01 mutable:01 mutable:01 integers:01 ocamlc:01 booleans:01 ocamlc:01 booleans:01 pervasives:01 inlining:01 inlining:01 failwith:01 node:01 node:01 ideally:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.9 required=5.0 tests=RCVD_BY_IP, RCVD_IN_BL_SPAMCOP_NET autolearn=disabled version=3.0.3 So I am implementing a DPLL procedure for CNF sat. This is the first time, for me, that I've been programming in ocaml that speed is absolutely critical. I will have a small code base running for literally days on end. Thus I have some speed/efficiently questions. First question: I notice references are implemented using mutable records. Does this imply tuples of references are slower than mutable records? I.E. type a =3D int ref * int ref * int ref vs type a =3D {mutable a : int; mutable b : int; mutable c : int} Second: I need a non-varient data type. It needs to store three integers and six mutable boolean. I would like this to be done as compactly as possible, ideally in 128 contiguious bits. Will either records or tuples store these contiguously? If I use tuples and references, will ocamlc 'compact' booleans, or give them 32 bits each? I think this is highly unlikely. If I use records, will ocamlc 'compact' booleans, or give them 32 bits each= ? If I use an integer to represent all six booleans, is there an easy way to gain access to/flip a single bit? I can only find shifting operations in pervasives Third question: How aggressive/intelligent is the ocamlc inlining? Should I worry about inlining functions that I expect to be used millions of times? Fourth question: If you got this far and still want to help, is there anything obviously wrong with the following imperitive linked list implementation in terms of speed? I expect traversal to be rare. I have defined add, delete, and insert operations (that are easily undoable). type 'a ll =3D Nul | Node of 'a * 'a ll ref | Head of 'a ll ref type 'a llptr =3D 'a ll * 'a ll (*the predecessor and the node pointed to.*= ) type 'a undo =3D 'a ll ref * 'a ll let undo ((a, b) : 'a undo) =3D a :=3D b let delete (llptr : 'a llptr) : 'a undo =3D match llptr with |(Head b, (Node (_, b') as deleted)) |(Node (_, b), (Node (_, b') as deleted)) -> b :=3D !b'; (b, deleted) |_ -> failwith "delete" -- Seth Fogarty sfogarty@[gmail.com|rice.edu|livejournal] Neep-neep at large AIM: Sorrath "I know there are people in this world who do not love their fellow human beings - and I hate people like that" --Tom Lehrer.