From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by c5ff346549e7 (Postfix) with ESMTP id 4D3635D4 for ; Thu, 20 Dec 2018 00:30:10 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.56,374,1539640800"; d="scan'208,217";a="361136873" Received: from sympa.inria.fr ([193.51.193.213]) by mail2-relais-roc.national.inria.fr with ESMTP; 20 Dec 2018 01:30:09 +0100 Received: by sympa.inria.fr (Postfix, from userid 20132) id 20C2882566; Thu, 20 Dec 2018 01:30:09 +0100 (CET) Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 56D50824CF for ; Thu, 20 Dec 2018 01:30:02 +0100 (CET) Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=lindsay.errington@gmail.com; spf=Pass smtp.mailfrom=lindsay.errington@gmail.com; spf=None smtp.helo=postmaster@mail-yb1-f173.google.com IronPort-PHdr: =?us-ascii?q?9a23=3Acg5GVRMJhoZKXSAe7mkl6mtUPXoX/o7sNwtQ0KIM?= =?us-ascii?q?zox0LfT9rarrMEGX3/hxlliBBdydt6oUzbKO+4nbGkU4qa6bt34DdJEeHzQksu?= =?us-ascii?q?4x2zIaPcieFEfgJ+TrZSFpVO5LVVti4m3peRMNQJW2aFLduGC94iAPERvjKwV1?= =?us-ascii?q?Ov71GonPhMiryuy+4ZLebxlLiTanfb9+MAi9oBnMuMURnYZsMLs6xAHTontPde?= =?us-ascii?q?RWxGdoKkyWkh3h+Mq+/4Nt/jpJtf45+MFOTav1f6IjTbxFFzsmKHw65NfqtRbY?= =?us-ascii?q?UwSC4GYXX3gMnRpJBwjF6wz6Xov0vyDnuOdxxDWWMMvrRr0yRD+s7bpkSAXwhS?= =?us-ascii?q?gINzA3/mLZhNFugq1Hux+uvQBzzpTObY2JKPZzfKXQds4aS2pbWcZRUjRMDIW9?= =?us-ascii?q?b4sJEuUBJvxXrongrFUBtxu+HwisBOXgyj9UgX/227Ax3uMlEQHH2gwvAskOv2?= =?us-ascii?q?7UrdnvKqgSS/q1zKjOzTXMc/NW3jH95ZPHchAku/6MXLZwfdDNxkkoEgPIl1Od?= =?us-ascii?q?opHrMTOS0+QCqWmb7+x4WOKgim4ntwFxoiW0ycs2lobJgYcVx1bZ/it62IY4Pc?= =?us-ascii?q?O0RFJ/bNK+E5ZdtzuWO5VrTs4mWW1kpSQ3x7MAtJWmZiYF0o4nyATaa/Gfc4iH?= =?us-ascii?q?/BbjVOGJLDd9nn1leba/iw+y8Ee71+HwT8e03EtIoydLiNXMuXcN1xvc6siDVP?= =?us-ascii?q?Rx5Fuu2TGK1wzL6+FEJ147lbbDJpI/3rI9koAfvEfDEyPshkn6kaubel859uWq?= =?us-ascii?q?5enrerDmqYWdN49whAH+KKMumsmnDOQ8MwgOWXWU+f+m27zj50H2Xq9Kjuc3kq?= =?us-ascii?q?nfv5DaOcMbpqiiDg9a14Ys8Re/DzO83NsEmnkHKUpJeAibgIjxJ1HOPPf4AO+j?= =?us-ascii?q?jFu2lTdrw+nKPrngApXWMnjOi6zhfLZ4605E0gU/19Ff55ROCrEAOv3/QEHxtM?= =?us-ascii?q?aLRiM+Zge9xuKiDNRmyqsfX3iOC+mXKvD8q1iNs8YuJeWXbZ5dlSznKv4q+/no?= =?us-ascii?q?xSs9mFkRZqC4m5YNcnG+EehhJW2WZHPthpEKFmJc7Vl2d/DjlFDXCW0bXH21Ra?= =?us-ascii?q?9pvmhqWrLjNp/KQ8WWuJLE2S66GpNMYWUfUwKDFH7pc8OPXPJeMXvOcP8kqSQN?= =?us-ascii?q?UP2ac6FkzQun7VaoxL9uL+6S8Sod58q6iYpFotbLnBR3zgRaSsSQ12bXETNxl2?= =?us-ascii?q?IMAi48heVx+BMmjFiE1qd8jrpTEtkBv/4=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0BHBwDl4Rpchq3bVdFkghmCaA9zJ4N9g?= =?us-ascii?q?R2CXpw8j0MNI4RJgm0aBwEENQUMAQMBAQIBAQEBARMBAQEICwsIKSMMgjYigmY?= =?us-ascii?q?EJAQZARseAwERAw03AiQBEQEFAYNXAYFoAQMNCA+MBIxpgx88ixl8FgUBF4J3B?= =?us-ascii?q?YExAYMNChknDV6BNwIBBRKMLYFXP4dBAoIOgluCVwKQVpBeBwKBajsEhGeKUhi?= =?us-ascii?q?BXo97ik2DdIsyDyGBPYF2TSNQMYI7gjWDU4p0ITAKjl0BAQ?= X-IPAS-Result: =?us-ascii?q?A0BHBwDl4Rpchq3bVdFkghmCaA9zJ4N9gR2CXpw8j0MNI4R?= =?us-ascii?q?Jgm0aBwEENQUMAQMBAQIBAQEBARMBAQEICwsIKSMMgjYigmYEJAQZARseAwERA?= =?us-ascii?q?w03AiQBEQEFAYNXAYFoAQMNCA+MBIxpgx88ixl8FgUBF4J3BYExAYMNChknDV6?= =?us-ascii?q?BNwIBBRKMLYFXP4dBAoIOgluCVwKQVpBeBwKBajsEhGeKUhiBXo97ik2DdIsyD?= =?us-ascii?q?yGBPYF2TSNQMYI7gjWDU4p0ITAKjl0BAQ?= X-IronPort-AV: E=Sophos;i="5.56,374,1539640800"; d="scan'208,217";a="361136813" Received: from mail-yb1-f173.google.com ([209.85.219.173]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 20 Dec 2018 01:30:01 +0100 Received: by mail-yb1-f173.google.com with SMTP id m129so8637420ybf.9 for ; Wed, 19 Dec 2018 16:30:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=ZPm1uq8wHSEBJ/R1jo8UOFG+MObWAIMd6gncEnbO7oQ=; b=ouE7hQhAmKfKKLxI/QBlFaFQoT4NLuLoZwwdAlrEcacrlarjQe3vtAJPlhaGg9WoQ4 7wChpAzhU9qQb+KB2i1jK7Btje65xB+qJbQoCBnFsdi/UaDes/38iTknbe8bBfUfYhdA X++FzpByizZCWoL7vkz3/OwaX4cVM9i4x38K/zzD2EgN2XxaqWahxtH485TF3Kr0JxcY THqpcOABWfTxRBL24zoxMBk9kK12LYB1RUDNkZ/W3rqr3vzEg+u4TBH+dA0S/NZh3bkO 8nKYQES4dl9AMwpqfqN7n7hJi1Wo8/sJJOWW/GSm8PgPgX/egSXwuGBeKgdLTlnvn5QO kIzg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=ZPm1uq8wHSEBJ/R1jo8UOFG+MObWAIMd6gncEnbO7oQ=; b=KlCJDOrWwRHY1ePfpzyLGUK4cV5HsMmhtBJt6JskncBKGOGiLNTdBb8KpyRD0vuWQo IZ/tYilvd5l0w1F7812M09n40uYNJLe+xd85vIzgcGMMDkEh1qCVKwpdMb/MO7vjEtzd WmOF91gmbgqrdK6P/wz1/S8Ke8QuFdOt4s7rd/ogMSEx58KnplRdUvSCCZvlyYE+cU+B iZT/LMxe2gqG2MpNA+sOuSCt5WCbou4YeWFoXj7JnUBgGSxPNpHqevE8hryGCQn/4eUn bHTaeZD6bgWTypUNY6b++m21eC27o2V7LH7IZ6NDAFjZG36R4mEAayCCGrbvETXHLibv FfSg== X-Gm-Message-State: AA+aEWbD2Rg+rZr+2I9d1VgVnTFeF3yOSYxx7HEvrHk83ttjTrluObBZ d0xn2DjZAcLclJ2oKQzCWN86TV9UDHMhqZJsTV5T8Ayi X-Google-Smtp-Source: AFSGD/X6qqZUXazOvGevXlU259wfYJwyNDtzqdDtLr0NBydNRVwu1snzegE1lV1WipN+vXsMwO34kZ26nN643MXB2is= X-Received: by 2002:a25:fc17:: with SMTP id v23mr23386314ybd.269.1545265799292; Wed, 19 Dec 2018 16:29:59 -0800 (PST) MIME-Version: 1.0 From: Lindsay Errington Date: Wed, 19 Dec 2018 16:29:48 -0800 Message-ID: To: caml-list@inria.fr Content-Type: multipart/alternative; boundary="0000000000000cf021057d693b8f" Subject: [Caml-list] Possible ephemeron bug? Reply-To: Lindsay Errington X-Loop: caml-list@inria.fr X-Sequence: 17253 Errors-to: caml-list-owner@inria.fr Precedence: list Precedence: bulk Sender: caml-list-request@inria.fr X-no-archive: yes List-Id: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --0000000000000cf021057d693b8f Content-Type: text/plain; charset="UTF-8" I'm trying to implement weak functional maps with ephemerons. Within the repl, things work fine. When I use the native or bytecode compilers, it looks like some things are not being collected. To illustrate, I'll use maps implemented as association lists. Complete source at https://gist.github.com/dlindsaye/66afcdef6f381e955d8c66773365d4d6 Keys are boxed integers: > type key = Key of int Values are elements of an algebraic type with references to keys: > type value = > | Str of string > | Link of key Elements of the association list are key/value pairs wrapped in an ephemeron: > module Eph = Ephemeron.K1 > type pair = (key,value) Eph.t > let mk_pair key value = > let eph = Eph.create () in > Eph.set_key eph key; > Eph.set_data eph value; > eph The following adds a new key/value pair to the assoc list: > let intern idx value map = > let key = Key idx in > let eph = mk_pair key value in > let map = eph::map in > (key,map) Next a function to update a key/value pair: > let rec upd key new_value map = > match map with > | [] -> raise Not_found > | pair::rest -> > begin > match Eph.get_key pair with > | Some other_key when eq_key key other_key -> > let eph = mk_pair key new_value in > eph::rest > | _ -> pair::(upd key new_value rest) > end Next, create a list of pairs: > let str n = Str (String.make n '#');; (* Ensure value is boxed *) > let (root,map) = > let map = [] in > let (k0,map) = intern 0 (str 1) map in > let (k1,map) = intern 1 (Link k0) map in > let (k2,map) = intern 2 (Link k1) map in > (k2,map);; Printing this yields: > root=(Key 2), map=(Eph ((Key 2),(Link (Key 1)))) > (Eph ((Key 1),(Link (Key 0)))) > (Eph ((Key 0),(Str #))) Next, update the root of the tree: > let map = upd root (str 2) map;; Which correctly binds (Key 2) to a string of length 2: > root=(Key 2) map1=(Eph ((Key 2),(Str ##))) > (Eph ((Key 1),(Link (Key 0)))) > (Eph ((Key 0),(Str #))) Invoking gc from within the repl and printing again yields: > Gc.full_major ();; > root=(Key 2) map1=(Eph ((Key 2),(Str ##))) > (Eph (None,None)) > (Eph (None,None)) which is exactly what one would expect. If however, I use the standalone bytecode compiler or the native compiler (4.07.1), then the entries are not nullified. Is this a bug or is there another way to persuade the garbage collector to clobber the entries? Thanks Lindsay -- Caml-list mailing list. Subscription management and archives: https://sympa.inria.fr/sympa/arc/caml-list https://inbox.ocaml.org/caml-list Forum: https://discuss.ocaml.org/ Bug reports: http://caml.inria.fr/bin/caml-bugs --0000000000000cf021057d693b8f Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I'm trying to implement weak functional maps with ephe= merons. Within the repl, things work fine. When I use the native or bytecod= e compilers, it looks like some things are not being collected.

