StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POCompacting a WeakReference Dictionary
text
Body
copied!<p>I've got a class <em>Foo</em> with a property <em>Id</em>. My goal is that there are no two instances of <em>Foo</em> with the same <em>Id</em> at the same time.</p> <p>So I created a factory method <em>CreateFoo</em> which uses a cache in order to return the same instance for the same <em>Id</em>.</p> <pre><code>static Foo CreateFoo(int id) { Foo foo; if (!cache.TryGetValue(id, out foo)) { foo = new Foo(id); foo.Initialize(...); cache.Put(id, foo); } return foo; } </code></pre> <p>The cache is implemented as a Dictionary<TKey,WeakReference>, based on <em>@JaredPar</em>'s <a href="http://blogs.msdn.com/jaredpar/archive/2009/03/03/building-a-weakreference-hashtable.aspx" rel="nofollow noreferrer">Building a WeakReference Hashtable</a>:</p> <pre><code>class WeakDictionary<TKey, TValue> where TValue : class { private readonly Dictionary<TKey, WeakReference> items; public WeakDictionary() { this.items = new Dictionary<TKey, WeakReference>(); } public void Put(TKey key, TValue value) { this.items[key] = new WeakReference(value); } public bool TryGetValue(TKey key, out TValue value) { WeakReference weakRef; if (!this.items.TryGetValue(key, out weakRef)) { value = null; return false; } else { value = (TValue)weakRef.Target; return (value != null); } } } </code></pre> <p>The problem is that the WeakReferences remain in the dictionary after their targets have been garbage collected. This implies the need for some strategy how to manually "garbage collect" dead WeakReferences, as explained by <em>@Pascal Cuoq</em> in <a href="https://stackoverflow.com/questions/1813740">What happens to a WeakReference after GC of WeakReference.Target</a>.</p> <hr> <p>My question is: <strong>What's the best strategy to compact a WeakReference Dictionary?</strong></p> <p>The options that I see are:</p> <ol> <li><p>Don't remove WeakReferences from the Dictionary. IMO this is bad, because the cache is used in the full lifetime of my application, and <em>a lot</em> of dead WeakReferences will accumulate over time.</p></li> <li><p>Walk the entire dictionary on each <em>Put</em> and <em>TryGetValue</em>, and remove dead WeakReferences. This defeats somewhat the purpose of a dictionary because both operations become <em>O(n)</em>.</p></li> <li><p>Walk the entire dictionary periodically in a background thread. What would be a good interval, given that I don't know the usage pattern of <em>CreateFoo</em>?</p></li> <li><p>Append each inserted KeyValuePair to a double-ended linked list. Each call to <em>Put</em> and <em>TryGetValue</em> examines the head of the list. If the WeakReference is alive, move the pair to the end of the list. If it is dead, remove the pair from the list and the WeakReference from the Dictionary.</p></li> <li><p>Implement a custom hash table with the minor difference that, when a bucket is full, dead WeakReferences are first removed from the bucket before proceeding as usual.</p></li> </ol> <p>Are there other strategies?</p> <p>The best strategy is probably an algorithm with amortized time complexity. Does such a strategy exist?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload