From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q27Gwt3O008016 for ; Wed, 7 Mar 2012 17:58:55 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjsDANCSV09KfVI0jWdsb2JhbABEoz+RVQgiAQEBAQkJCwkSBiOCCgEBAQMBEgIsARsSCwEDAQsGBQsNDSEhAQERAQUBChIGExIJB4dhBQubaAqLdIJxhUA/iHQBBQuJLoc2BJVBiyGDGD2EBQ X-IronPort-AV: E=Sophos;i="4.73,545,1325458800"; d="scan'208";a="134883979" Received: from mail-ww0-f52.google.com ([74.125.82.52]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 07 Mar 2012 17:58:50 +0100 Received: by wgbgn7 with SMTP id gn7so4393701wgb.9 for ; Wed, 07 Mar 2012 08:58:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; bh=6WI9K3LUX4PjFoxNaaykKC2+HDpHH2KV5Ae5fDeZSj0=; b=Kbw3oKYtmhqpFoYyMp9nwiE11S8nTUhReHHtujnbH6H5gL0M/ILB9DiodJZUtQ30Jm +cBdId9n8ENG97m7x0VaZpaY/7z7voxfFQnXUEIZ6bXGTUE1Zq/yLgIJBXfI3zNli8C9 5xfpdxd+03RuEcXWvHfTxCwjbrfjA/BThMpbo+K+UJMHYUB/K7mOopSQgmHUvxdUvvcD 1hlfuKsX0kNWxd91NuidzZu+R5ZP9OK4Z9qKTToMvgdq/R7p6bSDSX9dzyw3laSkHtTq U9TWxhgqAIuwRBSX/hxqFNifi/PnQa9R7yMaW4i3v8dd+/FCekTkbVg2FyGeOSmdS91F EsZw== Received: by 10.180.87.8 with SMTP id t8mr27711866wiz.15.1331139529308; Wed, 07 Mar 2012 08:58:49 -0800 (PST) MIME-Version: 1.0 Received: by 10.227.200.85 with HTTP; Wed, 7 Mar 2012 08:58:09 -0800 (PST) In-Reply-To: <878vjctlr3.fsf@frosties.localnet> References: <87sjhktqwi.fsf@frosties.localnet> <4F5777F2.2000806@gmail.com> <878vjctlr3.fsf@frosties.localnet> From: Gabriel Scherer Date: Wed, 7 Mar 2012 17:58:09 +0100 Message-ID: To: Goswin von Brederlow Cc: Edgar Friendly , caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id q27Gwt3O008016 Subject: Re: [Caml-list] Can one implement greedy/inline data structures in ocaml? > So then you need mutable option types or mutables that you initialize > with dummy values and then overwrite with the real thing once all > members of a cycle are created. Or some other trickery to make it > work. Overall cycles are generally not good. I believe the trick you need (either passing a dummy value of your type, or Obj.magic) is less ugly that your Camlp4 solution for inline access. If I really needed absolute performance, I'd use the inline version just like in C, with mutable fields, but without preprocessor sugar. Preprocessing could avoid a bit of duplication (corresponding to manual inlining) on the structure-definition side, but wouldn't simplify the structure-using code much. On Wed, Mar 7, 2012 at 5:32 PM, Goswin von Brederlow wrote: > Edgar Friendly writes: > >> On 03/07/2012 09:41 AM, Goswin von Brederlow wrote: >>> The task then needs pointers to each of the lists data >>> structures creating cycles. Not good for ocaml. It also would waste >>> memory for 2 pointers (per list). >> >> Cycles are fine for ocaml, pointers are pretty cheap, and I think the >> answer to your question is no - there's a regularity to values that's >> required by the garbage collector, and what you seem to want is the >> ability to inline nested structures without pointers, and OCaml's data >> representation doesn't allow this, mainly because of the tag word >> needed by the GC. >> >> Beware premature optimization. >> >> E. > > The problem with cycles is that you need to define all structures in a > cyled atomically as the same time. That means using "let rec foo = > ... and bar = ..." and sometimes needing to lift function calls out of > the initialization. > > For example and from memory you couldn't write this: > > let rec task = { >    all_list = all_list; >    state_list = state_list; >    foo = bar; > } > and all_list = DList.create_item all_list_head task > and state_list DList.create_item state_list_head task > > At the time the DList.create_item is called the task binding is still > incomplete and you get an error that it can't be on the right-hand side. > > So then you need mutable option types or mutables that you initialize > with dummy values and then overwrite with the real thing once all > members of a cycle are created. Or some other trickery to make it > work. Overall cycles are generally not good. > > > Inlining the DList wihtout another indirection like in C would be nice > but would certainly require some camlp4 code to pull off. But it would > certainly be enough to pull in a pointer to the list structure as long > as you don't also need a back pointer inside the list structure. The > cycle is the problem there, just one direction is fine. > > MfG >        Goswin > > -- > Caml-list mailing list.  Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs >