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

["Jon Harrop" <jon@ffconsultancy.com>]

> The OCaml GC is very good at optimizing *short-lived* allocations

I see lots of people still asserting that. I think it needs quantifying.
AFAIK, OCaml's GC makes short-lived values 2-3x faster than long lived
values or malloc/free but removing unnecessary short lived allocations can
often make a function several times faster. So I think there is every reason
to optimize away allocations even if they are short-lived. Obvious examples
include optional arguments, options, tuples and complex numbers.

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

FWIW, I think value types and reified generics already solved this problem
(and many other related problems).

Cheers,
Jon.

-----Original Message-----
From: caml-list-request@inria.fr [mailto:caml-list-request@inria.fr] On
Behalf Of Gabriel Scherer
Sent: 17 January 2014 09:10
To: David House
Cc: Julien Blond; Damien Guichard; Caml Mailing List
Subject: Re: [Caml-list] How much optimized is the 'a option type ?

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
>>>
>>>
>>
>

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