Re: [Caml-list] How much optimized is the 'a option type ?

[Yaron Minsky <yminsky@janestreet.com>]

[-- Attachment #1: Type: text/plain, Size: 6498 bytes --]

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" <alain@frisch.fr> 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
>

[-- Attachment #2: Type: text/html, Size: 7610 bytes --]