[Caml-list] reference cells

[Caml-list] reference cells

[Nicolas Ojeda Bar]

Hello,

I am translating an imperative language into Ocaml. Right now I am
translating mutable variables into ref cells. Will they be optimized
when I compile the corresponding Ocaml program? Or will they be heap
allocated? If this is the case, I will have to translate my language
into some sort of SSA form before, and I would like to avoid that.

Thanks!
N

Re: [Caml-list] reference cells

[Michael Ekstrand]

On 01/31/2011 10:29 AM, Nicolas Ojeda Bar wrote:
> I am translating an imperative language into Ocaml. Right now I am
> translating mutable variables into ref cells. Will they be optimized
> when I compile the corresponding Ocaml program? Or will they be heap
> allocated? If this is the case, I will have to translate my language
> into some sort of SSA form before, and I would like to avoid that.

Most of them will be heap-allocated.  They may stay on the minor heap if
they're short-lived, so they may never hit the major heap (and thus
incur higher GC overhead), but they'll be on the heap.

I believe the compiler has optimizations to unbox some refs,
particularly for ints and floats, but for heap-allocated structures I
believe it will produce heap allocated references.

Further, mutating references can be a relatively expensive operation. 
In order to support the major-minor heap scheme, modifying a reference
that points to a non-integral value (anything that's heap allocated)
involves checking some tables to see where the reference and referenced
object are.  This is to keep track of all references in the major heap
which have been changed to point to objects on the minor heap.  Int refs
can avoid this problem, as integers are not stored on the heap, but for
anything more complex (including boxed floats), you incur the
caml_modify overhead.  This is true not only for references, but also
for mutable fields and array cells.

- Michael

Re: [Caml-list] reference cells

[Guillaume Yziquel]

Le Monday 31 Jan 2011 à 11:29:01 (-0500), Nicolas Ojeda Bar a écrit :
> Hello,

Hi.

> I am translating an imperative language into Ocaml. Right now I am
> translating mutable variables into ref cells. Will they be optimized
> when I compile the corresponding Ocaml program? Or will they be heap
> allocated? If this is the case, I will have to translate my language
> into some sort of SSA form before, and I would like to avoid that.
> 

Heap allocated. Indeed:

> yziquel@seldon:~$ ocaml
>         Objective Caml version 3.12.0
> 
> # let x = ref 10;;
> val x : int ref = {contents = 10}
> # Obj.tag (Obj.repr x);;
> - : int = 0
> # Obj.size (Obj.repr x);;
> - : int = 1
> # (Obj.magic (Obj.field (Obj.repr x) 0) : int);;
> - : int = 10
> # 

-- 
     Guillaume Yziquel

Re: [Caml-list] reference cells

[David Baelde]

On Mon, Jan 31, 2011 at 5:46 PM, Guillaume Yziquel
<guillaume.yziquel@citycable.ch> wrote:
>> # let x = ref 10;;
>> val x : int ref = {contents = 10}
>> # Obj.tag (Obj.repr x);;
>> - : int = 0

A funny side note about that test: the fact that you pass your
reference to a function (Obj.repr) prevents the compiler from
optimizing it. So even if you try (let x = ref 10 in Obj.tag (Obj.repr
x)) you'll see the same tag, while (as Alain said) Ocaml can actually
avoid heap allocation in similar expressions where your reference is
clearly local.

The lambda code remains the best option:

$ cat test.ml
let () = let x = ref 10 in Printf.printf "%d\n" (Obj.tag (Obj.repr !x))
let () = let x = ref 10 in Printf.printf "%d\n" (Obj.tag (Obj.repr x))

$ ocamlc -dlambda test.ml
(setglobal Test!
  (let
    (match/61
       (let (x/58 10)
         (apply (field 1 (global Printf!)) "%d\n" (caml_obj_tag (id x/58))))
     match/60
       (let (x/59 (makemutable 0 10))
         (apply (field 1 (global Printf!)) "%d\n" (caml_obj_tag (id x/59)))))
    (makeblock 0)))

Cheers,
-- 
David

Re: [Caml-list] reference cells

[Guillaume Yziquel]

Le Friday 04 Feb 2011 à 12:49:28 (+0100), David Baelde a écrit :
> On Mon, Jan 31, 2011 at 5:46 PM, Guillaume Yziquel
> <guillaume.yziquel@citycable.ch> wrote:
> >> # let x = ref 10;;
> >> val x : int ref = {contents = 10}
> >> # Obj.tag (Obj.repr x);;
> >> - : int = 0
> 
> A funny side note about that test: the fact that you pass your
> reference to a function (Obj.repr) prevents the compiler from
> optimizing it. So even if you try (let x = ref 10 in Obj.tag (Obj.repr
> x)) you'll see the same tag, while (as Alain said) Ocaml can actually
> avoid heap allocation in similar expressions where your reference is
> clearly local.

Yes. I understood that looking at the -dlambda compiler option. I didn't
quite grasp the scope of the original question at the time I answered.
 
> The lambda code remains the best option:
> 
> $ cat test.ml
> let () = let x = ref 10 in Printf.printf "%d\n" (Obj.tag (Obj.repr !x))
> let () = let x = ref 10 in Printf.printf "%d\n" (Obj.tag (Obj.repr x))
> 
> $ ocamlc -dlambda test.ml
> (setglobal Test!
>   (let
>     (match/61
>        (let (x/58 10)
>          (apply (field 1 (global Printf!)) "%d\n" (caml_obj_tag (id x/58))))
>      match/60
>        (let (x/59 (makemutable 0 10))
>          (apply (field 1 (global Printf!)) "%d\n" (caml_obj_tag (id x/59)))))
>     (makeblock 0)))
> 
> Cheers,
> -- 
> David

So it's the 'makemutable' that makes all the difference.

By the way, is it possible to compile 'dlambda' code to native code directly?
It would be a nice compilation target.

-- 
     Guillaume Yziquel

Re: [Caml-list] reference cells

[Alain Frisch]

On 01/31/2011 05:29 PM, Nicolas Ojeda Bar wrote:
> I am translating an imperative language into Ocaml. Right now I am
> translating mutable variables into ref cells. Will they be optimized
> when I compile the corresponding Ocaml program? Or will they be heap
> allocated? If this is the case, I will have to translate my language
> into some sort of SSA form before, and I would like to avoid that.

Mutable variables which are used only internally in a function's body
are not heap allocated.

If you write:

    let r = ref e0 in e1

and r only appears in e1 under the form:

     r := ...
     !r

and not under a local abstraction, then the reference is kept in a local 
variable.

You can use the -dlambda switch to the compilers and toplevel to see that.


-- Alain

RE: [Caml-list] reference cells

[Jon Harrop]

Don't you add the redundant 1.0 *. x at the end of numerical functions to
trick ocamlopt into unboxing because the mutable variable used only
internally in the function's body is heap allocated otherwise?

Cheers,
Jon.

> -----Original Message-----
> From: Alain Frisch [mailto:alain.frisch@lexifi.com]
> Sent: 31 January 2011 18:13
> To: Nicolas Ojeda Bar
> Cc: caml-list@yquem.inria.fr
> Subject: Re: [Caml-list] reference cells
> 
> On 01/31/2011 05:29 PM, Nicolas Ojeda Bar wrote:
> > I am translating an imperative language into Ocaml. Right now I am
> > translating mutable variables into ref cells. Will they be optimized
> > when I compile the corresponding Ocaml program? Or will they be heap
> > allocated? If this is the case, I will have to translate my language
> > into some sort of SSA form before, and I would like to avoid that.
> 
> Mutable variables which are used only internally in a function's body
> are not heap allocated.
> 
> If you write:
> 
>     let r = ref e0 in e1
> 
> and r only appears in e1 under the form:
> 
>      r := ...
>      !r
> 
> and not under a local abstraction, then the reference is kept in a
> local
> variable.
> 
> You can use the -dlambda switch to the compilers and toplevel to see
> that.
> 
> 
> -- Alain
> 
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs