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 ESMTPS id 8477B7EC6E for ; Mon, 27 Jan 2014 16:29:46 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of goswin-v-b@web.de) identity=pra; client-ip=212.227.15.14; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="goswin-v-b@web.de"; x-sender="goswin-v-b@web.de"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of goswin-v-b@web.de) identity=mailfrom; client-ip=212.227.15.14; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="goswin-v-b@web.de"; x-sender="goswin-v-b@web.de"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mout.web.de) identity=helo; client-ip=212.227.15.14; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="goswin-v-b@web.de"; x-sender="postmaster@mout.web.de"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjcCAFt65lLU4w8OnGdsb2JhbABZuyKFUIETFg4BAQEBAQYNCQkUKIIlAQEBAwE6RAsLGAklDwUoNIdwAQwMwFkfhg4XjxSDJIEUBJgmhjESjwo X-IPAS-Result: AjcCAFt65lLU4w8OnGdsb2JhbABZuyKFUIETFg4BAQEBAQYNCQkUKIIlAQEBAwE6RAsLGAklDwUoNIdwAQwMwFkfhg4XjxSDJIEUBJgmhjESjwo X-IronPort-AV: E=Sophos;i="4.95,729,1384297200"; d="scan'208";a="55054087" Received: from mout.web.de ([212.227.15.14]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES128-SHA; 27 Jan 2014 16:29:46 +0100 Received: from frosties.localnet ([37.49.32.119]) by smtp.web.de (mrweb101) with ESMTPSA (Nemesis) id 0MNLFd-1WEegq1oUL-006ypg for ; Mon, 27 Jan 2014 16:29:45 +0100 Received: from mrvn by frosties.localnet with local (Exim 4.80) (envelope-from ) id 1W7o88-0007gE-Mi for caml-list@inria.fr; Mon, 27 Jan 2014 16:29:44 +0100 Date: Mon, 27 Jan 2014 16:29:44 +0100 From: Goswin von Brederlow To: caml-list@inria.fr Message-ID: <20140127152944.GA29326@frosties> References: <20140120101654.GI26447@frosties> <08bc01cf17b8$9263d070$b72b7150$@ffconsultancy.com> <20140123092925.GB20624@frosties> <01c401cf1891$b1fb1360$15f13a20$@ffconsultancy.com> <026101cf18dd$756c13d0$60443b70$@ffconsultancy.com> <030501cf1925$45380fa0$cfa82ee0$@ffconsultancy.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <030501cf1925$45380fa0$cfa82ee0$@ffconsultancy.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-Provags-ID: V03:K0:ovO/Xgm8IefeMwb0JHdVzCakfnKhDsu0r0aIuHCSXrL90DWL2Te ks+xrs7SqEtrWmulwScKWuaCNYzAachQb5zrcNaZkaUzZa3nAudnlGLbFVW8Cy9puXDnoNc KlFL25t8zbcrvKTJ3d/7mNcbfvXacV5PRNzds3w+5X32E9RlXkRSoc0bbEeBXe7+qD2yo+L YoEUvFLR8myBQA0ioB/Tg== Subject: Re: [Caml-list] How much optimized is the 'a option type ? On Fri, Jan 24, 2014 at 04:56:46PM -0000, Jon Harrop wrote: > 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. They should certainly be unboxed when in registers. So let t = (23, 42.0) in would basically become let t_0 = 23 in (* r0 *) let t_1 = 42.0 in (* fpu0 *) Unless the tuple escapes the scope (either up or down) it should never be allocated. But you can't just put a float 42.0 on the heap or even stack when the GC might get called. That needs to be boxed in some way to avoid it getting misread as pointer. > 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? Or compile code poly-monomorphic. Meaning for a function taking/returning a tuple compile 2 (or more) flavours. One that allocates the tuple and one that passes the tuple in registers. Obviously higher level function would need a lot of flavours to cover all combinations. And closure would need multiple flavours too. But when there are too many cases, or when it is undecidable, the compiler can simply use the base case of allocaating everything like it does now. But all of this would be done static at compile time. > 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? There are never multiple return values. You can only return tuples. let f x y z = (x, y, z) let (x,y,z) = f 1 2 3 It would be nice not to allocate that tuple. Does ocaml allocate it? Or does inlining optimize the tuple away? > 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. MfG Goswin