From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr 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 EA35F7F712 for ; Fri, 24 Jan 2014 11:16:44 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of alain@frisch.fr) identity=pra; client-ip=193.252.23.212; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="alain@frisch.fr"; x-sender="alain@frisch.fr"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of alain@frisch.fr) identity=mailfrom; client-ip=193.252.23.212; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="alain@frisch.fr"; x-sender="alain@frisch.fr"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@msa.smtpout.orange.fr) identity=helo; client-ip=193.252.23.212; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="alain@frisch.fr"; x-sender="postmaster@msa.smtpout.orange.fr"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnIBAEY84lLB/BfUnGdsb2JhbABRCb1MgwWBJA4BAQEBAQgLCQkUKIIlAQEBBCcRQAEQCxgJFg8JAwIBAgFFBgEMAQcBAYgFx3cXjh0IKDMHhDgBA5gmhkePBQ X-IPAS-Result: AnIBAEY84lLB/BfUnGdsb2JhbABRCb1MgwWBJA4BAQEBAQgLCQkUKIIlAQEBBCcRQAEQCxgJFg8JAwIBAgFFBgEMAQcBAYgFx3cXjh0IKDMHhDgBA5gmhkePBQ X-IronPort-AV: E=Sophos;i="4.95,712,1384297200"; d="scan'208";a="45973345" Received: from msa03.smtpout.orange.fr (HELO msa.smtpout.orange.fr) ([193.252.23.212]) by mail3-smtp-sop.national.inria.fr with ESMTP; 24 Jan 2014 11:16:44 +0100 Received: from [192.168.1.133] ([92.151.29.87]) by mwinf5d52 with ME id HmGj1n00Q1smU4k03mGjut; Fri, 24 Jan 2014 11:16:44 +0100 Message-ID: <52E23D8D.2030306@frisch.fr> Date: Fri, 24 Jan 2014 11:16:45 +0100 From: Alain Frisch User-Agent: Mozilla/5.0 (X11; Linux i686 on x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0 MIME-Version: 1.0 To: Gabriel Scherer , David House CC: Julien Blond , Damien Guichard , Caml Mailing List References: <523666417617602473@orange.fr> <52E23B0C.70502@frisch.fr> In-Reply-To: <52E23B0C.70502@frisch.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Caml-list] How much optimized is the 'a option type ? Revised description: there is no need to keep the tag on B or C values when applying the A constructor, and one can skip the 0 integer as the second field when applying the B/C constructor. B (x, y) ----> b0 = 1:(id_t,x, y) A (B (x, y)) ----> b1 = 0:(id_t, b0) C ----> c0 = 2:(id_t) A C ----> c1 = 0:(id_t, c0) This simplifies the criterion for checking if a value of type t has the B/C constructor (tag = 1 or 2) or the A constructor (tag = 0, and the argument is the second field of the block if the first is id_t, and the value itself otherwise). -- Alain On 01/24/2014 11:06 AM, Alain Frisch wrote: > On 01/17/2014 10:10 AM, Gabriel Scherer wrote: >> There have been recurrent discussions of optimizing `'a option` to >> avoid allocation in some cases, which is interesting when it is used >> as a default value for example. (The nice recent blog post by Thomas >> Leonard also seems to assume that `'a option` is somehow optimized.) >> >> My strictly personal opinion is that I doubt this would be a good >> idea, because I expect a fair share of the programming practice that >> currently use ('a option) to move to something like (('a, >> error-description) either) later in their lifetime, and I wouldn't >> want people to avoid to do that for performance concerns. >> Historically, we've rather come to see special-case representation >> optimizations (eg. array of floats) as a mistake -- but on the other >> hand there is not much downside to record of floats. > > It could be argued the role of option types is important enough to > justify a special treatment for them. But maybe one could think (just > for the fun of it) about a more general optimized representation for sum > types where one constructor should behave (mostly) as the identity at > runtime. > > To take an example, consider a type: > > type ('a, 'b) t = > | A of 'a > | B of 'b * 'b > | C > > with some marker to tell the compiler to optimize the representation of A. > > If one wants the constructor A to be the identity at runtime (in most > cases), we still need to distinguish C from A C, A (A C), A (A (A C)), > etc, and B (x, y) from A (B (x, y)), A (A (B (x, y))), etc. Here is > one possible implementation: let's allocate a fresh value to represent > the identity of the t type: > > id_t = 0:(0) > > that is, a block of size 1, tag 0, with a single 0 field (equivalent to: > id_t = ref ()). (This value would be generated by the compiler and > passed along in modules which re-export the type t.) > > The value (B (x, y)) would be represented as a block b0 = 1:(id_t, 0, x, > y) (block with tag 1 and 4 fields). Applying the A constructor to such > a block b0 would return a new block b1 = 1:(id_t, b0). Applying again > the A constructor to b1 would return b2 = 1:(id_t, b1). > > Similarly, the value C would be represented as a block c0 = 2:(id_t, 0). > Applying A to such a value would return a block c1 = 1:(id_t, c0), and > then c2 = 1:(id_t, c1). > > So, in general, applying the A constructor to a value x requires to > check if its argument is a block whose first field is equal to id_t, and > in this case, it returns a new block with the same tag and the two > fields id_t and x. In other cases, the constructors simply returns its > argument. > > With this representation, it is not difficult to deconstruct the three > constructors. For a value of type t: > > - If the value is a block whose first field is equal to id_t and its > second field is 0, then the value comes from the B or C constructor > (according to the block tag) and the arguments can be found in the block. > > - If the value is a block whose first first is equal to id_t and its > second field is not 0, then the value comes from the A constructor, and > the argument is the second field of the block. > > - Otherwise, the value comes from the A constructor and its argument > is represented by the same value. > > > There is one correctness problem with this representation, though: > applying the A constructor to a float value cannot be the identity, > because of the specific representation for float arrays (which is > triggered by checking if the value is a float block). This means we > must also have a special representation for A x, A (A x), etc, where x > is a float. The scheme above extends naturally to support this > representation: a0 = 0:(id_t, 0, x), a1 = 0:(id_t, a0), etc. > > > Another drawback is related to the use of the id_t block, which does not > work well with the generic marshaling, and requires extra plumbing to > make this value available where the type t can be constructed or > deconstructed. It's possible to do better for a type with a "global name". > > > In case of a constant constructor such as C, one can of course > pre-allocate the block c0 = 2:(id_t, 0). To avoid passing an extra > value around, one could store it within id_t itself (id_t = 0:(c0) > instead of id_t = 0:(0)). > > Another optimization is to avoid the allocation when applying the A > constructor several times to the same B or C value. This can be done by > memoization. One can add an extra field to all the blocks described > above, initialized to 0, and updated to point to the "next" application > of A when requested. > > So, we would have: > > c0 = 2:(id_t, 0, 0) > > When applying A to it, one create c1 > > c1 = 2:(id_t, c0, 0) > > and update the last field of c0 to be c1: > > c0 = 2:(id_t, 0, c1) > > If one needs to apply A again to c0, one can reuse the existing value. > The same applies to non-constant constructors as well. > > > > -- Alain >