OCaml and Boehm

OCaml and Boehm

[Lukasz Stafiniak]

Hi,

Is the OCaml runtime Boehm-safe? That is, can it be run with Boehm
turned on and traversing OCaml's heap? (So that the OCaml heap can
provide roots to Boehm.) And if not, could it be patched to make it
Boehm-safe in this sense?

Thanks,
Łukasz

Re: [Caml-list] OCaml and Boehm

[Basile STARYNKEVITCH]

Lukasz Stafiniak wrote:
> Hi,
>
> Is the OCaml runtime Boehm-safe? That is, can it be run with Boehm
> turned on and traversing OCaml's heap? (So that the OCaml heap can
> provide roots to Boehm.) And if not, could it be patched to make it
> Boehm-safe in this sense?
>
>   
Probably not. Because I am not sure of what you mean by Boehm-safe, 
since Boehm's GC is conservative and do not make much promises.

And very probably, Ocaml runtime cannot realistically be make Boehm-safe 
or even Boehm compatible.

There is a reason for all this. The major strength of Ocaml runtime is 
its robustness and its efficiency. The efficiency of Ocaml GC is of 
paramount importance (it supports very high allocation rate, which is 
out of reach for the Boehm collector; and big allocation rate is typical 
of most functional programs; the typical allocation speed within the 
Ocaml runtime is at least one or two order of magnitudes faster than 
that of GC_malloc; a typical GC_malloc is by itself a bit slower than a 
libc malloc.).

However, it could happen that you might run some Boehm GC code inside 
Ocaml if you are lucky. You should be sure that no pointer go from 
GC-Boehm zone into Ocaml zone.

But your question is really too vague. What is the Boehm-GC based code 
you want to run within an Ocaml application, and what is that application?

Regards.

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***

Re: [Caml-list] OCaml and Boehm

[Jon Harrop]

On Saturday 11 April 2009 10:46:13 Basile STARYNKEVITCH wrote:
> Lukasz Stafiniak wrote:
> > Hi,
> >
> > Is the OCaml runtime Boehm-safe? That is, can it be run with Boehm
> > turned on and traversing OCaml's heap? (So that the OCaml heap can
> > provide roots to Boehm.) And if not, could it be patched to make it
> > Boehm-safe in this sense?
>
> Probably not. Because I am not sure of what you mean by Boehm-safe,
> since Boehm's GC is conservative and do not make much promises.

Boehm's GC breaks on various code, most notably code that "hides" pointers to 
reachable data in an indirect form. The most famous example that breaks Boehm 
is the (admittedly awful and technically illegal) pointer bump trick used in 
Numerical Recipies to bring the wonderous starting-at-one indexes of Fortran 
to the C world. Boehm fails to recognise the bumped pointers as references 
into reachable data and goes right ahead and deallocates all of your 
numerical arrays for you.

> There is a reason for all this. The major strength of Ocaml runtime is
> its robustness and its efficiency. The efficiency of Ocaml GC is of
> paramount importance (it supports very high allocation rate, which is
> out of reach for the Boehm collector; and big allocation rate is typical
> of most functional programs; the typical allocation speed within the
> Ocaml runtime is at least one or two order of magnitudes faster than
> that of GC_malloc; a typical GC_malloc is by itself a bit slower than a
> libc malloc.).

Regarding OCaml vs libc malloc, I had always assumed that but HLVM appears to 
have proven otherwise. It uses malloc and free directly with no optimization 
whatsoever yet it is now well within 2x the performance of OCaml on the 
allocation and GC intensive 10-queens benchmark.

Boehm's allocator is asymptotically slower than malloc, of course.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] OCaml and Boehm

[Lukasz Stafiniak]

Ouch, we went off-list, that was my mistake...

