From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTP id CF04F7EC6E for ; Fri, 17 Jan 2014 10:11:18 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of dhouse@janestreet.com) identity=pra; client-ip=38.105.200.229; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dhouse@janestreet.com"; x-sender="dhouse@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of dhouse@janestreet.com designates 38.105.200.229 as permitted sender) identity=mailfrom; client-ip=38.105.200.229; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dhouse@janestreet.com"; x-sender="dhouse@janestreet.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@tot-dmz-mxout1.janestreet.com) identity=helo; client-ip=38.105.200.229; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dhouse@janestreet.com"; x-sender="postmaster@tot-dmz-mxout1.janestreet.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AioCAJFf2FImacjlnGdsb2JhbABZg0NQBqgoihSIVYEHHg4BAQEBAQYWCTyCJQEBAQMBQAEBLAsBBAsLCw0NISEBEgEFAQoSBhMSh14DCQgDAgMFnQ6LE4RSAQWSWAMKhVYRBoxrghAEB4Q4ljmBbIExiysDg0sYKYRZ X-IPAS-Result: AioCAJFf2FImacjlnGdsb2JhbABZg0NQBqgoihSIVYEHHg4BAQEBAQYWCTyCJQEBAQMBQAEBLAsBBAsLCw0NISEBEgEFAQoSBhMSh14DCQgDAgMFnQ6LE4RSAQWSWAMKhVYRBoxrghAEB4Q4ljmBbIExiysDg0sYKYRZ X-IronPort-AV: E=Sophos;i="4.95,670,1384297200"; d="scan'208";a="53664449" Received: from mx5.janestreet.com (HELO tot-dmz-mxout1.janestreet.com) ([38.105.200.229]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 17 Jan 2014 10:11:18 +0100 Received: from tot-oib-smtp1.delacy.com ([172.27.22.15] helo=tot-smtp) by tot-dmz-mxout1.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1W45SP-0002bc-Dg for caml-list@inria.fr; Fri, 17 Jan 2014 04:11:17 -0500 Received: from tot-dmz-mxgoog1.delacy.com ([172.27.224.14] helo=mxgoog2.janestreet.com) by tot-smtp with esmtps (TLSv1:AES256-SHA:256) (Exim 4.72) (envelope-from ) id 1W45SP-0008Q9-CA for caml-list@inria.fr; Fri, 17 Jan 2014 04:11:17 -0500 Received: from mail-ob0-f169.google.com ([209.85.214.169]) by mxgoog2.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1W45SP-0001d1-9T for caml-list@inria.fr; Fri, 17 Jan 2014 04:11:17 -0500 Received: by mail-ob0-f169.google.com with SMTP id wp4so4088104obc.0 for ; Fri, 17 Jan 2014 01:11:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=bIduOgKePooi9OjvDs76AeAFV/6HDHzLZnMH8VJEA1E=; b=IS3KhmsV0L2oH8b7Zl4A+hDlOO9/tE7zY2OUB9VnqVJ7kQmEsmYp7xANc5wSoRfnoK 9wmK+YBUjkkouo8z88qKA96oyqx6RKvyJZ9AxqPe4rexAZUewfoi84m9swvjP2x621UE jtcovHiFEW6RUF3wupPAlpUjT/be57dCwm09A= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=bIduOgKePooi9OjvDs76AeAFV/6HDHzLZnMH8VJEA1E=; b=IUrID+ob09b0Ehape3dHX8NMxZ1sdA26W7EFv9UKPLzrZShhgdT5yzhcdf2kWKKUUm 6FYnSaFvEEii4wuGvx3O+o0LOMGoqPHXARaS8ZfXqjBeZcrG7/8qRWilpEJWAlSms+lW UT9m7wH228wnn9pTKdpcSY3OtCSlahR5XJlwLwZvw0rpBT4l3GlHUG08d4A7Ub+jSSYF QJ6QrjksL/8L5pits69Ysn5PGXbGVBaepdkZ8FbS63RXSLeg2UgRX3Q8BXLlxmPNzhXp 25EbINeBYZveuE2kdJw/K1k8RckIN25x8lNI7AWp1cJ/VEdzgUDLKokYYAx/SOKcI6BT SlEA== X-Gm-Message-State: ALoCoQnLuw++B3R62jtPOR/TocSmGl+StbCJKjDiYCDr4VG1O1du+kLyspIldW76fmgL723c0eVjQxCrSslvt5OwNrLwC3l5HVzb/kwrZABR4w+jDg9vGkBmnhiezZLzVYeJWznfopMNVE1C/JRnmGI2+RT0Oxby9w== X-Received: by 10.60.78.9 with SMTP id x9mr620748oew.72.1389949877060; Fri, 17 Jan 2014 01:11:17 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.60.78.9 with SMTP id x9mr620741oew.72.1389949876956; Fri, 17 Jan 2014 01:11:16 -0800 (PST) Received: by 10.76.83.42 with HTTP; Fri, 17 Jan 2014 01:11:16 -0800 (PST) In-Reply-To: References: <523666417617602473@orange.fr> Date: Fri, 17 Jan 2014 09:11:16 +0000 Message-ID: From: David House To: Julien Blond Cc: Damien Guichard , Caml Mailing List Content-Type: multipart/alternative; boundary=089e0111bc64ac06c504f026eca9 Subject: Re: [Caml-list] How much optimized is the 'a option type ? --089e0111bc64ac06c504f026eca9 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable My attachment got rejected by the list. http://imgur.com/de9SBnA On 17 January 2014 09:09, David House wrote: > Here's some high-tech computer visualisation to illustrate this. > > > On 17 January 2014 08:40, David House wrote: > >> Err, right, sorry. If you have None in, say, a record, that's not >> allocated at all. Rather than there being a pointer in that field, there= is >> special word in that field which represents None. >> >> If that field is a Some, then it's a pointer to a two word allocated >> block which in turn points at the actual thing. So compared to a C point= er, >> there an extra two words and one more indirection. >> >> >> On 17 January 2014 08:16, Julien Blond wrote: >> >>> > An option value always takes two words: one for the header, and then >>> either a pointer or a word that means "None". >>> >>> No. From the reference manual =A7 19.3.4 : >>> >>> type 'a option =3D None (* Val_int(0), i.e. just an integer >>> value =3D 1 word *) >>> | Some of 'a (* block of size 1 =3D [(header =3D= 1 >>> word) + (1 field =3D 1 word)] =3D 2 words *) >>> >>> >>> 2014/1/17 David House >>> >>>> It behaves identically to that type. >>>> >>>> It is just like any other sum type. However, due to the way that sum >>>> types are represented in memory, it is not that inefficient. The only = thing >>>> that makes it less efficient than a C pointer is the header block >>>> (necessary for the GC). An option value always takes two words: one fo= r the >>>> header, and then either a pointer or a word that means "None". >>>> >>>> >>>> On 17 January 2014 07:35, Damien Guichard wrote: >>>> >>>>> Hello, >>>>> >>>>> Compared to the code : >>>>> >>>>> type 'a option =3D None | Some of 'a >>>>> >>>>> How do an 'a option value performs ? >>>>> Any allocation saved ? >>>>> Any indirection removed ? >>>>> >>>>> Is 'a option just like any sum type ? >>>>> Or is 'a option more like an ANSI C pointer type ? >>>>> >>>>> Regards, >>>>> >>>>> Damien Guichard >>>>> >>>>> >>>>> >>>>> -- >>>>> Caml-list mailing list. Subscription management and archives: >>>>> https://sympa.inria.fr/sympa/arc/caml-list >>>>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >>>>> Bug reports: http://caml.inria.fr/bin/caml-bugs >>>>> >>>> >>>> >>> >> > --089e0111bc64ac06c504f026eca9 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
My attachment got rejected by the list.=A0http://imgur.com/de9SBnA


On 17 January 2014 09:09, David H= ouse <dhouse@janestreet.com> wrote:
Here's some high-tech c= omputer visualisation to illustrate this.


On 17 January= 2014 08:40, David House <dhouse@janestreet.com> wrote:<= br>
Err, right, sorry. If you h= ave None in, say, a record, that's not allocated at all. Rather than th= ere being a pointer in that field, there is special word in that field whic= h represents None.

If that field is a Some, then it's a pointer to a two word allocat= ed block which in turn points at the actual thing. So compared to a C point= er, there an extra two words and one more indirection.


On 17 January 2014 08:16, Julien Blond <julien.blond@gmail.com= > wrote:
&g= t; An option value always takes two words: one for the header, and then eit= her a pointer or a word that means "None".

No. From the reference manual =A7 19.3.4 :

type 'a option =3D None=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (* Val_= int(0), i.e. just an integer value =3D 1 word *)
=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 | Some of 'a=A0=A0 = (* block of size 1 =3D [(header =3D 1 word) + (1 field =3D 1 word)] =3D 2 w= ords *)


2014/1/17 David House <dhouse@janestreet.com>
It behaves identically to that type.

It= is just like any other sum type. However, due to the way that sum types ar= e represented in memory, it is not that inefficient. The only thing that ma= kes it less efficient than a C pointer is the header block (necessary for t= he GC). An option value always takes two words: one for the header, and the= n either a pointer or a word that means "None".


On 17 January 2014 07:35, Damien Guichard <alphablock@orange.fr= > wrote:
Hello,

Compared to the code :

type 'a option =3D None | Some of 'a

How do an 'a option value performs ?
Any allocation saved ?
Any indirection removed ?

Is 'a option just like any sum type ?
Or is 'a option more like an ANSI C pointer type ?

Regards,

Damien Guichard



--
Caml-list mailing list. =A0Subscription management and archives:
ht= tps://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs





--089e0111bc64ac06c504f026eca9--