caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* [Caml-list] Possible ephemeron bug?
@ 2018-12-20  0:29 Lindsay Errington
  2018-12-20  9:46 ` Stephen Dolan
  0 siblings, 1 reply; 3+ messages in thread
From: Lindsay Errington @ 2018-12-20  0:29 UTC (permalink / raw)
  To: caml-list

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

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

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

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [Caml-list] Possible ephemeron bug?
  2018-12-20  0:29 [Caml-list] Possible ephemeron bug? Lindsay Errington
@ 2018-12-20  9:46 ` Stephen Dolan
  2018-12-20 17:40   ` Lindsay Errington
  0 siblings, 1 reply; 3+ messages in thread
From: Stephen Dolan @ 2018-12-20  9:46 UTC (permalink / raw)
  To: Lindsay Errington; +Cc: Ocaml Mailing List

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

On Thu, 20 Dec 2018 at 00:30, Lindsay Errington <lindsay.errington@gmail.com>
wrote:

> 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 for the detailed example!

The issue is with the test code at the end:

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

    Fmt.printf "root=%a, map=@[<v>%a@]@." pp_key root pp_map map;;

    let map = upd root (str 2) map;;

    Fmt.printf "root=%a map1=@[<v>%a@]@." pp_key root pp_map map;;

Both the bytecode and native code compilers take any value bound to a
global to be reachable forever, even if that global is later shadowed by
another global of the same name. The ephemerons don't get cleared, because
the original map is still alive.

You can change the code to avoid putting the original map in a global
constant:

    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
      Fmt.printf "root=%a, map=@[<v>%a@]@." pp_key k2 pp_map map;
      let map = upd k2 (str 2) map in
      (k2, map);;

    Fmt.printf "root=%a map1=@[<v>%a@]@." pp_key root pp_map map;;

With this version, the original map becomes unreachable, so the GC can
clear the ephemerons.

Stephen

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

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

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [Caml-list] Possible ephemeron bug?
  2018-12-20  9:46 ` Stephen Dolan
@ 2018-12-20 17:40   ` Lindsay Errington
  0 siblings, 0 replies; 3+ messages in thread
From: Lindsay Errington @ 2018-12-20 17:40 UTC (permalink / raw)
  To: Stephen Dolan; +Cc: Ocaml Mailing List

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

Great answer! Thanks to you both.

I have a followup ephemeron question which I'll post with a different
subject.

On Thu, Dec 20, 2018 at 1:46 AM Stephen Dolan <stephen.dolan@cl.cam.ac.uk>
wrote:

> On Thu, 20 Dec 2018 at 00:30, Lindsay Errington <
> lindsay.errington@gmail.com> wrote:
>
>> 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 for the detailed example!
>
> The issue is with the test code at the end:
>
>     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);;
>
>     Fmt.printf "root=%a, map=@[<v>%a@]@." pp_key root pp_map map;;
>
>     let map = upd root (str 2) map;;
>
>     Fmt.printf "root=%a map1=@[<v>%a@]@." pp_key root pp_map map;;
>
> Both the bytecode and native code compilers take any value bound to a
> global to be reachable forever, even if that global is later shadowed by
> another global of the same name. The ephemerons don't get cleared, because
> the original map is still alive.
>
> You can change the code to avoid putting the original map in a global
> constant:
>
>     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
>       Fmt.printf "root=%a, map=@[<v>%a@]@." pp_key k2 pp_map map;
>       let map = upd k2 (str 2) map in
>       (k2, map);;
>
>     Fmt.printf "root=%a map1=@[<v>%a@]@." pp_key root pp_map map;;
>
> With this version, the original map becomes unreachable, so the GC can
> clear the ephemerons.
>
> Stephen
>

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

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

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2018-12-20 17:41 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-12-20  0:29 [Caml-list] Possible ephemeron bug? Lindsay Errington
2018-12-20  9:46 ` Stephen Dolan
2018-12-20 17:40   ` Lindsay Errington

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).