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

[Gabriel Scherer <gabriel.scherer@gmail.com>]

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.

The OCaml GC is very good at optimizing *short-lived* allocations, so
many idiomatic uses of option are in fact already quite fast despite
the allocation. Using an `'a option array` for values that start
undefined is not one of such cases. Hopefully in fifteen years we'll
be using programming languages with well-typed strong update such as
Mezzo ( http://protz.github.io/mezzo/ ), that can solve this problem
without any kind of ad-hoc optimization.

On Fri, Jan 17, 2014 at 9:40 AM, David House <dhouse@janestreet.com> wrote:
> Err, right, sorry. If you have None in, say, a record, that's not allocated
> at all. Rather than there being a pointer in that field, there is special
> word in that field which represents None.
>
> If that field is a Some, then it's a pointer to a two word allocated block
> which in turn points at the actual thing. So compared to a C pointer, there
> an extra two words and one more indirection.
>
>
> On 17 January 2014 08:16, Julien Blond <julien.blond@gmail.com> wrote:
>>
>> > An option value always takes two words: one for the header, and then
>> > either a pointer or a word that means "None".
>>
>> No. From the reference manual § 19.3.4 :
>>
>> type 'a option = None           (* Val_int(0), i.e. just an integer value
>> = 1 word *)
>>                      | Some of 'a   (* block of size 1 = [(header = 1
>> word) + (1 field = 1 word)] = 2 words *)
>>
>>
>> 2014/1/17 David House <dhouse@janestreet.com>
>>>
>>> It behaves identically to that type.
>>>
>>> It is just like any other sum type. However, due to the way that sum
>>> types are represented in memory, it is not that inefficient. The only thing
>>> that makes it less efficient than a C pointer is the header block (necessary
>>> for the GC). An option value always takes two words: one for the header, and
>>> then either a pointer or a word that means "None".
>>>
>>>
>>> On 17 January 2014 07:35, Damien Guichard <alphablock@orange.fr> wrote:
>>>>
>>>> Hello,
>>>>
>>>> Compared to the code :
>>>>
>>>> type 'a option = None | Some of 'a
>>>>
>>>> How do an 'a option value performs ?
>>>> Any allocation saved ?
>>>> Any indirection removed ?
>>>>
>>>> Is 'a option just like any sum type ?
>>>> Or is 'a option more like an ANSI C pointer type ?
>>>>
>>>> Regards,
>>>>
>>>> Damien Guichard
>>>>
>>>>
>>>>
>>>> --
>>>> 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
>>>
>>>
>>
>