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 E56757F712 for ; Fri, 24 Jan 2014 14:32:59 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of yminsky@janestreet.com) identity=pra; client-ip=38.105.200.229; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yminsky@janestreet.com"; x-sender="yminsky@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of yminsky@janestreet.com designates 38.105.200.229 as permitted sender) identity=mailfrom; client-ip=38.105.200.229; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yminsky@janestreet.com"; x-sender="yminsky@janestreet.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.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=mail3-smtp-sop.national.inria.fr; envelope-from="yminsky@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: AkkCADVq4lImacjlnGdsb2JhbABRCYNEVqh4imuIU4EDHg4BAQEBAQYWCTyCJQEBAQMBJxkBASwLAQQLCwsNDSEiEgEFAQoSBhMICodfAwkIAwIInyOLE4RSAQWTJgOFYBEGjikIVwQHhDiJTI5fgTKOfxgpgmyCCw X-IPAS-Result: AkkCADVq4lImacjlnGdsb2JhbABRCYNEVqh4imuIU4EDHg4BAQEBAQYWCTyCJQEBAQMBJxkBASwLAQQLCwsNDSEiEgEFAQoSBhMICodfAwkIAwIInyOLE4RSAQWTJgOFYBEGjikIVwQHhDiJTI5fgTKOfxgpgmyCCw X-IronPort-AV: E=Sophos;i="4.95,712,1384297200"; d="scan'208";a="45998884" Received: from mx5.janestreet.com (HELO tot-dmz-mxout1.janestreet.com) ([38.105.200.229]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 24 Jan 2014 14:32:58 +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 1W6gsR-0001c6-6q for caml-list@inria.fr; Fri, 24 Jan 2014 08:32:55 -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 1W6gsR-0006VQ-4o for caml-list@inria.fr; Fri, 24 Jan 2014 08:32:55 -0500 Received: from mail-la0-f46.google.com ([209.85.215.46]) by mxgoog2.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1W6gsQ-0000uI-No for caml-list@inria.fr; Fri, 24 Jan 2014 08:32:54 -0500 Received: by mail-la0-f46.google.com with SMTP id b8so2526850lan.5 for ; Fri, 24 Jan 2014 05:32:54 -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=iKaCitgzk53UVjzMRAcGGET6IYCuHqn9R8MHS2MPaps=; b=cRgwSfAzB65feb+Xt+4+OzYleoCBuooiEtuJwuyoMFAshwmo4u75d8fEvmkIzTQalT hP3usihiaWZVQFWsL9peepyytK8lYJLDEsjSfTfF+LJsemIssfaBu2mfzV/nH3hYWSLl 5gk6Jz/cbe1Q1511xgzsz2xA8hdaYgVWZRLRA= 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=iKaCitgzk53UVjzMRAcGGET6IYCuHqn9R8MHS2MPaps=; b=AR1HlR1Y/NLj8ke4Ws+VNmk/qPgFmHJuvd1CkDgMrc9DMWiuL+GyHdFtvZhYYMDBMb gLb5Drw2EC6fa2fop39XMx0Wi5dMXhyi860vzuUphqqGxLftTwiSB5mQqyj3an8I87KF wSR/OKKE9vsPcaC4IAdib/vN+4yMBVh5HMRXn6QccYp3/XXlruNNI3kvx0EN7g2ofMQe OOmtyOMkD2pDao1yeQzTn0JtFYTcu8KkYfJLhNuwelwbm3XuSxZz3Lk8hyrwS5BPPGbl sqZJF6GvLVI0xea0xdG+i3Z3rzU+t50gNbMfO6BWaqu7zHemVu6XqD9Q4Dq4VTp2/UAh SnKQ== X-Gm-Message-State: ALoCoQm2+RDJFPy8IQAkcZd1Nz2bXTu2tIZPhvu5FOP1UitBGM/rdFC4dDmAYTd6Q48BwZmWSMiEjxMasEi9b3etFrwY9P9FWu5nK2x+jERJk0Pib1tSzfqX0iY8iedeBv+JKC5tIZI4BBIE8SVzSY0i+1GGcy+aGw== X-Received: by 10.153.3.2 with SMTP id bs2mr2414034lad.5.1390570374069; Fri, 24 Jan 2014 05:32:54 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.153.3.2 with SMTP id bs2mr2414020lad.5.1390570373941; Fri, 24 Jan 2014 05:32:53 -0800 (PST) Received: by 10.112.5.70 with HTTP; Fri, 24 Jan 2014 05:32:53 -0800 (PST) Received: by 10.112.5.70 with HTTP; Fri, 24 Jan 2014 05:32:53 -0800 (PST) In-Reply-To: <52E23D8D.2030306@frisch.fr> References: <523666417617602473@orange.fr> <52E23B0C.70502@frisch.fr> <52E23D8D.2030306@frisch.fr> Date: Fri, 24 Jan 2014 08:32:53 -0500 Message-ID: From: Yaron Minsky To: Alain Frisch Cc: Gabriel Scherer , Damien Guichard , Julien Blond , David House , Caml Mailing List Content-Type: multipart/alternative; boundary=001a1136c7422c9f1904f0b7659d Subject: Re: [Caml-list] How much optimized is the 'a option type ? --001a1136c7422c9f1904f0b7659d Content-Type: text/plain; charset=ISO-8859-1 I really do think that if the engineering challenges can be overcome, this would be a very useful representation to have on hand. There are many situations where the only way to get a sufficiently light memory representation is to use hand coded hacks that try to implement similar schemes using the Obj module. It wound be far better to have this as a first class part of the language. On Jan 24, 2014 5:16 AM, "Alain Frisch" wrote: > 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 >> >> > > -- > 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 > --001a1136c7422c9f1904f0b7659d Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

