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

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

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=