563653 - Weak dictionary hangs onto values

Status: RESOLVED WONTFIX

(Tamarin Graveyard :: Virtual Machine, defect)

Description

[Shannon Hickey]

User-Agent:       Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_5_8; en-us) AppleWebKit/531.22.7 (KHTML, like Gecko) Version/4.0.5 Safari/531.22.7
Build Identifier: 

When a Dictionary with weak keys lets go of a key, it continues to hold on to the value. It holds on to it even through GC passes in the profiler. Oddly, it seems that if I keep adding new items, it goes through a cycle where it releases values after every 7th iteration (Flash version MAC 10,0,45,2) or every iteration (Flash version MAC 10,1,53,21).

Reproducible: Always

Steps to Reproduce:
Create the source files shown below. Launch Scratch.mxml in the profiler and press the "Add One" button repeatedly.

-------------------
TheHolder.as
-------------------

package scratch
{
	import flash.utils.Dictionary;

	public class TheHolder
	{
		private static var dict:Dictionary = new Dictionary(true);

		public function addOne():void
		{
			var theKey:TheKey = new TheKey();
			var theValue:TheValue = new TheValue();
			dict[theKey] = theValue;
		}
	}
}

-------------------
TheKey.as
-------------------

package scratch
{
	public class TheKey {}
}

-------------------
TheValue.as
-------------------

package scratch
{
	public class TheValue	{}
}

-------------------
Scratch.mxml
-------------------

<?xml version="1.0" encoding="utf-8"?>
<mx:Application xmlns:mx="http://www.adobe.com/2006/mxml" layout="absolute" minWidth="955" minHeight="600">
	<mx:Script>
		<![CDATA[
			import scratch.TheHolder;
			private var theHolder:TheHolder = new TheHolder();
			public function doOne():void
			{
				theHolder.addOne();
			}
		]]>
	</mx:Script>
	<mx:Button x="175" y="141" label="Add One" click="doOne()"/>
</mx:Application>

Actual Results:  
Instances of TheValue stick around in the profiler according to the cycle I mentioned in the description.

Expected Results:  
Instances of TheValue are cleaned up immediately.

Mike Morearty wrote to me:

"Interesting -- and now that I think of it, it sort of makes sense to me that this would happen, given the implementation.  (I'm not saying it's okay -- I'm just saying, I think I see why this is happening.)  In avmplusHashtable.cpp, it appears that the only time it walks through the hashtable and removes values that were attached to now-deleted keys is when the hashtable needs to grow. 

I wonder if there should be a hook into the garbage collector so that when a GC happens, weak-key hashtables prune out values for keys that have been deleted."

Comment 1

[Tommy Reilly]

My thoughts:

- provide a Dictionary.prune method to do a rehash manually
- provide a true weak reference class than can be used to wrap the value

Comment 2

[Shannon Hickey]

I think the issue here is that a Dictionary with weak keys isn't doing what developers expect of it. Providing any solution that requires a manual prune call, to me, doesn't seem to solve the problem. As for the second suggestion, support for weak valued Dictionaries seems valuable, and may partially help with the problem. However, again, I don't think it solves the problem - which is that developers expect that when a key is cleaned up, the value goes with it.

Comment 3

[Tommy Reilly]

From the docs:

weakKeys:Boolean (default = false) — Instructs the Dictionary object to use "weak" references on object keys. If the only reference to an object is in the specified Dictionary object, the key is eligible for garbage collection and is removed from the table when the object is collected.

I can see how this implies we drop the entry from the table when the key is collected.   Implementing these semantics in a performant way would be a little tricky and might break existing apps that depended on the old semantics, the fix could be versioned though.  I can't confirm we'll fix it but I'm warming up to the idea that this is a legitimate bug ;-)

Comment 4

[Felix S. Klock II [:pnkfelix, :fklock]]

Note that there are (at least) three distinct cases to consider here when one is proposing solutions/work-arounds for the problem.  (Below I just went ahead and enumerated the four obvious combinations.)

