From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 9BB367F712 for ; Fri, 24 Jan 2014 17:56:39 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of jon@ffconsultancy.com) identity=pra; client-ip=212.159.14.18; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="jon@ffconsultancy.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of jon@ffconsultancy.com) identity=mailfrom; client-ip=212.159.14.18; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="jon@ffconsultancy.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@avasout06.plus.net) identity=helo; client-ip=212.159.14.18; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="postmaster@avasout06.plus.net"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArMBAHWa4lLUnw4SnGdsb2JhbABarguSRIENFg4BAQEBAQYNCQkUKIIlAQEBBAgCMD8NAwIJGC4ZIxsCBBMLBYd5yDYXjwwHhDgEjyieSg X-IPAS-Result: ArMBAHWa4lLUnw4SnGdsb2JhbABarguSRIENFg4BAQEBAQYNCQkUKIIlAQEBBAgCMD8NAwIJGC4ZIxsCBBMLBYd5yDYXjwwHhDgEjyieSg X-IronPort-AV: E=Sophos;i="4.95,713,1384297200"; d="scan'208";a="46029429" Received: from avasout06.plus.net ([212.159.14.18]) by mail3-smtp-sop.national.inria.fr with ESMTP; 24 Jan 2014 17:56:38 +0100 Received: from XPS ([91.125.112.34]) by avasout06 with smtp id Hswc1n0020kazHn01swd4D; Fri, 24 Jan 2014 16:56:37 +0000 X-CM-Score: 0.00 X-CNFS-Analysis: v=2.1 cv=IPI7VGfG c=1 sm=1 tr=0 a=DvnplZMz9B0OTucJM+SM4w==:117 a=DvnplZMz9B0OTucJM+SM4w==:17 a=0Bzu9jTXAAAA:8 a=XCxr5DcLagoA:10 a=Xub9RBUEA-sA:10 a=Kvk-SOs2Z7YA:10 a=kj9zAlcOel0A:10 a=r2vSxAw-AAAA:8 a=BR64nyZ84HQA:10 a=O-0No2N6Q5mDodl2q8AA:9 a=CjuIK1q_8ugA:10 a=d6ZO2ScF64gA:10 X-AUTH: jdh302:2500 Reply-To: From: "Jon Harrop" To: "'Andreas Rossberg'" Cc: "'Ocaml Mailing List'" References: <20140120101654.GI26447@frosties> <08bc01cf17b8$9263d070$b72b7150$@ffconsultancy.com> <20140123092925.GB20624@frosties> <01c401cf1891$b1fb1360$15f13a20$@ffconsultancy.com> <026101cf18dd$756c13d0$60443b70$@ffconsultancy.com> In-Reply-To: Date: Fri, 24 Jan 2014 16:56:46 -0000 Organization: Flying Frog Consultancy Ltd. Message-ID: <030501cf1925$45380fa0$cfa82ee0$@ffconsultancy.com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Outlook 14.0 Thread-Index: AQHI4li4v5YdVc3QG7JLKEaISEVTZQITm23GAs0uvsEBcUwfGALv8TtSARGMS8wBZ0wNRgGSGZD1Aq5lN6yaIKrPoA== Content-Language: en-gb Subject: RE: [Caml-list] How much optimized is the 'a option type ? On 24.01.2014 08:34, Andreas Rossberg wrote: > On Jan 24, 2014, at 09:22 , Jon Harrop wrote: >> With value types you can almost completely avoid the garbage >> collector by replacing pointers with indices into an array of value >> types that acts as a pool allocator. This can be useful for avoiding >> GC latency and for optimizing for collections that violate the >> generational hypothesis (e.g. >> long-lived Sets and Maps). > > As you well know, though, pervasive unboxing as for value types is > incompatible with a uniform representation approach like used by > OCaml. And non-uniform representation requires either static > monomorphisation (not possible in OCaml, because of first-class > polymorphism and separate compilation), or dynamic monomorphisation > (not possible without just-in-time compilation), or runtime type > passing and switching (expensive). I think there are halfway houses as well... Options could keep the same uniform representation when on the heap but be unboxed when they are stored locally (arguments, local variables and return values). You could either carry the pointer to the original option (if any) or re-allocate when it was needed. If run-time type passing and switching is expensive because of virtual dispatch then you could replace the dynamic jump with a test to see if the location is the same as it was for the last jump and, if so, use a static jump and then update just the static jump using JIT compilation. That requires JIT compilation but, perhaps, so little JIT compilation that the technique is of interest? The required run-time type information could just be the number of (uniformly-represented) words in each value and the "switch" could be a loop (that usually does only one iteration). For example, the "A of 'a | B of 'b * 'b | C" could be represented using 3 words per value instead of one: one for the tag A=1|B=2|C=3 and two for the two potential arguments. On a related note, doesn't OCaml box multiple return values as well? Could it use sret form and elide the write barrier instead? Even if such approaches don't improve overall performance they should shift the burden off the GC and onto the generated code which would make it easier to obtain good performance for alternative GC implementations (like OC4MC). Cheers, Jon.