From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 22B2F7EE25 for ; Wed, 6 Nov 2013 14:39:41 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of jean.krivine@gmail.com) identity=pra; client-ip=209.85.212.169; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jean.krivine@gmail.com"; x-sender="jean.krivine@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of jean.krivine@gmail.com designates 209.85.212.169 as permitted sender) identity=mailfrom; client-ip=209.85.212.169; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jean.krivine@gmail.com"; x-sender="jean.krivine@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-wi0-f169.google.com) identity=helo; client-ip=209.85.212.169; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jean.krivine@gmail.com"; x-sender="postmaster@mail-wi0-f169.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Aq4FAAZGelLRVdSplGdsb2JhbABagz9TtnqIQ4EbCBYOAQEBAQcLCwkSKoIlAQEEAUABFAcdAQMBCwYFCwM4IgERAQUBHAYTCYdlAQMJBg2gGoxXgwmEJwoZJw1kiQEBBQyPJyYHhDADliSBaIEvjm8YKYRSOw X-IPAS-Result: Aq4FAAZGelLRVdSplGdsb2JhbABagz9TtnqIQ4EbCBYOAQEBAQcLCwkSKoIlAQEEAUABFAcdAQMBCwYFCwM4IgERAQUBHAYTCYdlAQMJBg2gGoxXgwmEJwoZJw1kiQEBBQyPJyYHhDADliSBaIEvjm8YKYRSOw X-IronPort-AV: E=Sophos;i="4.93,647,1378850400"; d="scan'208";a="34023347" Received: from mail-wi0-f169.google.com ([209.85.212.169]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 06 Nov 2013 14:39:40 +0100 Received: by mail-wi0-f169.google.com with SMTP id cb5so4837127wib.4 for ; Wed, 06 Nov 2013 05:39:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=aWQ4HZkVqlxgMRRNKcjxsY/81kbu517/+a4r5iadh7g=; b=vl4rrTgBXX1XjMxC8lEtHRLmXzB8SpO3LCYUxSK7mKJ+EqfoPwLYF3ERCubfYm/ZR/ 9MCTH1wQ2rXiGdTE1cLcThp8DT8Dd5375BaDjkslfRGASB5x9570TRLk5FthSxCPlM4b W8gXYhuw8lHf/ASAyL1g2Bq4jZ9Mvh99l+S+8kGo38oP9lhUEjIFEfEJ7QI4TslfE7TV nAv3RJqQfYfZeyMNJaY0LkSguC2SZfYmRJq2JrjstjuKKmuuHTwxYWH+u1CzgsuBGeN7 ZHUH/EIXWLYFSJ+htMJlkZ4LNRRH5DadpTi/R8kvoEwofmzT/a4p7YKpU9lesQxZW6tC YDaA== X-Received: by 10.194.3.78 with SMTP id a14mr122856wja.77.1383745179617; Wed, 06 Nov 2013 05:39:39 -0800 (PST) MIME-Version: 1.0 Received: by 10.194.87.195 with HTTP; Wed, 6 Nov 2013 05:39:19 -0800 (PST) In-Reply-To: <1383743414.4083.47.camel@zotac> References: <1383743414.4083.47.camel@zotac> From: Jean Krivine Date: Wed, 6 Nov 2013 14:39:19 +0100 Message-ID: To: Gerd Stolpmann Cc: caml users Content-Type: multipart/alternative; boundary=047d7b343d6ae411d304ea82477a Subject: Re: [Caml-list] out-of-the-heap 'a arrays ? --047d7b343d6ae411d304ea82477a Content-Type: text/plain; charset=ISO-8859-1 That looks great thanks, I'll look into it ! J On Wed, Nov 6, 2013 at 2:10 PM, Gerd Stolpmann 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 > ------------------------------------------------------------ > --047d7b343d6ae411d304ea82477a Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
That looks great thanks, I'll look into it !

<= /div>
J


On Wed, Nov 6, 2013 at 2:10 PM, Gerd Stolpmann = <info@gerd-s= tolpmann.de> wrote:
Am Dienstag, den 05.11.2013, 18:07 +0100 sch= rieb 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.<= br> > 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<= br> > 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<= br> > for basic array types.
>
>
> To summarize my question: is there a (reasonable) way to implement an<= br> > 'a array out of the ocaml heap ?

Yes, but it's cumbersome. I did that for the Netmulticore l= ibrary 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/proje= cts/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 especial= ly 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 interprete= d 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). Net= sys_mem.as_value returns the pointer to the structure in the bigarray as &q= uot;normal" OCaml value pointer.

E.g.

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

let mem_size =3D 100000
let arr_size =3D 10
let mem =3D
=A0 Bigarray.Array1.create Bigarray.char Bigarray.c_layout mem_size
let (offs,blen) =3D
=A0 Netsys_mem.init_array mem 0 arr_size
let arr_ooh =3D
=A0 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 =3D ref blen
for k =3D 0 to arr_size-1 do
=A0 let v =3D { n =3D 5*k } in =A0 (* some random contents *)
=A0 let (v_offs, v_blen) =3D
=A0 =A0 Netsys_mem.init_value mem !next v [] in
=A0 let v_ooh =3D
=A0 =A0 Netsys_mem.as_value mem v_offs in
=A0 arr_ooh.(k) <- v_ooh; =A0 =A0 =A0(* out-of-heap assignment, see belo= w *)
=A0 next :=3D !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 =A0 =A0gerd@gerd-stolpmann.de
My OCaml site: =A0 =A0 =A0 =A0 =A0http://www.camlcity.org
Contact details: =A0 =A0 =A0 =A0http://www.camlcity.org/contact.html
Company homepage: =A0 =A0 =A0 http://www.gerd-stolpmann.de
------------------------------------------------------------

--047d7b343d6ae411d304ea82477a--