On Sat, Apr 11, 2009 at 3:33 PM, Basile STARYNKEVITCH
<basile@starynkevitch.net> wrote:
> Lukasz Stafiniak wrote:
>>
>> Can I call OCaml functions from an application that is GCed by Boehm?
>> No pointer goes from GC-Boehm zone to OCaml zone, but there are
>> pointers from OCaml to Boehm GC-malloced values that need to be
>> respected by Boehm GC.
>>
>
> I don't know, you could just try.
>
> If you really wanted to, you could hack Ocaml runtime to call  GC_add_roots
> on every memory segment its allocate. But I would believe that is a bad
> idea.
>
> Maybe adding some extra indirection,  and having the Ocaml -> Boehm pointers
> going thru Ocaml custom data and a Boehm mallocated table might do the
> trick.
>
> A valid answer can only be given you by the few persons who know well both
> Ocaml runtime implementation & Boehm GC implementation (I do know a bit
> about Ocaml runtime, but I did not dive into Boehm's source code). Very
> probably Damien Doligez is the right person to ask.
>
> But why do you want to do such nasty tricks?
>
> What is your application doing? Is it only a prototype which can
> mysteriously crash, or is it a serious program?
>
It is a large application. They debate whether to use Boehm or smart
pointers. They already have embedded Scheme (Guile) and are about to
embed Python. (Guile is said to be Boehm-compatible, in some sense,
from the next version.) It is possible that Boehm is a no-way for
them, I asked here to investigate this.

(Another question which is off-topic for this list is whether smart
pointers in their situation would be a high performance hit.)

Thank You,
Łukasz

Re: [Caml-list] OCaml and Boehm

[Jon Harrop]

On Saturday 11 April 2009 15:11:38 Lukasz Stafiniak wrote:
> (Another question which is off-topic for this list is whether smart
> pointers in their situation would be a high performance hit.)

Depends what "their situation" is. :-)

Smart pointers are adequate for specific domains where performance is 
unimportant and cycles cannot occur, like handling the destruction of GUI 
elements. In general, smart pointers are orders of magnitude slower than 
garbage collection because they bump values in the heap every time they 
change hands.

Also, don't forget that many people incorrectly claim that smart pointers 
deallocate at the earliest possible point when, in fact, they typically keep 
values alive longer than necessary.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] OCaml and Boehm

[Lukasz Stafiniak]

2009/4/11 Jon Harrop <jon@ffconsultancy.com>:
> On Saturday 11 April 2009 15:11:38 Lukasz Stafiniak wrote:
>> (Another question which is off-topic for this list is whether smart
>> pointers in their situation would be a high performance hit.)
>
> Depends what "their situation" is. :-)
>
General performance is very important for them... They plan to use
weak_ptr most of the time.

Re: [Caml-list] OCaml and Boehm

[Basile STARYNKEVITCH]

Lukasz Stafiniak wrote:
>>     
> It is a large application. They debate whether to use Boehm or smart
> pointers. They already have embedded Scheme (Guile) and are about to
> embed Python. (Guile is said to be Boehm-compatible, in some sense,
> from the next version.) It is possible that Boehm is a no-way for
> them, I asked here to investigate this.
>   

My advice is always to avoid mixing several garbage collection 
techniques or implementations inside the same program.

I am not sure "they" are right in embedding both Guile & Python inside 
the same program. I would really avoid doing that, especially if the 
application is long-running or has to be reliable.

Did you consider having a separate Ocaml program (& perhaps also a 
separate Python program) which communicates with that application using 
some communication channel (be it a pipe, a socket, IPC or Posix shared 
memory, ...) which at least provides a separation between various GCs 
and address spaces...


 From what you are suggesting, "your" application seems to be a big 
spaghetti system, very brittle and hard to maintain. I do know that 
these are very common, but I won't like to be at your place... because 
you describe a realistic, but quite nasty, situation (probably more a 
management issue than a technical one).

But beware of  one stuff: GC bugs are hard to find! A single bug could 
mean weeks of efforts!

Regards.

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***

Re: [Caml-list] OCaml and Boehm

[Jon Harrop]

On Saturday 11 April 2009 15:40:11 Lukasz Stafiniak wrote:
> 2009/4/11 Jon Harrop <jon@ffconsultancy.com>:
> > On Saturday 11 April 2009 15:11:38 Lukasz Stafiniak wrote:
> >> (Another question which is off-topic for this list is whether smart
> >> pointers in their situation would be a high performance hit.)
> >
> > Depends what "their situation" is. :-)
>
> General performance is very important for them... They plan to use
> weak_ptr most of the time.