I really do think that if the engineering challenges can be = overcome, this would be a very useful representation to have on hand. There= are many situations where the only way to get a sufficiently light memory = representation is to use hand coded hacks that try to implement similar sch= emes using the Obj module.=A0 It wound be far better to have this as a firs= t class part of the language.

On Jan 24, 2014 5:16 AM, "Alain Frisch"= ; <alain@frisch.fr> wrote:
Revised description: =A0there is no need to keep the tag on B or C values w= hen applying the A constructor, and one can skip the 0 integer as the secon= d field when applying the B/C constructor.

=A0 =A0B (x, y) =A0 ----> =A0 b0 =3D 1:(id_t,x, y)
A (B (x, y)) =A0----> =A0 b1 =3D 0:(id_t, b0)

=A0 =A0C =A0 =A0 =A0 =A0 =A0----> =A0 c0 =3D 2:(id_t)
A =A0C =A0 =A0 =A0 =A0 =A0----> =A0 c1 =3D 0:(id_t, c0)


This simplifies the criterion for checking if a value of type t has the B/C= constructor (tag =3D 1 or 2) or the A constructor (tag =3D 0, and the argu= ment is the second field of the block if the first is id_t, and the value i= tself 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. =A0But 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:

=A0 =A0type ('a, 'b) t =3D
=A0 =A0 =A0 | A of 'a
=A0 =A0 =A0 | B of 'b * 'b
=A0 =A0 =A0 | C

with some marker to tell the compiler to optimize the representation of A.<= br>
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, =A0and B (x, y) from A (B (x, y)), A (A (B (x, y))), etc. =A0Here is one possible implementation: =A0let's allocate a fresh value to represe= nt
the identity of the t type:

=A0 =A0id_t =3D 0:(0)

that is, a block of size 1, tag 0, with a single 0 field (equivalent to:
id_t =3D ref ()). =A0(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 =3D 1:(id_t, 0, x,<= br> y) =A0(block with tag 1 and 4 fields). =A0Applying the A constructor to suc= h
a block b0 would return a new block b1 =3D 1:(id_t, b0). =A0Applying again<= br> the A constructor to b1 would return b2 =3D 1:(id_t, b1).

Similarly, the value C would be represented as a block c0 =3D 2:(id_t, 0).<= br> =A0 Applying A to such a value would return a block c1 =3D 1:(id_t, c0), an= d
then c2 =3D 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. =A0In other cases, the constructors simply returns its argument.

With this representation, it is not difficult to deconstruct the three
constructors. =A0For a value of type t:

=A0 - 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.
=A0 - 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.

=A0 - 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). =A0This means we
must also have a special representation for A x, A (A x), etc, where x
is a float. =A0The scheme above extends naturally to support this
representation: =A0a0 =3D 0:(id_t, 0, x), a1 =3D 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. =A0It's possible to do better for a type with a "gl= obal name".


In case of a constant constructor such as C, one can of course
pre-allocate the block c0 =3D 2:(id_t, 0). =A0To avoid passing an extra
value around, one could store it within id_t itself (id_t =3D 0:(c0)
instead of id_t =3D 0:(0)).

Another optimization is to avoid the allocation when applying the A
constructor several times to the same B or C value. =A0This can be done by<= br> memoization. =A0One can add an extra field to all the blocks described
above, initialized to 0, and updated to point to the "next" appli= cation
of A when requested.

So, we would have:

=A0 =A0c0 =3D 2:(id_t, 0, 0)

When applying A to it, one create c1

=A0 =A0c1 =3D 2:(id_t, c0, 0)

and update the last field of c0 to be c1:

=A0 =A0c0 =3D 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



--
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<= /a>
Bug reports: http://caml.inria.fr/bin/caml-bugs
--001a1136c7422c9f1904f0b7659d--