[Caml-list] out-of-the-heap 'a arrays ?

[Caml-list] out-of-the-heap 'a arrays ?

[Jean Krivine]

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

Dear all

I am developing a graph rewriting algorithm which operates on large graphs.
Because of the large data structure the GC becomes quite inefficient for
two reasons that I am inferring:
1/ there is no correlation between the time of allocation of an object and
its likelihood to be garbage collected.
2/ even when there is nothing to collect, I guess that the GC is still
inspecting the heap.

Point 1 is inducing some memory leak and point 2 is just inefficient. I
think I took care of point 1 by using my own allocation heap (so there is
nothing to collect for the GC). But to take care of point 2 I guess I need
to tell the GC that my heap (an extensible array) should not be inspected.

As far as I understand there is a module Ancient which I can use to tell
the GC to ignore my array but, if I understand well, it would only work if
I use my array in a read only fashion.
I also thought I could use Bigarray, but it seems it can only be used for
basic array types.

To summarize my question: is there a (reasonable) way to implement an 'a
array out of the ocaml heap ?

Thanks!
JK

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

Re: [Caml-list] out-of-the-heap 'a arrays ?

[Lukasz Stafiniak]

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

On Tue, Nov 5, 2013 at 6:07 PM, Jean Krivine <jean.krivine@gmail.com> wrote:

>
> As far as I understand there is a module Ancient which I can use to tell
> the GC to ignore my array but, if I understand well, it would only work if
> I use my array in a read only fashion.
>

You cannot have pointers from Ancient heap to OCaml heap unless you do weak
pointer management (e.g. in the finalizer of a value). Otherwise I think
you're fine with modifying Ancient.

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

Re: [Caml-list] out-of-the-heap 'a arrays ?

[Lukasz Stafiniak]

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

On Tue, Nov 5, 2013 at 8:06 PM, Lukasz Stafiniak <lukstafi@gmail.com> wrote:

> On Tue, Nov 5, 2013 at 6:07 PM, Jean Krivine <jean.krivine@gmail.com>wrote:
>
>>
>> As far as I understand there is a module Ancient which I can use to tell
>> the GC to ignore my array but, if I understand well, it would only work if
>> I use my array in a read only fashion.
>>
>
> You cannot have pointers from Ancient heap to OCaml heap unless you do
> weak pointer management (e.g. in the finalizer of a value). Otherwise I
> think you're fine with modifying Ancient.
>

Scratch that, totally thoughtless -- of course values are moved around so
you cannot have pointers from Ancient heap to OCaml heap, period.

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

Re: [Caml-list] out-of-the-heap 'a arrays ?

[Jean Krivine]

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

It seems that Ancient requires the values that are moved to be immutable
full point. I understand that there is a problem if you have pointers from
Ancient Heap to Ocaml Heap. But what about pointers that are internal to
the Ancient Heap ? Am I talking nonsense? Sorry if I do.

J


On Tue, Nov 5, 2013 at 8:15 PM, Lukasz Stafiniak <lukstafi@gmail.com> wrote:

> On Tue, Nov 5, 2013 at 8:06 PM, Lukasz Stafiniak <lukstafi@gmail.com>wrote:
>
>> On Tue, Nov 5, 2013 at 6:07 PM, Jean Krivine <jean.krivine@gmail.com>wrote:
>>
>>>
>>> As far as I understand there is a module Ancient which I can use to tell
>>> the GC to ignore my array but, if I understand well, it would only work if
>>> I use my array in a read only fashion.
>>>
>>
>> You cannot have pointers from Ancient heap to OCaml heap unless you do
>> weak pointer management (e.g. in the finalizer of a value). Otherwise I
>> think you're fine with modifying Ancient.
>>
>
> Scratch that, totally thoughtless -- of course values are moved around so
> you cannot have pointers from Ancient heap to OCaml heap, period.
>

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

Re: [Caml-list] out-of-the-heap 'a arrays ?

[Richard W.M. Jones]

On Wed, Nov 06, 2013 at 10:19:42AM +0100, Jean Krivine wrote:
> It seems that Ancient requires the values that are moved to be immutable
> full point. I understand that there is a problem if you have pointers from
> Ancient Heap to Ocaml Heap. But what about pointers that are internal to
> the Ancient Heap ? Am I talking nonsense? Sorry if I do.

You can definitely create pointers between ancient objects.  You
just have to be really careful about what you're doing.

It's not too hard to understand -- I would suggest reading
the implementation.

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] out-of-the-heap 'a arrays ?

[Francois Berenger]

On 11/06/2013 02:07 AM, Jean Krivine wrote:
> Dear all
>
> I am developing a graph rewriting algorithm which operates on large
> graphs.

Doesn't the graph library from LRI allow to work efficiently
even on large graphs?

