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