[Caml-list] Expected behavior of Weak hash tables

[Caml-list] Expected behavior of Weak hash tables

[Josh Berdine]

Hi,

I am using the standard library's Weak hash tables for what I expect is
a pretty standard hash-consing implementation.  I wonder if I should
expect the implementation of Weak.Make to guarantee that elements of the
weak set disappear _only_after_ they become dead.  That is, can live
values that are members of a weak set be removed from the set by the
garbage collector?  I have tracked down some unexpected behavior
(e.g. non-maximal sharing) in my code to what looks like this premature
disappearance from a weak set.  I have only observed live values
disappear from the weak set after a major collection, and I think only
when the heap has been grown.  This behavior is very fragile and
seems to be extremely sensitive to very slight changes to the program,
and I can't say for certain at this point that my code is doing exactly
what it should.

So my question is: Am I expecting the implementation of Weak.Make to
satisfy a stronger property than it is intended to, or should I continue
hunting the bug in my code?  And also, does anyone have suggestions for
good approaches to debugging this sort of very allocation-sensitive
behavior?

In case they are relevant, some additional details:

- The values which are unexpectedly not members of the weak set are not
  the shallow copies of elements that are passed to the H.equal
  relation.

- The elements of the weak set have no finalizers, from either the C or
  OCaml APIs.

- The elements of the weak set may have cyclic substructures, but there
  are no cycles through a weak set element.  However, I observe the
  strange behavior even for very simple entirely acyclic immutable
  values.

- The type of elements of the weak set is hidden behind a private type
  to all of the code but ~10 lines, so there is little opportunity to
  make the usual sort of mistake of constructing shallow copies of weak
  set elements that are not themselves in the set.  Also, the only
  values of this type ever constructed are returned by Weak.Make.merge,
  and the clear, add, and remove operations are not used.

- This is with OCaml 4.00.1, using either the 32-bit MSVC Windows port
  or 64-bit Linux, although it seems to happen more often on the former.
  I tried with trunk, but the fix for PR#6005 seems to require
  significant changes to my code.  (But, no, I'm not exploiting PR#6005
  to define magic.)

Cheers, Josh

Re: [Caml-list] Expected behavior of Weak hash tables

[Jacques-Henri Jourdan]

Hi,

You are expecting the right property from Weak.Make (that is, their is 
probably some flaws in your code).

One way to introduce more determinism in these kind of behavior (to ease 
debugging), is to trigger manually a full GC cycle, so that values that 
have to be collected from weak tables will be.

A common mistake when using Weak.Make for memoization/hashconsing is to 
put pairs in a weak hash table in order to use it as a weak map. This 
can be wrong, because what is important in that case is the liveness of 
the pair itself, which is very likely to be pointed only by the weak 
hash table.

Regards,
-- 
Jacques-Henri Jourdan

Le 10/07/2013 01:05, Josh Berdine a écrit :
> Hi,
>
> I am using the standard library's Weak hash tables for what I expect is
> a pretty standard hash-consing implementation.  I wonder if I should
> expect the implementation of Weak.Make to guarantee that elements of the
> weak set disappear _only_after_ they become dead.  That is, can live
> values that are members of a weak set be removed from the set by the
> garbage collector?  I have tracked down some unexpected behavior
> (e.g. non-maximal sharing) in my code to what looks like this premature
> disappearance from a weak set.  I have only observed live values
> disappear from the weak set after a major collection, and I think only
> when the heap has been grown.  This behavior is very fragile and
> seems to be extremely sensitive to very slight changes to the program,
> and I can't say for certain at this point that my code is doing exactly
> what it should.
>
> So my question is: Am I expecting the implementation of Weak.Make to
> satisfy a stronger property than it is intended to, or should I continue
> hunting the bug in my code?  And also, does anyone have suggestions for
> good approaches to debugging this sort of very allocation-sensitive
> behavior?
>
> In case they are relevant, some additional details:
>
> - The values which are unexpectedly not members of the weak set are not
>    the shallow copies of elements that are passed to the H.equal
>    relation.
>
> - The elements of the weak set have no finalizers, from either the C or
>    OCaml APIs.
>
> - The elements of the weak set may have cyclic substructures, but there
>    are no cycles through a weak set element.  However, I observe the
>    strange behavior even for very simple entirely acyclic immutable
>    values.
>
> - The type of elements of the weak set is hidden behind a private type
>    to all of the code but ~10 lines, so there is little opportunity to
>    make the usual sort of mistake of constructing shallow copies of weak
>    set elements that are not themselves in the set.  Also, the only
>    values of this type ever constructed are returned by Weak.Make.merge,
>    and the clear, add, and remove operations are not used.
>
> - This is with OCaml 4.00.1, using either the 32-bit MSVC Windows port
>    or 64-bit Linux, although it seems to happen more often on the former.
>    I tried with trunk, but the fix for PR#6005 seems to require
>    significant changes to my code.  (But, no, I'm not exploiting PR#6005
>    to define magic.)
>
> Cheers, Josh
>