# opam info ocamlgraph
package: ocamlgraph
version: 1.8.3
upstream-url: http://ocamlgraph.lri.fr/download/ocamlgraph-1.8.3.tar.gz
homepage: http://ocamlgraph.lri.fr/
author: Sylvain Conchon, Jean-Christophe Filliâtre, Julien Signoles
license: GNU Library General Public License version 2.1
doc: http://ocamlgraph.lri.fr/doc
tags: graph, library, algorithms, directed graph, vertice, edge, 
persistent, imperative
description: A generic graph library for OCaml

Re: [Caml-list] out-of-the-heap 'a arrays ?

[Gerd Stolpmann]

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

Am Dienstag, den 05.11.2013, 18:07 +0100 schrieb Jean Krivine:
> Dear all
> 
> 
> I am developing a graph rewriting algorithm which operates on large
> graphs. Because of the large data structure the GC becomes quite
> inefficient for two reasons that I am inferring: 
> 1/ there is no correlation between the time of allocation of an object
> and its likelihood to be garbage collected.
> 2/ even when there is nothing to collect, I guess that the GC is still
> inspecting the heap.
> 
> 
> Point 1 is inducing some memory leak and point 2 is just inefficient.
> I think I took care of point 1 by using my own allocation heap (so
> there is nothing to collect for the GC). But to take care of point 2 I
> guess I need to tell the GC that my heap (an extensible array) should
> not be inspected.
> 
> 
> As far as I understand there is a module Ancient which I can use to
> tell the GC to ignore my array but, if I understand well, it would
> only work if I use my array in a read only fashion. 
> I also thought I could use Bigarray, but it seems it can only be used
> for basic array types.
> 
> 
> To summarize my question: is there a (reasonable) way to implement an
> 'a array out of the ocaml heap ? 

Yes, but it's cumbersome. I did that for the Netmulticore library of
Ocamlnet.

Here are the basics: You can have a pointer from the normal heap to
other memory, and the GC will not follow it. You cannot have pointers
the other way round, because the GC may move in-heap memory, and there
is no mechanism to update such inverse pointers.

In Ocamlnet you find the required support functions in
http://projects.camlcity.org/projects/dl/ocamlnet-3.7.3/doc/html-main/Netsys_mem.html. This functionality shares the same basic ideas of Ancient, but is more complete, and especially supports read-write modifications of out-of-heap values in a reasonable way. Out-of-heap memory is here encapsulated as bigarrays. With Netsys_mem.init_array you can initialize bigarrays so their contents can be interpreted as Ocaml array. With Netsys_mem.init_value you can copy arbitrary values to bigarrays (i.e. for initializing/setting the elements of the array). Netsys_mem.as_value returns the pointer to the structure in the bigarray as "normal" OCaml value pointer.

E.g.

type elem = { n : int }
type arr = elem array

let mem_size = 100000
let arr_size = 10
let mem =
  Bigarray.Array1.create Bigarray.char Bigarray.c_layout mem_size
let (offs,blen) =
  Netsys_mem.init_array mem 0 arr_size
let arr_ooh =
  Netsys_mem.as_value mem offs

Now arr_ooh contains invalid pointers (which doesn't matter for the
moment because the GC will not inspect them). Here is how to set all
elements to some contents:

let next = ref blen
for k = 0 to arr_size-1 do
  let v = { n = 5*k } in   (* some random contents *)
  let (v_offs, v_blen) =
    Netsys_mem.init_value mem !next v [] in
  let v_ooh =
    Netsys_mem.as_value mem v_offs in
  arr_ooh.(k) <- v_ooh;      (* out-of-heap assignment, see below *)
  next := !next + v_blen
done

Of course, you need to do your own memory-management here (there are
higher-level functions in Ocamlnet for that, see the Netmulticore
library).

So finally you get an initialized out-of-heap array arr_ooh residing
within the bigarray.

The assignment arr_ooh.(k) <- v_ooh needs some further discussion. Until
OCaml-4.00.1 this was fully supported by the OCaml runtime. OCaml-4.01.0
includes a change that disallows to modify out-of-heap memory with
normal OCaml assignment operators. Ocamlnet contains a workaround (which
works by overriding the changed caml_initialize and caml_modify
functions with their old definitions), and it is automatically enabled
if you add -package netmulticore at link time. The workaround is
incompatible with non-custom bytecode links, though.

Gerd


> 
> 
> Thanks!
> JK

-- 
------------------------------------------------------------
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] out-of-the-heap 'a arrays ?

[Jean Krivine]

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

That looks great thanks, I'll look into it !

J


On Wed, Nov 6, 2013 at 2:10 PM, Gerd Stolpmann <info@gerd-stolpmann.de>wrote:

