Weak reference is still alive if key is alive, but weak reference itself not reachable

We've been running into some unexpected behavior with weak references. The use case it hackage package HMap, which is a (heterogenous, but that is besides the point) map from keys to values. Since there is no way to enumerate all elements in the map, there is no way to obtain a value for a key if the key is dead.

As an optimization, I therefore used weak references to the values in the map, such that if the key dies, then the value is also dead. I was under the impression that a weak reference is alive if: (1): The key is still alive AND (2): The weak reference itself is alive (i.e. reachable from root set)

However, the actual behavior is that a weak reference is alive if (1), (2) does not matter. Hence, the weak references here actually create a space leak, because an alive key will keep all values in all maps that it was ever used in alive.

I think it would be desirable, to change the behavior to (1) AND (2), instead of just (1). This would prevent space leaks in this use case instead of creating them. Or would this cause problems in other use cases?

See also: https://github.com/atzeus/HMap/issues/5#issuecomment-132538324

Trac metadata

Trac field	Value
Version	7.10.2
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Runtime System
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed weight to 5

added RTS Tbug Trac import labels

closed

This is working as intended, see http://research.microsoft.com/apps/pubs/default.aspx?id=67497

The paper includes an implementation of a memo table, which should help with the situation in HMap.

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedWon'tFix

Thanks! The paper indeed discusses and gives a nice solution to this. Subtle stuff :)

added runtime perf label

added Pnormal label