To illustrate, I'll use maps implemented as association lists. = Complete source at https://gist.github.com/dlindsaye/66afcdef6f381e955d= 8c66773365d4d6

Keys are boxed integers:
<= div>
>=C2=A0type key =3D Key of i= nt=C2=A0

Values are elements of an algebrai= c type with references to keys:

> type value =3D
>= =C2=A0 =C2=A0| Str of string
>= =C2=A0 =C2=A0| Link of key

Elements of the = association list are key/value pairs wrapped in an ephemeron:
> module Eph =3D Ephemeron.K1<= /font>
> type pair =3D (ke= y,value) Eph.t
> le= t mk_pair key value =3D
>=C2= =A0 =C2=A0let eph =3D Eph.create () in
>=C2=A0 =C2=A0Eph.set_key eph key;
>=C2=A0 =C2=A0Eph.set_data eph value;
>=C2=A0 =C2=A0eph
=C2=A0=C2=A0=
The following adds a new key/value pair to the assoc list:
=

> let intern idx value= map =3D
>=C2=A0 =C2=A0let key= =3D Key idx in
>=C2=A0 =C2=A0= let eph =3D mk_pair key value in
= >=C2=A0 =C2=A0let map =3D eph::map in
>=C2=A0 =C2=A0(key,map)