> Am Dienstag, den 05.11.2013, 18:07 +0100 schrieb Jean Krivine:
> > Dear all
> >
> >
> > I am developing a graph rewriting algorithm which operates on large
> > graphs. Because of the large data structure the GC becomes quite
> > inefficient for two reasons that I am inferring:
> > 1/ there is no correlation between the time of allocation of an object
> > and its likelihood to be garbage collected.
> > 2/ even when there is nothing to collect, I guess that the GC is still
> > inspecting the heap.
> >
> >
> > Point 1 is inducing some memory leak and point 2 is just inefficient.
> > I think I took care of point 1 by using my own allocation heap (so
> > there is nothing to collect for the GC). But to take care of point 2 I
> > guess I need to tell the GC that my heap (an extensible array) should
> > not be inspected.
> >
> >
> > As far as I understand there is a module Ancient which I can use to
> > tell the GC to ignore my array but, if I understand well, it would
> > only work if I use my array in a read only fashion.
> > I also thought I could use Bigarray, but it seems it can only be used
> > for basic array types.
> >
> >
> > To summarize my question: is there a (reasonable) way to implement an
> > 'a array out of the ocaml heap ?
>
> Yes, but it's cumbersome. I did that for the Netmulticore library of
> Ocamlnet.
>
> Here are the basics: You can have a pointer from the normal heap to
> other memory, and the GC will not follow it. You cannot have pointers
> the other way round, because the GC may move in-heap memory, and there
> is no mechanism to update such inverse pointers.
>
> In Ocamlnet you find the required support functions in
>
> http://projects.camlcity.org/projects/dl/ocamlnet-3.7.3/doc/html-main/Netsys_mem.html.
> This functionality shares the same basic ideas of Ancient, but is more
> complete, and especially supports read-write modifications of out-of-heap
> values in a reasonable way. Out-of-heap memory is here encapsulated as
> bigarrays. With Netsys_mem.init_array you can initialize bigarrays so their
> contents can be interpreted as Ocaml array. With Netsys_mem.init_value you
> can copy arbitrary values to bigarrays (i.e. for initializing/setting the
> elements of the array). Netsys_mem.as_value returns the pointer to the
> structure in the bigarray as "normal" OCaml value pointer.
>
> E.g.
>
> type elem = { n : int }
> type arr = elem array
>
> let mem_size = 100000
> let arr_size = 10
> let mem =
>   Bigarray.Array1.create Bigarray.char Bigarray.c_layout mem_size
> let (offs,blen) =
>   Netsys_mem.init_array mem 0 arr_size
> let arr_ooh =
>   Netsys_mem.as_value mem offs
>
> Now arr_ooh contains invalid pointers (which doesn't matter for the
> moment because the GC will not inspect them). Here is how to set all
> elements to some contents:
>
> let next = ref blen
> for k = 0 to arr_size-1 do
>   let v = { n = 5*k } in   (* some random contents *)
>   let (v_offs, v_blen) =
>     Netsys_mem.init_value mem !next v [] in
>   let v_ooh =
>     Netsys_mem.as_value mem v_offs in
>   arr_ooh.(k) <- v_ooh;      (* out-of-heap assignment, see below *)
>   next := !next + v_blen
> done
>
> Of course, you need to do your own memory-management here (there are
> higher-level functions in Ocamlnet for that, see the Netmulticore
> library).
>
> So finally you get an initialized out-of-heap array arr_ooh residing
> within the bigarray.
>
> The assignment arr_ooh.(k) <- v_ooh needs some further discussion. Until
> OCaml-4.00.1 this was fully supported by the OCaml runtime. OCaml-4.01.0
> includes a change that disallows to modify out-of-heap memory with
> normal OCaml assignment operators. Ocamlnet contains a workaround (which
> works by overriding the changed caml_initialize and caml_modify
> functions with their old definitions), and it is automatically enabled
> if you add -package netmulticore at link time. The workaround is
> incompatible with non-custom bytecode links, though.
>
> Gerd
>
>
> >
> >
> > Thanks!
> > JK
>
> --
> ------------------------------------------------------------
> 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: Type: text/html, Size: 5686 bytes --]

Re: [Caml-list] out-of-the-heap 'a arrays ?

[Richard W.M. Jones]

On Tue, Nov 05, 2013 at 06:07:42PM +0100, Jean Krivine wrote:
> As far as I understand there is a module Ancient which I can use to tell
> the GC to ignore my array but, if I understand well, it would only work if
> I use my array in a read only fashion.

I don't think you're reading this right.  You can mutate the ancient
heap data (eg. if it's an array of ints, updating an int), you just
have to be very careful not to create a pointer from ancient data to
the OCaml heap.

It's probably worth reviewing how ocaml-ancient is implemented.  It's
not that hard to understand.

Rich.

-- 
Richard Jones
Red Hat