Ok. My advice is to avoid shared pointers if at all possible and rely on a 
robust GC implementation like OCaml's. GC is vastly more efficient and vastly 
less error prone.

I concur with Basile that a loose binding is preferable to a tight binding 
when you have more than one form of deallocation. Message passing is 
generally the easiest solution.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] OCaml and Boehm

[Jon Harrop]

On Saturday 11 April 2009 16:03:56 Basile STARYNKEVITCH wrote:
>  From what you are suggesting, "your" application seems to be a big
> spaghetti system, very brittle and hard to maintain. I do know that
> these are very common, but I won't like to be at your place... because
> you describe a realistic, but quite nasty, situation (probably more a
> management issue than a technical one).

Irish driving directions: "well, I would not start from here". :-)

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] OCaml and Boehm

[Goswin von Brederlow]

Basile STARYNKEVITCH <basile@starynkevitch.net> writes:

> Lukasz Stafiniak wrote:
>> Hi,
>>
>> Is the OCaml runtime Boehm-safe? That is, can it be run with Boehm
>> turned on and traversing OCaml's heap? (So that the OCaml heap can
>> provide roots to Boehm.) And if not, could it be patched to make it
>> Boehm-safe in this sense?
>>
>>
> Probably not. Because I am not sure of what you mean by Boehm-safe,
> since Boehm's GC is conservative and do not make much promises.

It makes the promise that a block that is pointed too is never freed.
(at least for some form of pointed too)

> And very probably, Ocaml runtime cannot realistically be make
> Boehm-safe or even Boehm compatible.

Correct me if I'm wrong but aren't pointers in ocaml always pointing
inside allocated memory instead of its begining? Each block has a
header and the ocaml value points to after the header. So every ocaml
value would be 4/8 bytes offset to the real address of a block.

Can Boehm cope with that at all?

> However, it could happen that you might run some Boehm GC code inside
> Ocaml if you are lucky. You should be sure that no pointer go from
> GC-Boehm zone into Ocaml zone.

And probably the other way around too given the above. But you need
bindings for any non ocaml code you call so you already have stub
functions between ocaml and boehm using code. Any values that pass
between the two you can register with each GC. But I fear Boehm has no
finalize_* equivalent which you would need to tell the ocaml GC a
value as been droped when the Boehm GC frees something.

So I would guess you can't pass ocaml pointers into Boehm GC at all
without manually handling the resource.

> But your question is really too vague. What is the Boehm-GC based code
> you want to run within an Ocaml application, and what is that
> application?
>
> Regards.

MfG
        Goswin

Re: [Caml-list] OCaml and Boehm

[Lukasz Stafiniak]

On Sun, Apr 12, 2009 at 5:34 AM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
>
> Correct me if I'm wrong but aren't pointers in ocaml always pointing
> inside allocated memory instead of its begining? Each block has a
> header and the ocaml value points to after the header. So every ocaml
> value would be 4/8 bytes offset to the real address of a block.
>
> Can Boehm cope with that at all?

Boehm is only supposed to collect the C(++)land values. One can
register the OCaml-boxed pointers that refer to these values as
Boehm-GC roots, and deregister them (?) in the OCaml-finalizers for
the pointers. I don't see anything scary with this approach, provided
(?) is possible. Is the performance penalty as big as with smart
pointers?

Re: [Caml-list] OCaml and Boehm

[Christoph Bauer]

Basile STARYNKEVITCH <basile@starynkevitch.net> writes:

> Lukasz Stafiniak wrote:
>>>     
>> It is a large application. They debate whether to use Boehm or smart
>> pointers. They already have embedded Scheme (Guile) and are about to
>> embed Python. (Guile is said to be Boehm-compatible, in some sense,
>> from the next version.) It is possible that Boehm is a no-way for
>> them, I asked here to investigate this.
>>   
>
> My advice is always to avoid mixing several garbage collection
> techniques or implementations inside the same program.
>

TCL uses refcounted Tcl_Objs. We use these Tcl_Objs in OCaml for a long
time. And it works excellent.