Next a f= unction to update a key/value pair:

> let rec upd key new_value map =3D
>=C2=A0 =C2=A0match map with
>=C2=A0 =C2=A0 =C2=A0| [] -> raise Not_found
>=C2=A0 =C2=A0 =C2=A0| pair::rest ->= ;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0= begin
>=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0match Eph.get_key pair with
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| Some ot= her_key when eq_key key other_key ->
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0let eph =3D mk_p= air key new_value in
>=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0eph::rest
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| _ -> pa= ir::(upd key new_value rest)
>= =C2=A0 =C2=A0 =C2=A0 =C2=A0end

N= ext, create a list of pairs:

> let str n =3D Str (String.make n '#');;=C2=A0 =C2=A0(* Ens= ure value is boxed *)

=
> let (root,map) =3D
>=C2=A0 =C2=A0let map =3D [] in
<= div>>=C2=A0 =C2=A0let (k0,map) =3D intern 0 (st= r 1) map in
>=C2=A0 =C2=A0let = (k1,map) =3D intern 1 (Link k0) map in
>=C2=A0 =C2=A0let (k2,map) =3D intern 2 (Link k1) map in
>=C2=A0 =C2=A0(k2,map);;

Printing this yields:

> root=3D(Key 2), map=3D(Eph ((Key 2),(Link (K= ey 1))))
>=C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(Eph ((Key 1),(Link (Key 0= ))))
>=C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(Eph ((Key 0),(Str #)))=

Next, update the root of the tree:

> let map =3D upd root (s= tr 2) map;;

Which correctly binds (Key 2) t= o a string of length 2:

&= gt; root=3D(Key 2) map1=3D(Eph ((Key 2),(Str ##)))
<= div>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0(Eph ((Key 1),(Link (Key 0))))
= >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0(Eph ((Key 0),(Str #)))

=
Invoking gc from within the repl and printing again yields:

> Gc.full_major ();;
> root=3D(Key 2) map1=3D(Eph ((Key 2),(Str ##)))
<= div>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0(Eph (None,None))
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0(Eph (None,None))

which is = exactly what one would expect. If however, I use the standalone bytecode co= mpiler or the native compiler (4.07.1), then the entries are not nullified.= Is this a bug or is there another way to persuade the garbage collector to= clobber the entries?

Thanks

<= div>Lindsay



--0000000000000cf021057d693b8f--