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

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

[Damien Guichard]

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

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

[David House]

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

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
>

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

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

[Julien Blond]

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

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

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

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

[David House]

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

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

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

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

[Gabriel Scherer]

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

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

[David House]

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

My attachment got rejected by the list. http://imgur.com/de9SBnA


On 17 January 2014 09:09, David House <dhouse@janestreet.com> wrote:

> Here's some high-tech computer visualisation to illustrate this.
>
>
> On 17 January 2014 08:40, 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
>>>>>
>>>>
>>>>
>>>
>>
>

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

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

[Simon Cruanes]

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

Le Fri, 17 Jan 2014, Gabriel Scherer a écrit :

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

I think optimization of some local uses of options, such as:

let rec iter_stream f s =
    match (try Some (MyStream.get s) with End_of_stream -> None) with
    | None -> ()
    | Some (x, s') ->
        f x;
        iter_stream f s'

where an option is used to keep the function tail-rec (I've heard
several people tell me they often need to use this), or other cases like
optional parameters (which are not going to move to Either), would be
useful and future-proof. I hope the current work on optimizations will
help with this kind of cases (removing useless allocations of local
options, references, exceptions when no escape is possible).

</wishlist>
</2cents>
</</>>

-- 
Simon

[-- Attachment #2: Type: application/pgp-signature, Size: 819 bytes --]

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

[Jonathan Kimmitt]

In my humble opinion the main purpose of Some _ | None is to avoid the
requirement for a nil pointer in OCaml. If an external function wants to
return nil in order to indicate, for example that a certain resource is not
available, it can return None instead and this prevents dereferencing a nil
pointer in OCaml because the None cannot be dereferenced. If you compare this
behaviour with the inferior clone F# written by Microsoft, you can see that
one of the things they added to the language was a nil pointer, thus
abandoning all type safety immediately and all because they did not want to
change their .NET runtime system for C# etc. They also have the notion of
initialising a typed object to in an invalid default, which is another obvious
disaster area. Oh and did I mention operators like +/- etc are overloaded so
you cannot infer function types without adding type annotations.
The final insult is to make indentation significant in the syntax so that if
you post a program to a list which does not respect whitespace (for example
using a well-known Microsoft mail client), it completely destroys the meaning
of the program.

I'm sure the authors of F# have their reasons for making all these changes,
and I'm not one to stand in the way of progress, and I don't set out to offend
anybody, but I think they got it wrong ...

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

[Nicolas Braud-Santoni]

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

On 17/01/2014 12:23, Jonathan Kimmitt wrote:
> In my humble opinion the main purpose of Some _ | None is to avoid the
> requirement for a nil pointer in OCaml. If an external function wants to
> return nil in order to indicate, for example that a certain resource is not
> available, it can return None instead and this prevents dereferencing a nil
> pointer in OCaml because the None cannot be dereferenced.
Yes.
This doesn't forbid the compiler from representing 'a option values as
pointers.
Indeed, the type system already enforces that the None case is handled
and the representation of None and Some _ do not matter.

That said, I agree with Gabriel Scherer : adding optimizations specific
to 'a option might refrain people wanting to switch to more appropriate
datatypes.
However, would is be possible to “optimize away” all types of the form
“type 'a t = X of 'a | A | B | ...” (with at most one non-constant
constructor) ?
Would it be worth doing ?


Kind regards,
Nicolas


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[Frédéric Bour]

Le 17/01/2014 14:46, Nicolas Braud-Santoni a écrit :
> On 17/01/2014 12:23, Jonathan Kimmitt wrote:
>> In my humble opinion the main purpose of Some _ | None is to avoid the
>> requirement for a nil pointer in OCaml. If an external function wants to
>> return nil in order to indicate, for example that a certain resource is not
>> available, it can return None instead and this prevents dereferencing a nil
>> pointer in OCaml because the None cannot be dereferenced.
> Yes.
> This doesn't forbid the compiler from representing 'a option values as
> pointers.
> Indeed, the type system already enforces that the None case is handled
> and the representation of None and Some _ do not matter.
>
> That said, I agree with Gabriel Scherer : adding optimizations specific
> to 'a option might refrain people wanting to switch to more appropriate
> datatypes.
> However, would is be possible to “optimize away” all types of the form
> “type 'a t = X of 'a | A | B | ...” (with at most one non-constant
> constructor) ?
> Would it be worth doing ?

This won't work when used with 'a = another type with constant constructors.
And what about 'a 'a t?

Sticking to a uniform representation prevents a lot of problem.

> Kind regards,
> Nicolas

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

[Yaron Minsky]

I also agree with Gabriel that an option-specific optimization is not
clearly the right move.

But I wonder if a more general optimization that provided the
possibility of minting "fast-path" variants.  i.e., one could have an
annotation that marked a given branch of a variant as the
"no-indirection" one, i.e., the one that doesn't lead to the
allocation of an extra block:

type ('a,'b) result =
     | Ok of 'a [@@no_indirection]
     | Error of 'b

would lead to a type where [Ok x == x].  Some cleverness is required
then for the representation of the [Error] branch.  In particular,
you'd need some dynamic test you could run to see if you were using a
value that was not the fast-path one.

The thing that I don't know if there's a solution for is the nesting
problem.  i.e., can you effectively distinguish:

  Ok (Ok (Error x))

from

  Error x

since they would have the same physical representation.  I'm not sure
if some variant of the counting trick used for options would work here
or not.  But if you could get this, it would make it possible to avoid
a large number of dirty Obj.magic hacks that people need to do to
build efficient datastructures in practice.  The fact that the stdlib
needs to use Obj.magic to get the necessary performance is, I think, a
sign that something important is missing from the language.  I'm not
sure if this is quite it, to be clear.

y


On Fri, Jan 17, 2014 at 8:46 AM, Nicolas Braud-Santoni
<nicolas.braudsantoni@gmail.com> wrote:
> On 17/01/2014 12:23, Jonathan Kimmitt wrote:
>> In my humble opinion the main purpose of Some _ | None is to avoid the
>> requirement for a nil pointer in OCaml. If an external function wants to
>> return nil in order to indicate, for example that a certain resource is not
>> available, it can return None instead and this prevents dereferencing a nil
>> pointer in OCaml because the None cannot be dereferenced.
> Yes.
> This doesn't forbid the compiler from representing 'a option values as
> pointers.
> Indeed, the type system already enforces that the None case is handled
> and the representation of None and Some _ do not matter.
>
> That said, I agree with Gabriel Scherer : adding optimizations specific
> to 'a option might refrain people wanting to switch to more appropriate
> datatypes.
> However, would is be possible to “optimize away” all types of the form
> “type 'a t = X of 'a | A | B | ...” (with at most one non-constant
> constructor) ?
> Would it be worth doing ?
>
>
> Kind regards,
> Nicolas
>

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

[Simon Cruanes]

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

Le Fri, 17 Jan 2014, Yaron Minsky a écrit :
> I also agree with Gabriel that an option-specific optimization is not
> clearly the right move.
> 
> But I wonder if a more general optimization that provided the
> possibility of minting "fast-path" variants.  i.e., one could have an
> annotation that marked a given branch of a variant as the
> "no-indirection" one, i.e., the one that doesn't lead to the
> allocation of an extra block:
> 
> type ('a,'b) result =
>      | Ok of 'a [@@no_indirection]
>      | Error of 'b
> 
> would lead to a type where [Ok x == x].  Some cleverness is required
> then for the representation of the [Error] branch.  In particular,
> you'd need some dynamic test you could run to see if you were using a
> value that was not the fast-path one.
> 
> The thing that I don't know if there's a solution for is the nesting
> problem.  i.e., can you effectively distinguish:
> 
>   Ok (Ok (Error x))
> 
> from
> 
>   Error x
> 
> since they would have the same physical representation.  I'm not sure
> if some variant of the counting trick used for options would work here
> or not.  But if you could get this, it would make it possible to avoid
> a large number of dirty Obj.magic hacks that people need to do to
> build efficient datastructures in practice.  The fact that the stdlib
> needs to use Obj.magic to get the necessary performance is, I think, a
> sign that something important is missing from the language.  I'm not
> sure if this is quite it, to be clear.

Maybe I'm stating the obvious, but wouldn't value types be the general
solution here? Assuming the optimizer can guarantee that the option
value will not outlive the current scope, the value can be allocated on
the stack or in registers. That's probably fast enough for most uses,
isn't it? I think rust deals with option values exactly this way.


-- 
Simon

[-- Attachment #2: Type: application/pgp-signature, Size: 819 bytes --]

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

[Gabriel Scherer]

> The fact that the stdlib
> needs to use Obj.magic to get the necessary performance is, I think, a
> sign that something important is missing from the language.

I think this specific example needs to die. Yes, there is an Obj.magic
in the implementation of Queue, and this mistake was committed more
than a decade ago. But we could perfectly remove this use of Obj.magic
and use different implementation techniques to get equally efficient
(or better) code. But there is no reason to change code that works
well enough.

That some Obj.magic remains in some old code is *no excuse* to use it
today or tomorrow.

On Fri, Jan 17, 2014 at 3:02 PM, Yaron Minsky <yminsky@janestreet.com> wrote:
> I also agree with Gabriel that an option-specific optimization is not
> clearly the right move.
>
> But I wonder if a more general optimization that provided the
> possibility of minting "fast-path" variants.  i.e., one could have an
> annotation that marked a given branch of a variant as the
> "no-indirection" one, i.e., the one that doesn't lead to the
> allocation of an extra block:
>
> type ('a,'b) result =
>      | Ok of 'a [@@no_indirection]
>      | Error of 'b
>
> would lead to a type where [Ok x == x].  Some cleverness is required
> then for the representation of the [Error] branch.  In particular,
> you'd need some dynamic test you could run to see if you were using a
> value that was not the fast-path one.
>
> The thing that I don't know if there's a solution for is the nesting
> problem.  i.e., can you effectively distinguish:
>
>   Ok (Ok (Error x))
>
> from
>
>   Error x
>
> since they would have the same physical representation.  I'm not sure
> if some variant of the counting trick used for options would work here
> or not.  But if you could get this, it would make it possible to avoid
> a large number of dirty Obj.magic hacks that people need to do to
> build efficient datastructures in practice.  The fact that the stdlib
> needs to use Obj.magic to get the necessary performance is, I think, a
> sign that something important is missing from the language.  I'm not
> sure if this is quite it, to be clear.
>
> y
>
>
> On Fri, Jan 17, 2014 at 8:46 AM, Nicolas Braud-Santoni
> <nicolas.braudsantoni@gmail.com> wrote:
>> On 17/01/2014 12:23, Jonathan Kimmitt wrote:
>>> In my humble opinion the main purpose of Some _ | None is to avoid the
>>> requirement for a nil pointer in OCaml. If an external function wants to
>>> return nil in order to indicate, for example that a certain resource is not
>>> available, it can return None instead and this prevents dereferencing a nil
>>> pointer in OCaml because the None cannot be dereferenced.
>> Yes.
>> This doesn't forbid the compiler from representing 'a option values as
>> pointers.
>> Indeed, the type system already enforces that the None case is handled
>> and the representation of None and Some _ do not matter.
>>
>> That said, I agree with Gabriel Scherer : adding optimizations specific
>> to 'a option might refrain people wanting to switch to more appropriate
>> datatypes.
>> However, would is be possible to “optimize away” all types of the form
>> “type 'a t = X of 'a | A | B | ...” (with at most one non-constant
>> constructor) ?
>> Would it be worth doing ?
>>
>>
>> Kind regards,
>> Nicolas
>>
>
> --
> 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

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

[Markus Mottl]

Others have already answered about memory representation, but there is
one thing about allocations that many OCaml programmers may not yet be
aware of and that can make a noticeable performance difference when
used wisely: the OCaml compiler will inspect your code and, under the
right conditions, batch together allocations.  E.g. consider this
function (references are records, btw.):

  let f n =
    let x = ref (ref (Some (Some n))) in
    [(x, n); (x, n)]

One might naively assume that this would lead to seven or so
allocations.  But if you inspect the assembly, you'll see only one
allocation followed by mere initialization assignments.

Such allocation batches can break if, for example, the code calls
non-inlined (e.g. recursive or external) functions.  I'm not quite
sure about all the rules there, but it's generally trivial to just
look at the assembler output to find out what the compiler is doing.
In some cases merely calling all functions before any allocations take
place can speed up your code.  There are even cases where it may be
more efficient to allocate several values in one chunk though only
some may be needed depending on branches taken later.

Regards,
Markus

On Fri, Jan 17, 2014 at 2:35 AM, 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



-- 
Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com

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

[Yotam Barnoy]

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

That reminds me -- what is the situation regarding inlining? Is there work
being done on inlining from other modules? Is heavy inlining being done
within a module? Would it be possible to annotate with [@@inline] to give
hints to the compiler at some point?

-Yotam


On Fri, Jan 17, 2014 at 9:36 AM, Markus Mottl <markus.mottl@gmail.com>wrote:

> Others have already answered about memory representation, but there is
> one thing about allocations that many OCaml programmers may not yet be
> aware of and that can make a noticeable performance difference when
> used wisely: the OCaml compiler will inspect your code and, under the
> right conditions, batch together allocations.  E.g. consider this
> function (references are records, btw.):
>
>   let f n =
>     let x = ref (ref (Some (Some n))) in
>     [(x, n); (x, n)]
>
> One might naively assume that this would lead to seven or so
> allocations.  But if you inspect the assembly, you'll see only one
> allocation followed by mere initialization assignments.
>
> Such allocation batches can break if, for example, the code calls
> non-inlined (e.g. recursive or external) functions.  I'm not quite
> sure about all the rules there, but it's generally trivial to just
> look at the assembler output to find out what the compiler is doing.
> In some cases merely calling all functions before any allocations take
> place can speed up your code.  There are even cases where it may be
> more efficient to allocate several values in one chunk though only
> some may be needed depending on branches taken later.
>
> Regards,
> Markus
>
> On Fri, Jan 17, 2014 at 2:35 AM, 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
>
>
>
> --
> Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com
>
> --
> 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: 3934 bytes --]

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

[Markus Mottl]

Cross-module inlining (even across compilation units) is already
supported.  I guess what you mean is whether functor arguments are
inlined, which is not yet the case.  There has been some recent work
on this:

  http://www.ocamlpro.com/blog/2013/07/11/inlining-progress-report.html

I'd really love to see something like that in the compiler.

Regards,
Markus

On Fri, Jan 17, 2014 at 10:49 AM, Yotam Barnoy <yotambarnoy@gmail.com> wrote:
> That reminds me -- what is the situation regarding inlining? Is there work
> being done on inlining from other modules? Is heavy inlining being done
> within a module? Would it be possible to annotate with [@@inline] to give
> hints to the compiler at some point?
>
> -Yotam
>
>
> On Fri, Jan 17, 2014 at 9:36 AM, Markus Mottl <markus.mottl@gmail.com>
> wrote:
>>
>> Others have already answered about memory representation, but there is
>> one thing about allocations that many OCaml programmers may not yet be
>> aware of and that can make a noticeable performance difference when
>> used wisely: the OCaml compiler will inspect your code and, under the
>> right conditions, batch together allocations.  E.g. consider this
>> function (references are records, btw.):
>>
>>   let f n =
>>     let x = ref (ref (Some (Some n))) in
>>     [(x, n); (x, n)]
>>
>> One might naively assume that this would lead to seven or so
>> allocations.  But if you inspect the assembly, you'll see only one
>> allocation followed by mere initialization assignments.
>>
>> Such allocation batches can break if, for example, the code calls
>> non-inlined (e.g. recursive or external) functions.  I'm not quite
>> sure about all the rules there, but it's generally trivial to just
>> look at the assembler output to find out what the compiler is doing.
>> In some cases merely calling all functions before any allocations take
>> place can speed up your code.  There are even cases where it may be
>> more efficient to allocate several values in one chunk though only
>> some may be needed depending on branches taken later.
>>
>> Regards,
>> Markus
>>
>> On Fri, Jan 17, 2014 at 2:35 AM, 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
>>
>>
>>
>> --
>> Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com
>>
>> --
>> 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
>
>



-- 
Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com

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

[Gerd Stolpmann]

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

Am Freitag, den 17.01.2014, 10:22 +0100 schrieb Simon Cruanes:
> Le Fri, 17 Jan 2014, Gabriel Scherer a écrit :
> 
> > 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.
> 
> I think optimization of some local uses of options, such as:

I also think that local uses of options (and other variant types) could
be candidates for optimization. Gabriel is right that the GC is good at
short-living values, but that still leaves room for getting better with
ultra-short-living values.

My idea would be to try to delay the allocation of the block, and to use
two registers, i.e. one for the tag, and one for the tagged inner value.
First when the constructed value is passed to some other function, or
returned, or stored inside another block, or in another register, the
allocation is really done. Of course, this could also result in more
work in total (especially when the compiler has no idea what the desired
fast path of the algorithm is), and I guess the real problem is that you
need a good heuristics to decide when to do this. But there are at least
two criterions at hand:

 - You are not under pressure with registers
 - All consumers of the constructed value are inside the same function

I guess this would result in a quite heavy patch for the comparatively
small effect, and that's why it is not yet done.


Gerd


> let rec iter_stream f s =
>     match (try Some (MyStream.get s) with End_of_stream -> None) with
>     | None -> ()
>     | Some (x, s') ->
>         f x;
>         iter_stream f s'
> 
> where an option is used to keep the function tail-rec (I've heard
> several people tell me they often need to use this), or other cases like
> optional parameters (which are not going to move to Either), would be
> useful and future-proof. I hope the current work on optimizations will
> help with this kind of cases (removing useless allocations of local
> options, references, exceptions when no escape is possible).
> 
> </wishlist>
> </2cents>
> </</>>
> 

-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

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

[Yaron Minsky]

I agree that representation hacking (which is what Obj.magic is all
about) is something that should be done rarely, and I don't think the
Queue example justifies it.  There are other hacks, though, that make
sense, like the hack for lazy values, which I think is totally worth
it.

We've had to do a number of Obj.magic hacks in Core_kernel to get it
to perform adequately.  I think those hacks are a reasonably good
place to look for inspiration as to how to make OCaml more hospitable
for those with stringent performance requirements.

For what it's worth, GADTs have been a big win in this regard, by
making access to existentials cheap and easy, which can avoid a lot of
pointless allocation of closures in complex libraries.  I'd like to
see this improve yet further by allowing for existential values to be
created without an extra allocated block, which the GADT approach
currently requires.

If you're interested, you can look at Core_stack, Flat_queue, Dequeue
and Pool to see some examples where we've needed to use Obj.magic for
performance reasons.

y

On Fri, Jan 17, 2014 at 9:24 AM, Gabriel Scherer
<gabriel.scherer@gmail.com> wrote:
>> The fact that the stdlib
>> needs to use Obj.magic to get the necessary performance is, I think, a
>> sign that something important is missing from the language.
>
> I think this specific example needs to die. Yes, there is an Obj.magic
> in the implementation of Queue, and this mistake was committed more
> than a decade ago. But we could perfectly remove this use of Obj.magic
> and use different implementation techniques to get equally efficient
> (or better) code. But there is no reason to change code that works
> well enough.
>
> That some Obj.magic remains in some old code is *no excuse* to use it
> today or tomorrow.
>
> On Fri, Jan 17, 2014 at 3:02 PM, Yaron Minsky <yminsky@janestreet.com> wrote:
>> I also agree with Gabriel that an option-specific optimization is not
>> clearly the right move.
>>
>> But I wonder if a more general optimization that provided the
>> possibility of minting "fast-path" variants.  i.e., one could have an
>> annotation that marked a given branch of a variant as the
>> "no-indirection" one, i.e., the one that doesn't lead to the
>> allocation of an extra block:
>>
>> type ('a,'b) result =
>>      | Ok of 'a [@@no_indirection]
>>      | Error of 'b
>>
>> would lead to a type where [Ok x == x].  Some cleverness is required
>> then for the representation of the [Error] branch.  In particular,
>> you'd need some dynamic test you could run to see if you were using a
>> value that was not the fast-path one.
>>
>> The thing that I don't know if there's a solution for is the nesting
>> problem.  i.e., can you effectively distinguish:
>>
>>   Ok (Ok (Error x))
>>
>> from
>>
>>   Error x
>>
>> since they would have the same physical representation.  I'm not sure
>> if some variant of the counting trick used for options would work here
>> or not.  But if you could get this, it would make it possible to avoid
>> a large number of dirty Obj.magic hacks that people need to do to
>> build efficient datastructures in practice.  The fact that the stdlib
>> needs to use Obj.magic to get the necessary performance is, I think, a
>> sign that something important is missing from the language.  I'm not
>> sure if this is quite it, to be clear.
>>
>> y
>>
>>
>> On Fri, Jan 17, 2014 at 8:46 AM, Nicolas Braud-Santoni
>> <nicolas.braudsantoni@gmail.com> wrote:
>>> On 17/01/2014 12:23, Jonathan Kimmitt wrote:
>>>> In my humble opinion the main purpose of Some _ | None is to avoid the
>>>> requirement for a nil pointer in OCaml. If an external function wants to
>>>> return nil in order to indicate, for example that a certain resource is not
>>>> available, it can return None instead and this prevents dereferencing a nil
>>>> pointer in OCaml because the None cannot be dereferenced.
>>> Yes.
>>> This doesn't forbid the compiler from representing 'a option values as
>>> pointers.
>>> Indeed, the type system already enforces that the None case is handled
>>> and the representation of None and Some _ do not matter.
>>>
>>> That said, I agree with Gabriel Scherer : adding optimizations specific
>>> to 'a option might refrain people wanting to switch to more appropriate
>>> datatypes.
>>> However, would is be possible to “optimize away” all types of the form
>>> “type 'a t = X of 'a | A | B | ...” (with at most one non-constant
>>> constructor) ?
>>> Would it be worth doing ?
>>>
>>>
>>> Kind regards,
>>> Nicolas
>>>
>>
>> --
>> 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

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

[Yaron Minsky]

I don't think it's enough.  Quite often these values are long-lived
enough that the analysis for short-lived objects would not help.
Short lived allocations are considerably cheaper anyway, so the bigger
win is on allocations that make it to the major heap.

Representation hacking has good uses.  Lazy is a fine example, where
lazy values are made considerably cheaper by the fact that OCaml
removes the extra level of indirection when a lazy is forced.

Not all representation hacks have worked out so well, I would argue.
I think there's relatively wide agreement that we'd be better off
without the float hack for arrays.  It complicates lots of things,
including the lazy hack!

y

On Fri, Jan 17, 2014 at 9:09 AM, Simon Cruanes
<simon.cruanes.2007@m4x.org> wrote:
> Le Fri, 17 Jan 2014, Yaron Minsky a écrit :
>> I also agree with Gabriel that an option-specific optimization is not
>> clearly the right move.
>>
>> But I wonder if a more general optimization that provided the
>> possibility of minting "fast-path" variants.  i.e., one could have an
>> annotation that marked a given branch of a variant as the
>> "no-indirection" one, i.e., the one that doesn't lead to the
>> allocation of an extra block:
>>
>> type ('a,'b) result =
>>      | Ok of 'a [@@no_indirection]
>>      | Error of 'b
>>
>> would lead to a type where [Ok x == x].  Some cleverness is required
>> then for the representation of the [Error] branch.  In particular,
>> you'd need some dynamic test you could run to see if you were using a
>> value that was not the fast-path one.
>>
>> The thing that I don't know if there's a solution for is the nesting
>> problem.  i.e., can you effectively distinguish:
>>
>>   Ok (Ok (Error x))
>>
>> from
>>
>>   Error x
>>
>> since they would have the same physical representation.  I'm not sure
>> if some variant of the counting trick used for options would work here
>> or not.  But if you could get this, it would make it possible to avoid
>> a large number of dirty Obj.magic hacks that people need to do to
>> build efficient datastructures in practice.  The fact that the stdlib
>> needs to use Obj.magic to get the necessary performance is, I think, a
>> sign that something important is missing from the language.  I'm not
>> sure if this is quite it, to be clear.
>
> Maybe I'm stating the obvious, but wouldn't value types be the general
> solution here? Assuming the optimizer can guarantee that the option
> value will not outlive the current scope, the value can be allocated on
> the stack or in registers. That's probably fast enough for most uses,
> isn't it? I think rust deals with option values exactly this way.
>
>
> --
> Simon

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

[Jon Harrop]

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

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

[Jon Harrop]

Jonathan Kimmitt wrote:
> If you compare this behaviour with the inferior clone F# written by
Microsoft,
> you can see that one of the things they added to the language was a nil
> pointer, thus abandoning all type safety immediately and all because they
> did not want to change their .NET runtime system for C# etc.

F# has a very good FFI to C#. In particular, it is memory safe. F# has null
because it is required for interop with C#. Idiomatic F# code does not use
null. Compare with OCaml's memory-unsafe FFI to C...

> They also have the notion of initialising a typed object to in an invalid
default,
> which is another obvious disaster area.

When you dequeue an element from a mutable queue that is represented
internally as an over-sized array you need to null-out the removed element
or you leak everything reachable from that value that would otherwise be
unreachable. F# uses Unchecked.defaultof<_> to create a default value of any
type (even a value type). The Queue module in the OCaml stdlib uses
"Obj.magic None" which works because OCaml doesn't have value types.

> Oh and did I mention operators like +/- etc are overloaded so you cannot
> infer function types without adding type annotations.

In F# the same arithmetic operators work transparently on the byte, sbyte,
uint16, int16, uint32, int32, uint64, int64, float, float32, BigInteger and
BigRational types as well as decimal, DateTime, vectors, matrices and
user-defined types. OCaml has + for int, +. for float and +/ for big
rationals and no other numeric types. Imagine what would happen if OCaml
supported just the full complement of numeric types, let alone the others?
You'd need 15 different operators just to support the numeric types I
listed...

> The final insult is to make indentation significant in the syntax so that
if
> you post a program to a list which does not respect whitespace (for
> example using a well-known Microsoft mail client), it completely destroys
> the meaning of the program.

I agree. :-)

Cheers,
Jon.

-----Original Message-----
From: caml-list-request@inria.fr [mailto:caml-list-request@inria.fr] On
Behalf Of Jonathan Kimmitt
Sent: 17 January 2014 11:24
To: caml-list@inria.fr
Subject: Re: [Caml-list] How much optimized is the 'a option type ?

In my humble opinion the main purpose of Some _ | None is to avoid the
requirement for a nil pointer in OCaml. If an external function wants to
return nil in order to indicate, for example that a certain resource is not
available, it can return None instead and this prevents dereferencing a nil
pointer in OCaml because the None cannot be dereferenced. If you compare
this behaviour with the inferior clone F# written by Microsoft, you can see
that one of the things they added to the language was a nil pointer, thus
abandoning all type safety immediately and all because they did not want to
change their .NET runtime system for C# etc. They also have the notion of
initialising a typed object to in an invalid default, which is another
obvious disaster area. Oh and did I mention operators like +/- etc are
overloaded so you cannot infer function types without adding type
annotations.
The final insult is to make indentation significant in the syntax so that if
you post a program to a list which does not respect whitespace (for example
using a well-known Microsoft mail client), it completely destroys the
meaning of the program.

I'm sure the authors of F# have their reasons for making all these changes,
and I'm not one to stand in the way of progress, and I don't set out to
offend anybody, but I think they got it wrong ...

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

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

[Jon Harrop]

What if you unbox locals and box only when a value is written into the heap?

Consider your type:

type ('a,'b) result =
     | Ok of 'a
     | Error of 'b

The representation could be a bit tag, an 'a and a 'b. These three would be
passed into a function as three separate arguments etc.

In essence, the representation is the value type bit * 'a * 'b while the
value is local (a function parameter, a local variable, a return value) and
the usual boxed representation when it is written into the heap.

I actually wanted to try implementing this representation in HLVM...

Cheers,
Jon.

-----Original Message-----
From: caml-list-request@inria.fr [mailto:caml-list-request@inria.fr] On
Behalf Of Yaron Minsky
Sent: 17 January 2014 14:02
To: Nicolas Braud-Santoni
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] How much optimized is the 'a option type ?

I also agree with Gabriel that an option-specific optimization is not
clearly the right move.

But I wonder if a more general optimization that provided the possibility of
minting "fast-path" variants.  i.e., one could have an annotation that
marked a given branch of a variant as the "no-indirection" one, i.e., the
one that doesn't lead to the allocation of an extra block:

type ('a,'b) result =
     | Ok of 'a [@@no_indirection]
     | Error of 'b

would lead to a type where [Ok x == x].  Some cleverness is required then
for the representation of the [Error] branch.  In particular, you'd need
some dynamic test you could run to see if you were using a value that was
not the fast-path one.

The thing that I don't know if there's a solution for is the nesting
problem.  i.e., can you effectively distinguish:

  Ok (Ok (Error x))

from

  Error x

since they would have the same physical representation.  I'm not sure if
some variant of the counting trick used for options would work here or not.
But if you could get this, it would make it possible to avoid a large number
of dirty Obj.magic hacks that people need to do to build efficient
datastructures in practice.  The fact that the stdlib needs to use Obj.magic
to get the necessary performance is, I think, a sign that something
important is missing from the language.  I'm not sure if this is quite it,
to be clear.

y


On Fri, Jan 17, 2014 at 8:46 AM, Nicolas Braud-Santoni
<nicolas.braudsantoni@gmail.com> wrote:
> On 17/01/2014 12:23, Jonathan Kimmitt wrote:
>> In my humble opinion the main purpose of Some _ | None is to avoid 
>> the requirement for a nil pointer in OCaml. If an external function 
>> wants to return nil in order to indicate, for example that a certain 
>> resource is not available, it can return None instead and this 
>> prevents dereferencing a nil pointer in OCaml because the None cannot be
dereferenced.
> Yes.
> This doesn't forbid the compiler from representing 'a option values as 
> pointers.
> Indeed, the type system already enforces that the None case is handled 
> and the representation of None and Some _ do not matter.
>
> That said, I agree with Gabriel Scherer : adding optimizations 
> specific to 'a option might refrain people wanting to switch to more 
> appropriate datatypes.
> However, would is be possible to "optimize away" all types of the form 
> "type 'a t = X of 'a | A | B | ..." (with at most one non-constant
> constructor) ?
> Would it be worth doing ?
>
>
> Kind regards,
> Nicolas
>

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

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

[Jon Harrop]

Gerd wrote:
> Gabriel is right that the GC is good at short-living values, but that
> still leaves room for getting better with ultra-short-living values.

FWIW, the largest benefit of value types is in improving the topology of the
heap for long-lived values rather than for stack-allocating short-lived
values. For example, value types facilitate much more efficient generic hash
tables.

Cheers,
Jon.

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

Am Freitag, den 17.01.2014, 10:22 +0100 schrieb Simon Cruanes:
> Le Fri, 17 Jan 2014, Gabriel Scherer a écrit :
> 
> > 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.
> 
> I think optimization of some local uses of options, such as:

I also think that local uses of options (and other variant types) could be
candidates for optimization. Gabriel is right that the GC is good at
short-living values, but that still leaves room for getting better with
ultra-short-living values.

My idea would be to try to delay the allocation of the block, and to use two
registers, i.e. one for the tag, and one for the tagged inner value.
First when the constructed value is passed to some other function, or
returned, or stored inside another block, or in another register, the
allocation is really done. Of course, this could also result in more work in
total (especially when the compiler has no idea what the desired fast path
of the algorithm is), and I guess the real problem is that you need a good
heuristics to decide when to do this. But there are at least two criterions
at hand:

 - You are not under pressure with registers
 - All consumers of the constructed value are inside the same function

I guess this would result in a quite heavy patch for the comparatively small
effect, and that's why it is not yet done.


Gerd


> let rec iter_stream f s =
>     match (try Some (MyStream.get s) with End_of_stream -> None) with
>     | None -> ()
>     | Some (x, s') ->
>         f x;
>         iter_stream f s'
> 
> where an option is used to keep the function tail-rec (I've heard 
> several people tell me they often need to use this), or other cases 
> like optional parameters (which are not going to move to Either), 
> would be useful and future-proof. I hope the current work on 
> optimizations will help with this kind of cases (removing useless 
> allocations of local options, references, exceptions when no escape is
possible).
> 
> </wishlist>
> </2cents>
> </</>>
> 

--
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------

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

[Jon Harrop]

Simon Cruanes wrote:
> Maybe I'm stating the obvious, but wouldn't value types be the general solution here?

Yes but value types conflict with a uniform data representation. I think OCaml has reached a local optimum here...

Cheers,
Jon.

-----Original Message-----
From: caml-list-request@inria.fr [mailto:caml-list-request@inria.fr] On Behalf Of Simon Cruanes
Sent: 17 January 2014 14:10
To: Yaron Minsky
Cc: Nicolas Braud-Santoni; caml-list@inria.fr
Subject: Re: [Caml-list] How much optimized is the 'a option type ?

Le Fri, 17 Jan 2014, Yaron Minsky a écrit :
> I also agree with Gabriel that an option-specific optimization is not 
> clearly the right move.
> 
> But I wonder if a more general optimization that provided the 
> possibility of minting "fast-path" variants.  i.e., one could have an 
> annotation that marked a given branch of a variant as the 
> "no-indirection" one, i.e., the one that doesn't lead to the 
> allocation of an extra block:
> 
> type ('a,'b) result =
>      | Ok of 'a [@@no_indirection]
>      | Error of 'b
> 
> would lead to a type where [Ok x == x].  Some cleverness is required 
> then for the representation of the [Error] branch.  In particular, 
> you'd need some dynamic test you could run to see if you were using a 
> value that was not the fast-path one.
> 
> The thing that I don't know if there's a solution for is the nesting 
> problem.  i.e., can you effectively distinguish:
> 
>   Ok (Ok (Error x))
> 
> from
> 
>   Error x
> 
> since they would have the same physical representation.  I'm not sure 
> if some variant of the counting trick used for options would work here 
> or not.  But if you could get this, it would make it possible to avoid 
> a large number of dirty Obj.magic hacks that people need to do to 
> build efficient datastructures in practice.  The fact that the stdlib 
> needs to use Obj.magic to get the necessary performance is, I think, a 
> sign that something important is missing from the language.  I'm not 
> sure if this is quite it, to be clear.

Maybe I'm stating the obvious, but wouldn't value types be the general solution here? Assuming the optimizer can guarantee that the option value will not outlive the current scope, the value can be allocated on the stack or in registers. That's probably fast enough for most uses, isn't it? I think rust deals with option values exactly this way.


--
Simon

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

[oleg]

> let rec iter_stream f s =
>     match (try Some (MyStream.get s) with End_of_stream -> None) with
>     | None -> ()
>     | Some (x, s') ->
>         f x;
>         iter_stream f s'
>
> where an option is used to keep the function tail-rec (I've heard
> several people tell me they often need to use this), or other cases
> like optional parameters (which are not going to move to Either),
> would be useful and future-proof. 

I concur this is a very common pattern. The immediate thought is that
perhaps functions like MyStream.get should return an (('result,'error)
either) value rather than throw an exception. But there is a better
solution, described in

        Exceptional Syntax 
        Nick Benton and Andrew Kennedy. 
        In Journal of Functional Programming, 11(4):
        395-410, July 2001.
        http://research.microsoft.com/en-us/um/people/akenn/sml/ExceptionalSyntax.pdf

Incidentally, the example presented in Sec 3 of the paper is almost
exactly like the example mentioned on this thread. It is a common
problem, and luckily a good solution has been designed and well
explained. I guess what's lacking is time to implement it.

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

[Goswin von Brederlow]

On Fri, Jan 17, 2014 at 09:36:22AM -0500, Markus Mottl wrote:
> Others have already answered about memory representation, but there is
> one thing about allocations that many OCaml programmers may not yet be
> aware of and that can make a noticeable performance difference when
> used wisely: the OCaml compiler will inspect your code and, under the
> right conditions, batch together allocations.  E.g. consider this
> function (references are records, btw.):
> 
>   let f n =
>     let x = ref (ref (Some (Some n))) in
>     [(x, n); (x, n)]
> 
> One might naively assume that this would lead to seven or so
> allocations.  But if you inspect the assembly, you'll see only one
> allocation followed by mere initialization assignments.

Cool. Didn't know that. Thanks for whoever implemented that.

MfG
	Goswin

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

[Goswin von Brederlow]

On Fri, Jan 17, 2014 at 12:23:32PM +0100, Jonathan Kimmitt wrote:
> In my humble opinion the main purpose of Some _ | None is to avoid the
> requirement for a nil pointer in OCaml. If an external function wants to
> return nil in order to indicate, for example that a certain resource is not
> available, it can return None instead and this prevents dereferencing a nil
> pointer in OCaml because the None cannot be dereferenced. If you compare this
> behaviour with the inferior clone F# written by Microsoft, you can see that
> one of the things they added to the language was a nil pointer, thus
> abandoning all type safety immediately and all because they did not want to
> change their .NET runtime system for C# etc. They also have the notion of
> initialising a typed object to in an invalid default, which is another obvious
> disaster area. Oh and did I mention operators like +/- etc are overloaded so
> you cannot infer function types without adding type annotations.
> The final insult is to make indentation significant in the syntax so that if
> you post a program to a list which does not respect whitespace (for example
> using a well-known Microsoft mail client), it completely destroys the meaning
> of the program.
> 
> I'm sure the authors of F# have their reasons for making all these changes,
> and I'm not one to stand in the way of progress, and I don't set out to offend
> anybody, but I think they got it wrong ...

You could use the following representaion for 'a option:

None -> NULL pointer
Some x -> value x (meaning pointer for complex types, tagged integer eles)

This looks fine at first and typesafe. A pointer can never be NULL,
same for a tagged integer. BUT

None -> NULL
Some None -> NULL
Some Some x -> value x

You could no longer have 'a option option types. In F#, with nil
pointer, that will be a problem. But I guess nobody ever has 'a option
option types there.

MfG
	Goswin

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

[Jonathan Kimmitt]

OCaml already uses the number 1 to represent
0(sic), [], and None. Type safety prevents them getting mixed up.
The integer 1 would be represented by 3, and so on. Since pointers
are always even (on sensible platforms) this helps the garbage collector
to quickly scan without caring too much about what it all means.

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

[Francois Berenger]

On 01/19/2014 03:19 PM, oleg@okmij.org wrote:
>> let rec iter_stream f s =
>>      match (try Some (MyStream.get s) with End_of_stream -> None) with
>>      | None -> ()
>>      | Some (x, s') ->
>>          f x;
>>          iter_stream f s'
>>
>> where an option is used to keep the function tail-rec (I've heard
>> several people tell me they often need to use this), or other cases
>> like optional parameters (which are not going to move to Either),
>> would be useful and future-proof.
>
> I concur this is a very common pattern.

Almost the whole List module in batteries is written in this style,
to avoid reverting lists but keeping tail-rec functions which are not
when implemented naively.

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

[Francois Berenger]

Isn't this thread about people wanting to have monadic code
in OCaml going faster?

Someone has in mind some optimization that would make
all monadic code faster, right?
Not only the 'a option case, I hope.

On 01/20/2014 08:23 PM, Jonathan Kimmitt wrote:
> OCaml already uses the number 1 to represent
> 0(sic), [], and None. Type safety prevents them getting mixed up.
> The integer 1 would be represented by 3, and so on. Since pointers
> are always even (on sensible platforms) this helps the garbage collector
> to quickly scan without caring too much about what it all means.

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

[Jon Harrop]

Francois wrote:
> Isn't this thread about people wanting to have monadic code in OCaml going
faster?

I think you would need the equivalent optimizations applied to closures
which begs the question: how do you represent closures using value types?

Cheers,
Jon.

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

[Jon Harrop]

Goswin wrote:
> In F#, with nil pointer, that will be a problem. But I guess nobody ever
has 'a option option types there

I believe the representation of Some None in F# is a heap allocated block
containing a NULL pointer.

Cheers,
Jon.

-----Original Message-----
From: caml-list-request@inria.fr [mailto:caml-list-request@inria.fr] On
Behalf Of Goswin von Brederlow
Sent: 20 January 2014 10:17
To: caml-list@inria.fr
Subject: Re: [Caml-list] How much optimized is the 'a option type ?

On Fri, Jan 17, 2014 at 12:23:32PM +0100, Jonathan Kimmitt wrote:
> In my humble opinion the main purpose of Some _ | None is to avoid the 
> requirement for a nil pointer in OCaml. If an external function wants 
> to return nil in order to indicate, for example that a certain 
> resource is not available, it can return None instead and this 
> prevents dereferencing a nil pointer in OCaml because the None cannot 
> be dereferenced. If you compare this behaviour with the inferior clone 
> F# written by Microsoft, you can see that one of the things they added 
> to the language was a nil pointer, thus abandoning all type safety 
> immediately and all because they did not want to change their .NET 
> runtime system for C# etc. They also have the notion of initialising a 
> typed object to in an invalid default, which is another obvious 
> disaster area. Oh and did I mention operators like +/- etc are overloaded
so you cannot infer function types without adding type annotations.
> The final insult is to make indentation significant in the syntax so 
> that if you post a program to a list which does not respect whitespace 
> (for example using a well-known Microsoft mail client), it completely 
> destroys the meaning of the program.
> 
> I'm sure the authors of F# have their reasons for making all these 
> changes, and I'm not one to stand in the way of progress, and I don't 
> set out to offend anybody, but I think they got it wrong ...

You could use the following representaion for 'a option:

None -> NULL pointer
Some x -> value x (meaning pointer for complex types, tagged integer eles)

This looks fine at first and typesafe. A pointer can never be NULL, same for
a tagged integer. BUT

None -> NULL
Some None -> NULL
Some Some x -> value x

You could no longer have 'a option option types. In F#, with nil pointer,
that will be a problem. But I guess nobody ever has 'a option option types
there.

MfG
	Goswin

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

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

[Goswin von Brederlow]

On Wed, Jan 22, 2014 at 09:26:09PM -0000, Jon Harrop wrote:
> Goswin wrote:
> > In F#, with nil pointer, that will be a problem. But I guess nobody ever
> has 'a option option types there
> 
> I believe the representation of Some None in F# is a heap allocated block
> containing a NULL pointer.
> 
> Cheers,
> Jon.

So Some x is the value x unless x is an option type? That wouldn't
work for polymorphic functions, those taking 'a option. You can't
encode 'a option differently depending on 'a unless you have a flag
for which encoding it used as well.

I think you can only have one: option types using nil or 'a option
option.

Which doesn't mean you can't have nil too, just not to represent the
None part of 'a option. In ocaml you would need a new type syntax like

type 'a ptr_option = NIL | PTR of 'a constraint type b . 'a != b ptr_option

MfG
	Goswin

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

[Jon Harrop]

Goswin wrote:
> So Some x is the value x unless x is an option type?

No, Some x is always a reference to a heap-allocated object that contains
the value "x".

In fact, I think it is essentially the same as OCaml's representation for
the 'a option type (except for the run-time "type" information required by
the GC).

> You can't encode 'a option differently depending on 'a unless you have a
flag for which encoding it used as well.

Yes. I think it is a bad data representation though. Option types should
never allocate anything at all. They should be a value type containing a
boolean "HasValue" and the value itself which has a default in the event
that it is None. So None=(false, _), Some 3=(true, 3), Some None=(true,
(false, _)) and Some(Some 3)=(true, (true, 3)). You could even store the
Booleans and bytes as pack them so Some(Some 3) would take the same amount
of space (16 bytes) as Some 3.

Cheers,
Jon.

-----Original Message-----
From: caml-list-request@inria.fr [mailto:caml-list-request@inria.fr] On
Behalf Of Goswin von Brederlow
Sent: 23 January 2014 09:29
To: caml-list@inria.fr
Subject: Re: [Caml-list] How much optimized is the 'a option type ?

On Wed, Jan 22, 2014 at 09:26:09PM -0000, Jon Harrop wrote:
> Goswin wrote:
> > In F#, with nil pointer, that will be a problem. But I guess nobody 
> > ever
> has 'a option option types there
> 
> I believe the representation of Some None in F# is a heap allocated 
> block containing a NULL pointer.
> 
> Cheers,
> Jon.

So Some x is the value x unless x is an option type? That wouldn't work for
polymorphic functions, those taking 'a option. You can't encode 'a option
differently depending on 'a unless you have a flag for which encoding it
used as well.

I think you can only have one: option types using nil or 'a option option.

Which doesn't mean you can't have nil too, just not to represent the None
part of 'a option. In ocaml you would need a new type syntax like

type 'a ptr_option = NIL | PTR of 'a constraint type b . 'a != b ptr_option

MfG
	Goswin

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

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

[Yotam Barnoy]

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

Just to clarify, by value types you mean stuff allocated on the stack,
right?

-Yotam


On Thu, Jan 23, 2014 at 6:20 PM, Jon Harrop <jon@ffconsultancy.com> wrote:

> Goswin wrote:
> > So Some x is the value x unless x is an option type?
>
> No, Some x is always a reference to a heap-allocated object that contains
> the value "x".
>
> In fact, I think it is essentially the same as OCaml's representation for
> the 'a option type (except for the run-time "type" information required by
> the GC).
>
> > You can't encode 'a option differently depending on 'a unless you have a
> flag for which encoding it used as well.
>
> Yes. I think it is a bad data representation though. Option types should
> never allocate anything at all. They should be a value type containing a
> boolean "HasValue" and the value itself which has a default in the event
> that it is None. So None=(false, _), Some 3=(true, 3), Some None=(true,
> (false, _)) and Some(Some 3)=(true, (true, 3)). You could even store the
> Booleans and bytes as pack them so Some(Some 3) would take the same amount
> of space (16 bytes) as Some 3.
>
> Cheers,
> Jon.
>
> -----Original Message-----
> From: caml-list-request@inria.fr [mailto:caml-list-request@inria.fr] On
> Behalf Of Goswin von Brederlow
> Sent: 23 January 2014 09:29
> To: caml-list@inria.fr
> Subject: Re: [Caml-list] How much optimized is the 'a option type ?
>
> On Wed, Jan 22, 2014 at 09:26:09PM -0000, Jon Harrop wrote:
> > Goswin wrote:
> > > In F#, with nil pointer, that will be a problem. But I guess nobody
> > > ever
> > has 'a option option types there
> >
> > I believe the representation of Some None in F# is a heap allocated
> > block containing a NULL pointer.
> >
> > Cheers,
> > Jon.
>
> So Some x is the value x unless x is an option type? That wouldn't work for
> polymorphic functions, those taking 'a option. You can't encode 'a option
> differently depending on 'a unless you have a flag for which encoding it
> used as well.
>
> I think you can only have one: option types using nil or 'a option option.
>
> Which doesn't mean you can't have nil too, just not to represent the None
> part of 'a option. In ocaml you would need a new type syntax like
>
> type 'a ptr_option = NIL | PTR of 'a constraint type b . 'a != b ptr_option
>
> MfG
>         Goswin
>
> --
> 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
>

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

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

[Jon Harrop]

Yotam wrote:
> Just to clarify, by value types you mean stuff allocated on the stack,
right?

A value type is just an unboxed type like a C struct. A local variable of a
value type is stored on the stack. A field inside a heap-allocated object
that is a value type is stored inside the object and not in a separate
object. An array of value types is a single contiguous block of memory with
no pointers (e.g. an array of complex numbers).

With value types you can almost completely avoid the garbage collector by
replacing pointers with indices into an array of value types that acts as a
pool allocator. This can be useful for avoiding GC latency and for
optimizing for collections that violate the generational hypothesis (e.g.
long-lived Sets and Maps).

In HLVM, tuples were value types. For example, an (int * float) array is
represented as a single contiguous block of memory. In constrast, OCaml
represents this is an array of pointers to pairs where the second element is
another pointer to a boxed float.

Value types and reified generics permit very efficient hash tables. For
example, the Dictionary<int, float> type on .NET does not contain any
pointers.

Cheers,
Jon.

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

[Andreas Rossberg]

On Jan 24, 2014, at 09:22 , Jon Harrop <jon@ffconsultancy.com> wrote:
> With value types you can almost completely avoid the garbage collector by
> replacing pointers with indices into an array of value types that acts as a
> pool allocator. This can be useful for avoiding GC latency and for
> optimizing for collections that violate the generational hypothesis (e.g.
> long-lived Sets and Maps).

As you well know, though, pervasive unboxing as for value types is incompatible with a uniform representation approach like used by OCaml. And non-uniform representation requires either static monomorphisation (not possible in OCaml, because of first-class polymorphism and separate compilation), or dynamic monomorphisation (not possible without just-in-time compilation), or runtime type passing and switching (expensive).

/Andreas

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

[Alain Frisch]

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

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

[Alain Frisch]

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
>

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

[Yaron Minsky]

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

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

[Jon Harrop]

On 24.01.2014 08:34, Andreas Rossberg wrote:
> On Jan 24, 2014, at 09:22 , Jon Harrop <jon@ffconsultancy.com> wrote:
>> With value types you can almost completely avoid the garbage 
>> collector by replacing pointers with indices into an array of value 
>> types that acts as a pool allocator. This can be useful for avoiding 
>> GC latency and for optimizing for collections that violate the 
>> generational hypothesis (e.g.
>> long-lived Sets and Maps).
>
> As you well know, though, pervasive unboxing as for value types is 
> incompatible with a uniform representation approach like used by 
> OCaml. And non-uniform representation requires either static 
> monomorphisation (not possible in OCaml, because of first-class 
> polymorphism and separate compilation), or dynamic monomorphisation 
> (not possible without just-in-time compilation), or runtime type 
> passing and switching (expensive).

I think there are halfway houses as well...

Options could keep the same uniform representation when on the heap but be
unboxed when they are stored locally (arguments, local variables and return
values). You could either carry the pointer to the original option (if any)
or re-allocate when it was needed.

If run-time type passing and switching is expensive because of virtual
dispatch then you could replace the dynamic jump with a test to see if the
location is the same as it was for the last jump and, if so, use a static
jump and then update just the static jump using JIT compilation. 
That requires JIT compilation but, perhaps, so little JIT compilation that
the technique is of interest?

The required run-time type information could just be the number of
(uniformly-represented) words in each value and the "switch" could be a loop
(that usually does only one iteration). For example, the "A of 'a | B of 'b
* 'b | C" could be represented using 3 words per value instead of one: one
for the tag A=1|B=2|C=3 and two for the two potential arguments.

On a related note, doesn't OCaml box multiple return values as well? Could
it use sret form and elide the write barrier instead?

Even if such approaches don't improve overall performance they should shift
the burden off the GC and onto the generated code which would make it easier
to obtain good performance for alternative GC implementations (like OC4MC).

Cheers,
Jon.

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

[Goswin von Brederlow]

On Fri, Jan 24, 2014 at 08:22:43AM -0000, Jon Harrop wrote:
> Yotam wrote:
> > Just to clarify, by value types you mean stuff allocated on the stack,
> right?
> 
> A value type is just an unboxed type like a C struct. A local variable of a
> value type is stored on the stack. A field inside a heap-allocated object
> that is a value type is stored inside the object and not in a separate
> object. An array of value types is a single contiguous block of memory with
> no pointers (e.g. an array of complex numbers).
> 
> With value types you can almost completely avoid the garbage collector by
> replacing pointers with indices into an array of value types that acts as a
> pool allocator. This can be useful for avoiding GC latency and for
> optimizing for collections that violate the generational hypothesis (e.g.
> long-lived Sets and Maps).
> 
> In HLVM, tuples were value types. For example, an (int * float) array is
> represented as a single contiguous block of memory. In constrast, OCaml
> represents this is an array of pointers to pairs where the second element is
> another pointer to a boxed float.
> 
> Value types and reified generics permit very efficient hash tables. For
> example, the Dictionary<int, float> type on .NET does not contain any
> pointers.
> 
> Cheers,
> Jon.

Problem is that a value is a fixed size and fits in a register. A
tuple does not. (int * float) even takes the space of 3 values on
32bit. You can unbox that in the optimizer for local use but in memory
and in function calls you need to pass this as box. Otherwise
polymorphic functions break.

Putting larger structures into an array without boxing also only works
for immutable objects and by copying them every time they are passed
around. You can't copy a mutable and you can't pass a pointer to the
middle of an array to another function or the GC might freak out.

So you have to be verry carefull where you use those unboxed arrays.
They only works within a single module like a Hashtbl.

MfG
	Goswin

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

[Goswin von Brederlow]

On Fri, Jan 24, 2014 at 04:56:46PM -0000, Jon Harrop wrote:
> On 24.01.2014 08:34, Andreas Rossberg wrote:
> > On Jan 24, 2014, at 09:22 , Jon Harrop <jon@ffconsultancy.com> wrote:
> >> With value types you can almost completely avoid the garbage 
> >> collector by replacing pointers with indices into an array of value 
> >> types that acts as a pool allocator. This can be useful for avoiding 
> >> GC latency and for optimizing for collections that violate the 
> >> generational hypothesis (e.g.
> >> long-lived Sets and Maps).
> >
> > As you well know, though, pervasive unboxing as for value types is 
> > incompatible with a uniform representation approach like used by 
> > OCaml. And non-uniform representation requires either static 
> > monomorphisation (not possible in OCaml, because of first-class 
> > polymorphism and separate compilation), or dynamic monomorphisation 
> > (not possible without just-in-time compilation), or runtime type 
> > passing and switching (expensive).
> 
> I think there are halfway houses as well...
> 
> Options could keep the same uniform representation when on the heap but be
> unboxed when they are stored locally (arguments, local variables and return
> values). You could either carry the pointer to the original option (if any)
> or re-allocate when it was needed.

They should certainly be unboxed when in registers. So

let t = (23, 42.0) in

would basically become

let t_0 = 23 in   (* r0 *)
let t_1 = 42.0 in (* fpu0 *)

Unless the tuple escapes the scope (either up or down) it should never
be allocated.

But you can't just put a float 42.0 on the heap or even stack when the
GC might get called. That needs to be boxed in some way to avoid it
getting misread as pointer.
 
> If run-time type passing and switching is expensive because of virtual
> dispatch then you could replace the dynamic jump with a test to see if the
> location is the same as it was for the last jump and, if so, use a static
> jump and then update just the static jump using JIT compilation. 
> That requires JIT compilation but, perhaps, so little JIT compilation that
> the technique is of interest?

Or compile code poly-monomorphic. Meaning for a function
taking/returning a tuple compile 2 (or more) flavours. One that
allocates the tuple and one that passes the tuple in registers.

Obviously higher level function would need a lot of flavours to cover
all combinations. And closure would need multiple flavours too. But
when there are too many cases, or when it is undecidable, the compiler
can simply use the base case of allocaating everything like it does
now. But all of this would be done static at compile time.
 
> The required run-time type information could just be the number of
> (uniformly-represented) words in each value and the "switch" could be a loop
> (that usually does only one iteration). For example, the "A of 'a | B of 'b
> * 'b | C" could be represented using 3 words per value instead of one: one
> for the tag A=1|B=2|C=3 and two for the two potential arguments.
> 
> On a related note, doesn't OCaml box multiple return values as well? Could
> it use sret form and elide the write barrier instead?

There are never multiple return values. You can only return tuples.

let f x y z = (x, y, z)
let (x,y,z) = f 1 2 3

It would be nice not to allocate that tuple. Does ocaml allocate it?
Or does inlining optimize the tuple away?

> Even if such approaches don't improve overall performance they should shift
> the burden off the GC and onto the generated code which would make it easier
> to obtain good performance for alternative GC implementations (like OC4MC).
> 
> Cheers,
> Jon.

MfG
	Goswin

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

[Yotam Barnoy]

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

>
> But you can't just put a float 42.0 on the heap or even stack when the
> GC might get called. That needs to be boxed in some way to avoid it
> getting misread as pointer.
>
>
It wouldn't be too hard to add a word of metadata to the stack to tell the
GC what's a pointer and what isn't. Haskell does this for function calls
(in fact, if the metadata doesn't fit in a word, it allocates a separate
metadata structure), and F# has this from the .NET runtime which has full
type metadata for everything.

Problem is that a value is a fixed size and fits in a register. A
> tuple does not. (int * float) even takes the space of 3 values on
> 32bit. You can unbox that in the optimizer for local use but in memory
> and in function calls you need to pass this as box. Otherwise
> polymorphic functions break.
>
> Putting larger structures into an array without boxing also only works
> for immutable objects and by copying them every time they are passed
> around. You can't copy a mutable and you can't pass a pointer to the
> middle of an array to another function or the GC might freak out.
>

Leaving it to the optimizer is problematic because it might cause a lot of
unneeded boxing and unboxing.
Haskell has the {- #UNPACK -} pragma to unbox types. You have to be really
careful in haskell with this, because you're also changing the evaluation
semantics to be strict. This makes for really ugly optimized haskell code,
but maybe we can do something similar (but not as ugly). F# inherits .NET's
struct types, which are similarly limited, but also useful. Of course, once
you unbox, all parametric polymorphism is lost, but because you have
control over it, you can decide where it's worthwhile.

An example of unpack usage in haskell:

data T = T {-# UNPACK #-} !(Int,Int)

which would be equivalent to something like
type t = (int * int) [@u]

Note that the whole tuple is unboxed.

In haskell, you can now do

f :: T -> Int
f (T(i1,i2)) = i1 + i2

and in ocaml you'd do

let f : t -> int = fun (i1,i2) = i1 + i2

Of course, this would require more metadata for the stack. For the heap,
you'd probably want to just use a new tag or the custom tag. For ocaml
you'd also probably have to stipulate that polymorphic marshalling cannot
be performed on this type, and neither can polymorphic comparison -- you'd
have to have specific marshalling/comparison functions, which aren't too
difficult to generate automatically.

-Yotam



>
> --
> 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: 3898 bytes --]

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

[Goswin von Brederlow]

On Mon, Jan 27, 2014 at 11:18:23AM -0500, Yotam Barnoy wrote:
> >
> > But you can't just put a float 42.0 on the heap or even stack when the
> > GC might get called. That needs to be boxed in some way to avoid it
> > getting misread as pointer.
> >
> >
> It wouldn't be too hard to add a word of metadata to the stack to tell the
> GC what's a pointer and what isn't. Haskell does this for function calls
> (in fact, if the metadata doesn't fit in a word, it allocates a separate
> metadata structure), and F# has this from the .NET runtime which has full
> type metadata for everything.
> 
> Problem is that a value is a fixed size and fits in a register. A
> > tuple does not. (int * float) even takes the space of 3 values on
> > 32bit. You can unbox that in the optimizer for local use but in memory
> > and in function calls you need to pass this as box. Otherwise
> > polymorphic functions break.
> >
> > Putting larger structures into an array without boxing also only works
> > for immutable objects and by copying them every time they are passed
> > around. You can't copy a mutable and you can't pass a pointer to the
> > middle of an array to another function or the GC might freak out.
> >
> 
> Leaving it to the optimizer is problematic because it might cause a lot of
> unneeded boxing and unboxing.
> Haskell has the {- #UNPACK -} pragma to unbox types. You have to be really
> careful in haskell with this, because you're also changing the evaluation
> semantics to be strict. This makes for really ugly optimized haskell code,
> but maybe we can do something similar (but not as ugly). F# inherits .NET's
> struct types, which are similarly limited, but also useful. Of course, once
> you unbox, all parametric polymorphism is lost, but because you have
> control over it, you can decide where it's worthwhile.
> 
> An example of unpack usage in haskell:
> 
> data T = T {-# UNPACK #-} !(Int,Int)
> 
> which would be equivalent to something like
> type t = (int * int) [@u]
> 
> Note that the whole tuple is unboxed.
> 
> In haskell, you can now do
> 
> f :: T -> Int
> f (T(i1,i2)) = i1 + i2
> 
> and in ocaml you'd do
> 
> let f : t -> int = fun (i1,i2) = i1 + i2
> 
> Of course, this would require more metadata for the stack. For the heap,
> you'd probably want to just use a new tag or the custom tag. For ocaml
> you'd also probably have to stipulate that polymorphic marshalling cannot
> be performed on this type, and neither can polymorphic comparison -- you'd
> have to have specific marshalling/comparison functions, which aren't too
> difficult to generate automatically.
> 
> -Yotam

That would make it a new type, incompatible with the old one. So a
function expecting 'a wouldn't accept 'a [@u] and everything would be
fine (but not nice). And then you can define the semantic that types
like that are passed and returned in registers if small enough.

As for allocation. On the stack you would have one big block for all
local variables and put unboxed structures there. You couldn't put the
values on the heap. So if you return a unpacked type then it has to be
copied (implizit if it is passed in regs) on return or the caller has
to pass a pointer to where the result should go as implizit argument.

MfG
	Goswin

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

[Jon Harrop]

Yotam wrote:
> Of course, once you unbox, all parametric polymorphism is lost

Is it?

You would have to box the tuple before passing it to a polymorphic function
with the type 'a -> 'a. However, if the function has the type 'a * 'b -> 'b
* 'a then you could always unbox, right?

Cheers,
Jon.

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

[Yotam Barnoy]

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

On Wed, Jan 29, 2014 at 3:32 AM, Jon Harrop <jon@ffconsultancy.com> wrote:

> Yotam wrote:
> > Of course, once you unbox, all parametric polymorphism is lost
>
> Is it?
>
>
It is in haskell. In general, I don't think you can do any parametric
polymorphism without metadata.


> You would have to box the tuple before passing it to a polymorphic function
> with the type 'a -> 'a. However, if the function has the type 'a * 'b -> 'b
> * 'a then you could always unbox, right?
>
>
I don't think so. Without metadata, how do you know where one tuple member
ends and another begins?

Yotam

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

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

[Yotam Barnoy]

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

BTW there's a compromise with unboxing that also has benefits, which is
embedding. An [@embed] annotation could turn an array into an embedding
array, for example. This would mean that an array would have boxed members
within it ie. not accessible via pointers. The advantages are better cache
performance and that the GC could be instructed when the array is
completely flat ie. an embedded array without any pointers could be skipped
by the GC in the mark phase. It would have full polymorphism capability.

The down side is that deallocating the array without deallocating the
embedded structure would be tricky. When deallocating, you have to check
every member to see if it should be deallocated as well. If not, you copy
the member (minor heap) or reallocate the member where it is in memory
(major heap).

Yotam


On Wed, Jan 29, 2014 at 11:11 AM, Yotam Barnoy <yotambarnoy@gmail.com>wrote:

>
> On Wed, Jan 29, 2014 at 3:32 AM, Jon Harrop <jon@ffconsultancy.com> wrote:
>
>> Yotam wrote:
>> > Of course, once you unbox, all parametric polymorphism is lost
>>
>> Is it?
>>
>>
> It is in haskell. In general, I don't think you can do any parametric
> polymorphism without metadata.
>
>
>> You would have to box the tuple before passing it to a polymorphic
>> function
>> with the type 'a -> 'a. However, if the function has the type 'a * 'b ->
>> 'b
>> * 'a then you could always unbox, right?
>>
>>
> I don't think so. Without metadata, how do you know where one tuple member
> ends and another begins?
>
> Yotam
>

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

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

[Jon Harrop]

Yotam wrote:
> I don't think so. Without metadata, how do you know where one tuple member
ends and another begins?

Use static type information. When the type is known to be 'a * 'b you use
the unboxed representation. Otherwise you default to the boxed
representation.

OCaml already does this to some extent because functions that accept a tuple
are compiled to multi-argument functions (IIRC). So this would just be an
extension to handle the return value too. The same idea could be used with
many other types, e.g. unboxed optional arguments.

Cheers,
Jon.

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

[Yotam Barnoy]

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

I don't really understand how this could work. If the type of a function is
'a * 'b -> 'c then the function expects 2 tuple members, right? It has no
idea what their size is, because it can be called on any tuple. Now let's
say the tuple is float * int. If we unbox the tuple,  we get 3 words, with
the int comprising the 3rd word, and no metadata. How does the function
know how big each member is, or where to find each member? Are you assuming
we monomorphize the function?

Yotam


On Thu, Jan 30, 2014 at 4:31 PM, Jon Harrop <jon@ffconsultancy.com> wrote:

> Yotam wrote:
> > I don't think so. Without metadata, how do you know where one tuple
> member
> ends and another begins?
>
> Use static type information. When the type is known to be 'a * 'b you use
> the unboxed representation. Otherwise you default to the boxed
> representation.
>
> OCaml already does this to some extent because functions that accept a
> tuple
> are compiled to multi-argument functions (IIRC). So this would just be an
> extension to handle the return value too. The same idea could be used with
> many other types, e.g. unboxed optional arguments.
>
> Cheers,
> Jon.
>
>
>

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

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

[Jon Harrop]

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

 

I see. I meant unbox the tuple as in "the tuple and only the tuple" rather
than "the tuple and everything inside the tuple". So unboxing a float * int
would give you two words, one pointing to the boxed float and the other
containing a tagged int.

 

Cheers,

Jon.

 

From: Yotam Barnoy [mailto:yotambarnoy@gmail.com] 
Sent: 30 January 2014 21:43
To: Jon Harrop
Cc: Goswin von Brederlow; Ocaml Mailing List
Subject: Re: [Caml-list] How much optimized is the 'a option type ?

 

I don't really understand how this could work. If the type of a function is
'a * 'b -> 'c then the function expects 2 tuple members, right? It has no
idea what their size is, because it can be called on any tuple. Now let's
say the tuple is float * int. If we unbox the tuple,  we get 3 words, with
the int comprising the 3rd word, and no metadata. How does the function know
how big each member is, or where to find each member? Are you assuming we
monomorphize the function?

Yotam

 

On Thu, Jan 30, 2014 at 4:31 PM, Jon Harrop <jon@ffconsultancy.com> wrote:

Yotam wrote:
> I don't think so. Without metadata, how do you know where one tuple member
ends and another begins?

Use static type information. When the type is known to be 'a * 'b you use
the unboxed representation. Otherwise you default to the boxed
representation.

OCaml already does this to some extent because functions that accept a tuple
are compiled to multi-argument functions (IIRC). So this would just be an
extension to handle the return value too. The same idea could be used with
many other types, e.g. unboxed optional arguments.

Cheers,
Jon.



 


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

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

[Goswin von Brederlow]

On Mon, Jan 27, 2014 at 11:18:23AM -0500, Yotam Barnoy wrote:
> >
> > But you can't just put a float 42.0 on the heap or even stack when the
> > GC might get called. That needs to be boxed in some way to avoid it
> > getting misread as pointer.
> >
> >
> It wouldn't be too hard to add a word of metadata to the stack to tell the
> GC what's a pointer and what isn't. Haskell does this for function calls
> (in fact, if the metadata doesn't fit in a word, it allocates a separate
> metadata structure), and F# has this from the .NET runtime which has full
> type metadata for everything.

You can do that. It's called BOXING.

Even if you create just a single box for the whole stackframe of the
function it is still a box.

See the other thread about changing the in memory represenation of
ocaml for how to improve having boxed with mixed content so
int32/int64/float don't need extra boxing on their own.
 
> Problem is that a value is a fixed size and fits in a register. A
> > tuple does not. (int * float) even takes the space of 3 values on
> > 32bit. You can unbox that in the optimizer for local use but in memory
> > and in function calls you need to pass this as box. Otherwise
> > polymorphic functions break.
> >
> > Putting larger structures into an array without boxing also only works
> > for immutable objects and by copying them every time they are passed
> > around. You can't copy a mutable and you can't pass a pointer to the
> > middle of an array to another function or the GC might freak out.
> >
> 
> Leaving it to the optimizer is problematic because it might cause a lot of
> unneeded boxing and unboxing.
> Haskell has the {- #UNPACK -} pragma to unbox types. You have to be really
> careful in haskell with this, because you're also changing the evaluation
> semantics to be strict. This makes for really ugly optimized haskell code,
> but maybe we can do something similar (but not as ugly). F# inherits .NET's
> struct types, which are similarly limited, but also useful. Of course, once
> you unbox, all parametric polymorphism is lost, but because you have
> control over it, you can decide where it's worthwhile.
> 
> An example of unpack usage in haskell:
> 
> data T = T {-# UNPACK #-} !(Int,Int)
> 
> which would be equivalent to something like
> type t = (int * int) [@u]
> 
> Note that the whole tuple is unboxed.
> 
> In haskell, you can now do
> 
> f :: T -> Int
> f (T(i1,i2)) = i1 + i2
> 
> and in ocaml you'd do
> 
> let f : t -> int = fun (i1,i2) = i1 + i2
> 
> Of course, this would require more metadata for the stack. For the heap,
> you'd probably want to just use a new tag or the custom tag. For ocaml
> you'd also probably have to stipulate that polymorphic marshalling cannot
> be performed on this type, and neither can polymorphic comparison -- you'd
> have to have specific marshalling/comparison functions, which aren't too
> difficult to generate automatically.
> 
> -Yotam

Consider this:

type ['a] tt = ('a * 'a) [@u]
let ff : 'a tt -> ('a -> int) -> int = fun (t1, t2) f = f t2
let x = ff ((1, 2), (3, 4)) f

The ff function is tail recursive so f is called with the arguments of
ff no longer registered with the GC. And f is passed a pointer to the
middle of the tt type. Now lets assume the GC will run inside f.

*BOOM*

The tt type is no longer reachable so it would be freed. f has a
pointer pointing to the middle of a block causing the GC to parse the
t1 part of tt type as metadata.

Overall verry bad. Boxed and UNPACKed types would have to be
incompatible in ocaml.

MfG
	Goswin

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

[Goswin von Brederlow]

On Thu, Jan 30, 2014 at 01:43:59PM -0500, Yotam Barnoy wrote:
> BTW there's a compromise with unboxing that also has benefits, which is
> embedding. An [@embed] annotation could turn an array into an embedding
> array, for example. This would mean that an array would have boxed members
> within it ie. not accessible via pointers. The advantages are better cache
> performance and that the GC could be instructed when the array is
> completely flat ie. an embedded array without any pointers could be skipped
> by the GC in the mark phase. It would have full polymorphism capability.
> 
> The down side is that deallocating the array without deallocating the
> embedded structure would be tricky. When deallocating, you have to check
> every member to see if it should be deallocated as well. If not, you copy
> the member (minor heap) or reallocate the member where it is in memory
> (major heap).
> 
> Yotam

When deallocating the array you simply deallocate it all. You can't
have any pointers to inside the array floating around or the GC would
blow up. An array of embedded values can only be freed when nothing
has access to it any more at all. And access to members can only b
done as pointer to array + offset.

> On Wed, Jan 29, 2014 at 11:11 AM, Yotam Barnoy <yotambarnoy@gmail.com>wrote:
> 
> >
> > On Wed, Jan 29, 2014 at 3:32 AM, Jon Harrop <jon@ffconsultancy.com> wrote:
> >
> >> Yotam wrote:
> >> > Of course, once you unbox, all parametric polymorphism is lost
> >>
> >> Is it?
> >>
> >>
> > It is in haskell. In general, I don't think you can do any parametric
> > polymorphism without metadata.
> >
> >
> >> You would have to box the tuple before passing it to a polymorphic
> >> function
> >> with the type 'a -> 'a. However, if the function has the type 'a * 'b ->
> >> 'b
> >> * 'a then you could always unbox, right?

let f =
  let t = ref 0 in
  function (x, y) ->
    t := y;
    (y, x)

With f being unboxed you end up with a pointer to the middle of a
tuple in t and the GC goes *BOOM*.

Unboxed values allow only some operations.

> > I don't think so. Without metadata, how do you know where one tuple member
> > ends and another begins?
> >
> > Yotam

Being unboxed you get the first member in R0 and the second in R1.

MfG
	Goswin