Here are the two most important wrapper functions:

static
void finalize_tclobj( value v ) {
  Tcl_DecrRefCount( TclObj_val (v) );
}

static
value alloc_tcl_obj( Tcl_Obj * obj )
{
  value v = caml_alloc_custom( &tcl_obj_ops, sizeof( Tcl_Obj * ), 0, 1 );
  Tcl_IncrRefCount( obj );
  TclObj_val( v ) = obj;
  return v;
}

So I guess,  it's easier to use smart pointers.

Christoph Bauer

Re: [Caml-list] OCaml and Boehm

[Lukasz Stafiniak]

On Mon, Apr 13, 2009 at 11:42 AM, Christoph Bauer
<c-bauer-olsbruecken@t-online.de> wrote:
> Basile STARYNKEVITCH <basile@starynkevitch.net> writes:
>
>> My advice is always to avoid mixing several garbage collection
>> techniques or implementations inside the same program.
>>
>
> TCL uses refcounted Tcl_Objs. We use these Tcl_Objs in OCaml for a long
> time. And it works excellent.
>
> So I guess,  it's easier to use smart pointers.
>
I'll restate my question: is it the same deal with Boehm, or is it
really more difficult with Boehm? I'm not talking about Boehm starting
from Caml roots -- this would be too difficult I guess (?), although
the only way to get back the full performance. Instead, just as with
smart pointers: every wrapper would register a Boehm-GC root with
GC_MALLOC_UNCOLLECTABLE, and a finalizer would deregister it with
GC_FREE. A performance hit, but at least doesn't hit the C++ code.

Thanks in advance.
Łukasz

Re: [Caml-list] OCaml and Boehm

[Xavier Leroy]

> Is the OCaml runtime Boehm-safe? That is, can it be run with Boehm
> turned on and traversing OCaml's heap? (So that the OCaml heap can
> provide roots to Boehm.)

I conjecture the answer is "yes", although it's hard to tell for sure
without a precise specification of what is/is not OK with the
Boehm-Demers-Weiser collector.

>From the standpoint of this collector, OCaml's heap is just a set of
large-ish blocks allocated with malloc()  (*) and containing a zillion
pointers within those blocks.  OCaml doesn't play any dirty tricks
with pointers: no xoring of two pointers, no pointers represented as
offsets from a base, no pointers one below or one above a malloc-ed
block.  Most pointers are word-aligned but we sometimes play tricks
with the low 2 bits.

Of course, almost all Caml pointers point inside those malloc-ed
blocks, not to the beginning, but I'm confident that the B-D-W collector
can handle this, otherwise it would fail on pretty much any existing C
code.

This said, I agree with Basile that what you're trying to achieve
(coexistence between several GCs) is risky, and that a design based on
message passing and separated memory spaces would be more robust, if
feasible.

- Xavier Leroy


(*) In 3.10 and earlier releases, OCaml sometimes used mmap() instead
of malloc() to obtain these blocks.  Starting from 3.11, malloc() is
the only interface OCaml uses to obtain memory from the OS.

Re: [Caml-list] OCaml and Boehm

[Goswin von Brederlow]

Lukasz Stafiniak <lukstafi@gmail.com> writes:

> On Mon, Apr 13, 2009 at 11:42 AM, Christoph Bauer
> <c-bauer-olsbruecken@t-online.de> wrote:
>> Basile STARYNKEVITCH <basile@starynkevitch.net> writes:
>>
>>> My advice is always to avoid mixing several garbage collection
>>> techniques or implementations inside the same program.
>>>
>>
>> TCL uses refcounted Tcl_Objs. We use these Tcl_Objs in OCaml for a long
>> time. And it works excellent.
>>
>> So I guess,  it's easier to use smart pointers.
>>
> I'll restate my question: is it the same deal with Boehm, or is it
> really more difficult with Boehm? I'm not talking about Boehm starting
> from Caml roots -- this would be too difficult I guess (?), although
> the only way to get back the full performance. Instead, just as with
> smart pointers: every wrapper would register a Boehm-GC root with
> GC_MALLOC_UNCOLLECTABLE, and a finalizer would deregister it with
> GC_FREE. A performance hit, but at least doesn't hit the C++ code.
>
> Thanks in advance.
> £ukasz