Notational shorthands below: kN are keys, vN are values; uppercase letter mean globally unreachable (other than through chains of weak-references, or via hidden references in the table's representation), lowercase letter means reachable from a chain of (non-weak) references from a root.

Lets say we have a weak table holding the (abstract) mappings:
 { k1 => v1, k2 => V2, K3 => v3, K4 => V4}.
Thus V2, K3, K4, and V4 are globally unreachable, apart from the table itself (or external chains with at least 1 weak reference).

Obviously k1 and v1 will stay in the table, as they're both alive.

Also obviously K3 can be reclaimed (and its associated object v3 will not be, as long as it remains globally reachable).  I'll ignore the issue of whether the table holds onto a representation of the entry, since that seems like a minor space-efficiency issue.  The interesting question is how the 2nd and 4th mappings will be handled.

My understanding is that this bug is describing a current problem with K4/V4: when K4 is reclaimed, the table is artificially holding on to V4.  (Tommy has pointed out to me that it may be possible for a client to observe this retention, by using V4 as a weak key in a separate table.  Thus we may need api versioning before we can do anything about this.)

But whatever solution/workaround we propose should not break the other cases.  In particular, telling a client to wrap values in a weak box before putting them into the table will break the 2nd case, since the mapping k2 => V2 should keep V2 *alive*, but if you put V2 into a weak-box before adding this abstract mapping to the table, that makes V2 eligible for collection despite k2 being generally reachable.

(My pithy summary is: that there is a reason that the Java Collections API includes a WeakHashmap, rather than trying to layer everything on top of weak reference objects.)

Comment 5

[Lars T Hansen]

(In reply to comment #4)
> My understanding is that this bug is describing a current problem with K4/V4:
> when K4 is reclaimed, the table is artificially holding on to V4.

Yes, and I think that's probably a legitimate bug, not an enhancement request.  I'm reverting Dan's downgrade but leaving the targeting to 'Future'.

> (Tommy has
> pointed out to me that it may be possible for a client to observe this
> retention, by using V4 as a weak key in a separate table.  Thus we may need api
> versioning before we can do anything about this.)

You may be right, although I hate applying versioning to GC semantics, over time it boxes us in in the worst way.  (That's true for versioning in general, but while we can rev the world by shipping two separate components for eg regex engines, it's harder to do that for GC).  We should think carefully about what observability means here and whether it's likely that anyone is making use of it.  After all, they can observe that V4 disappeared from the heap, but only indirectly - notably through the change in the size of the dictionary that used V4 as a key.

Comment 6

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #5)
> After all, they can observe that V4 disappeared from the heap, but only
> indirectly - notably through the change in the size of the dictionary that used
> V4 as a key.

Oh, is one not able to enumerate the keys of one of these dictionaries?  I had assumed the interface was analogous to that for object properties, at least in terms of expressiveness.

Comment 7

[Lars T Hansen]

(In reply to comment #6)
> (In reply to comment #5)
> > After all, they can observe that V4 disappeared from the heap, but only
> > indirectly - notably through the change in the size of the dictionary that used
> > V4 as a key.
> 
> Oh, is one not able to enumerate the keys of one of these dictionaries?  I had
> assumed the interface was analogous to that for object properties, at least in
> terms of expressiveness.

You can do that, but you can't know directly which key or value was removed because you can't keep those keys or values around for comparison purposes.  (You could keep a copy around, of course, or a digest, and for some sorts of values that isn't a stretch.)

Comment 8

[Felix S. Klock II [:pnkfelix, :fklock]]

Oh, and for the record I agree with you that I suspect no client is making such observations.

(Then again, my instinct would be to push the fix for bug 559401; I suspect I have not properly digested the degree of backwards compatibility that we must adhere to.)

Comment 9

[Sylvestre Ledru [:Sylvestre]]

Tamarin isn't maintained anymore. WONTFIX remaining bugs.