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

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