That would work. But only allows data to go in one direction. That way
Ocaml can use pointers into the Boehm heap but you can not use
pointers into the ocaml heap.

MfG
        Goswin

Re: [Caml-list] OCaml and Boehm

[Goswin von Brederlow]

Jon Harrop <jon@ffconsultancy.com> writes:

> On Saturday 11 April 2009 20:17:58 Ed Keith wrote:
>> --- On Sat, 4/11/09, Jon Harrop <jon@ffconsultancy.com> wrote:
>> > From: Jon Harrop <jon@ffconsultancy.com>
>> > Subject: Re: [Caml-list] OCaml and Boehm
>> > To: caml-list@yquem.inria.fr
>> > Date: Saturday, April 11, 2009, 10:27 AM
>> >
>> > Also, don't forget that many people incorrectly claim that smart pointers
>> > deallocate at the earliest possible point when, in fact, they typically
>> > keep values alive longer than necessary.
>>
>> Could elaborate on this? I'm having a hard time envisioning a situation
>> where GC could free memory that smart pointers would not free.
>
> Smart pointers deallocate when values fall out of scope. GC deallocates when 
> it runs and values are unreachable.
>
> Consider:
>
>   let () =
>     let x = ..
>     f x
>     g()
>
> The value "x" stays in scope to the end of the block so a smart pointer will 
> not deallocate it. The GC may well run during "g", realise that "x" is 
> unreachable and deallocate it.
>
> Note that there are further unwanted side effects of smart pointers here. 
> Specifically, having to keep "x" around until the end of scope increases 
> register pressure and makes it more likely to values will be spilled, which 
> is a substantial performance cost.

How about cyclic records:

type r = { next : r }

let rec r1 { next = r2 } and r2 = { next = r1 }

Smart pointers will never free that since r1 kees r2 alive and r2
keeps r1 alive.

MfG
        Goswin

Re: [Caml-list] OCaml and Boehm

[Jon Harrop]

On Saturday 11 April 2009 20:17:58 Ed Keith wrote:
> --- On Sat, 4/11/09, Jon Harrop <jon@ffconsultancy.com> wrote:
> > From: Jon Harrop <jon@ffconsultancy.com>
> > Subject: Re: [Caml-list] OCaml and Boehm
> > To: caml-list@yquem.inria.fr
> > Date: Saturday, April 11, 2009, 10:27 AM
> >
> > Also, don't forget that many people incorrectly claim that smart pointers
> > deallocate at the earliest possible point when, in fact, they typically
> > keep values alive longer than necessary.
>
> Could elaborate on this? I'm having a hard time envisioning a situation
> where GC could free memory that smart pointers would not free.

Smart pointers deallocate when values fall out of scope. GC deallocates when 
it runs and values are unreachable.

Consider:

  let () =
    let x = ..
    f x
    g()

The value "x" stays in scope to the end of the block so a smart pointer will 
not deallocate it. The GC may well run during "g", realise that "x" is 
unreachable and deallocate it.

Note that there are further unwanted side effects of smart pointers here. 
Specifically, having to keep "x" around until the end of scope increases 
register pressure and makes it more likely to values will be spilled, which 
is a substantial performance cost.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] OCaml and Boehm

[Ed Keith]

--- On Sat, 4/11/09, Jon Harrop <jon@ffconsultancy.com> wrote:

> From: Jon Harrop <jon@ffconsultancy.com>
> Subject: Re: [Caml-list] OCaml and Boehm
> To: caml-list@yquem.inria.fr
> Date: Saturday, April 11, 2009, 10:27 AM
> 
> Also, don't forget that many people incorrectly claim that smart pointers 
> deallocate at the earliest possible point when, in fact, they typically keep 
> values alive longer than necessary.

Could elaborate on this? I'm having a hard time envisioning a situation where GC could free memory that smart pointers would not free. 

  -EdK

Ed Keith
e_d_k@yahoo.com

Blog: edkeith.blogspot.com