Weak Referencing – Building a weakly referenced cache.

 

Hi All,

Today let’s consider the following case: There are some external data objects inserted into your system by some external process. For each object the user may request to see additional data that takes some time to fetch or generate. To save this time you would like to build a cache for the generated data but there is one major issue. You don’t control the insertion rate of these external objects. An object may be valid (referenced) for several seconds or for several hours. Furthermore, the insertion rate may vary for each object. I will try to give a concrete example (which might not reflect real life accurately but will explain the scenario). Suppose you have a list of system alerts which you show the user in some table. The user may double click an alert to see some more details on it. To fetch this extra data you need to make a web service call to a slow server that generates this data. The problem is that the alerts may not be valid anymore because they are removed in the alert manager that manages the collection of the alerts. I would like to discuss only the cache part of this problem.

The most straightforward way to implement such cache would be to use a dictionary which maps an alert to the cached data. When the alert is removed from the alert manager collection (let’s hope it has an event for that you can subscribe to) you can remove this alert from your dictionary. This solution is in most cases too strongly coupled with the implementation of the alert manager. The alert manager will assume that once it removes an alert from its internal collection it will be freed by the garbage collection mechanism but if someone accidently keeps this alert in own dictionary or collection then it might remain there forever causing a memory leak.

The most common solution to this problem is using a weak dictionary. In C# this structure can be implemented using the WeakReference class provided by the framework. The WeakReference class allows you to create a reference that would not prevent from the garbage collection to collect this object. In the next section I provide a skeleton implementation of such a dictionary.

The WeakDictionary

To build a weak dictionary let's recap shortly how dictionary (hash table) data structure works. The dictionary contains pairs of objects, a key and a value. The value can be anything and is not important for the inner workings of the data structure. What’s important is the key (pun intended). The key class must implement two methods: GetHashCode() which generates a non-unique code that identifies the specific instance and Equals(other) which compares the current instance to another instance and returns true if they are equal. The dictionary keeps a list of “buckets”, in each bucket is a Set of key objects with the same GetHashCode result. When a key is inserted the dictionary looks at the hash code of that key and tries to insert it into a bucket with this hash code. In a bucket it iterates over all the keys already in the bucket to see if it is already contained in this bucket if no suck key is found it inserts a new key value pair in that bucket otherwise it updates the value of the existing key. The retrieval of an item works just the same.

We want our keys to be the user defined objects so that the internal implementation will not be visible for the user so we will build an internal object that we will use as a key. This object will hold a weak reference to the original key provided by the user and therefore will not prevent its collection by the garbage collector. Here is a possible implementation of such a class:

8. public class WeakDictionary<TKey, TValue> where TKey : class
9. {
10.   private class WeakPair
11.   {
12.     private WeakReference _keyReference;
13.  
14.     private TValue _value;
15.     public TValue Value
16.     {
17.       get { return _value; }
18.       set { _value = value; }
19.     }
20.  
21.     public TKey Key
22.     {
23.       get
24.       {
25.         TKey result = _keyReference.Target as TKey;
26.         return result;
27.       }
28.     }
29.  
30.     private int _innerHashCode;
31.  
32.     public WeakPair(TKey key, TValue value)
33.     {
34.       _keyReference = new WeakReference(key);
35.       _value = value;
36.       _innerHashCode = key.GetHashCode();
37.     }
38.  
39.     public override int GetHashCode()
40.     {
41.       return _innerHashCode;
42.     }
43.  
44.     public override bool Equals(object obj)
45.     {
46.       WeakPair other = obj as WeakPair;
47.       if (other == null)
48.         return false;
49.  
50.       object key1 = _keyReference.Target;
51.       object key2 = other._keyReference.Target;
52.  
53.       if (key1 == null && key2 == null)
54.         return true;
55.       if (key1 == null)
56.         return false;
57.       if (key2 == null)
58.         return false;
59.  
60.       return key1.Equals(key2);
61.     }
62.   }

The most interesting method here is the Equals method where we delegate to the Equals method of the original class but checking if it was released by the garbage collection beforehand.

Now for the dictionary implementation itself. Since this is only a skeleton implementation I omitted anything not relevant to understanding the implementation (such as null checks). Our weak dictionary will hold an internal regular dictionary but we will manage the buckets ourselves.

64. private Dictionary<int, List<WeakPair>> _data = new Dictionary<int, List<WeakPair>>();

Each entry in this dictionary maps a hash code (int) to the data itself held by our weak pair class. I have implemented the three most important methods of the weak dictionary: Set, TryGet and CleanUp (which removes dead links from the dictionary). Here is my implementation:

66. public void Set(TKey key, TValue value)
67. {
68.   WeakPair pair = new WeakPair(key, value);
69.   int hashCode = key.GetHashCode();
70.   if (!_data.ContainsKey(hashCode))
71.     _data.Add(hashCode, new List<WeakPair>());
72.   List<WeakPair> dataList = _data[hashCode];
73.   for (int i = 0; i < dataList.Count; i++)
74.   {
75.     if (dataList[i].Equals(pair))
76.     {
77.       dataList[i] = pair;
78.       return;
79.     }
80.   }
81.  
82.   dataList.Add(pair);
83. }
84.  
85. public bool TryGet(TKey key, ref TValue value)
86. {
87.   int hashCode = key.GetHashCode();
88.   if (!_data.ContainsKey(hashCode))
89.   {
90.     return false;
91.   }
92.  
93.   WeakPair pair = new WeakPair(key, default(TValue));
94.   List<WeakPair> dataList = _data[hashCode];
95.   for (int i = 0; i < dataList.Count; i++)
96.   {
97.     if (dataList[i].Equals(pair))
98.     {
99.       value = dataList[i].Value;
100.       return true;
101.     }
102.   }
103.  
104.   return false;
105. }
106.  
107. public void CleanUp()
108. {
109.   foreach (int key in _data.Keys)
110.   {
111.     List<WeakPair> pairs = _data[key];
112.     for (int i = 0; i < pairs.Count; )
113.     {
114.       if (pairs[i].Key == null)
115.         pairs.RemoveAt(i);
116.       else
117.         i++;
118.     }
119.   }
120. }

The implementation is pretty straightforward. The interesting method is CleanUp which you need to call from time to time to remove the dead references from the dictionary. This implementation achieves the goal we set. If we use this dictionary as the cache for our alert objects they will not be considered as referenced by the cache for the garbage collection thus removing the need to register on the events of the alerts manager.

The key disadvantages of this implementation are:

1. You still need to do the maintenance of the dictionary yourself. It is not entirely clear when to call the CleanUp method as this call may be costly in some cases.
2. We use WeakReferences but how much overhead does it cause in reality? In terms of space the overhead is not severe (except maybe for the dead references that remain) but what about the time consumption? I ran a simple test to check how much time it takes to allocate a WeakReference as opposed to a regular object and here is the result:
                  As you can see, the mere allocation of a weak reference takes a lot more time than allocating a simple object. I won’t go into details on this one but if you check out the implementation using ILSpy you will see that inside it creates a GCHandle and uses some unmanaged code. Also note that each WeakReference object you add to the heap is registered within the CLR internal structures which are examined during the garbage collection run making it a bit more slower.
3. The cached data itself is linked with the WeakReference object and not with the original object and therefore it will be garbage collected only after you run CleanUp.

So what can you do? Well the solution is simpler than it seems because .Net framework 4 provides a class for you that will do all I have mentioned above but without the disadvantages. This class is the ConditionalWeakTable. This data structure will weakly hold references to both the keys and the values.

Here is a little test program that compares the two structures:

8. public class Alert
9. {
10.   static int Count = 0;
11.   private int _data;
12.   public Alert()
13.   {
14.     _data = Count++;
15.   }
16.  
17.   ~Alert()
18.   {
19.     Console.Out.WriteLine(String.Format("* Finalizing Alert {0}", _data));
20.   }
21. }
22.  
23. public class CacheData
24. {
25.   static int Count = 0;
26.   private int _data;
27.   public CacheData()
28.   {
29.     _data = Count++;
30.   }
31.  
32.   ~CacheData()
33.   {
34.     Console.Out.WriteLine(String.Format("*** Finalizing CacheData {0}", _data));
35.   }
36. }

Here I defined two data objects that correspond to my example. Every time an object is created it is given a unique ID which is printed out on the finalizer of that object.

19. Console.Out.WriteLine("WeakDictionary without cleanup");
20. List<Alert> alerts = new List<Alert>();
21. WeakDictionary<Alert, CacheData> dictionary = new WeakDictionary<Alert, CacheData>();
22. for (int i = 1; i <= 10; i++)
23. {
24.   Alert alert = new Alert();
25.   if (i % 2 == 0)
26.     alerts.Add(alert);
27.   dictionary.Set(alert, new CacheData());
28. }
29.  
30. GC.Collect();
31. GC.WaitForPendingFinalizers();
32. Console.Out.WriteLine("------------------");
33. Console.Out.WriteLine("WeakDictionary after cleanup");
34.  
35. dictionary.CleanUp();
36.  
37. GC.Collect();
38. GC.WaitForPendingFinalizers();
39. Console.Out.WriteLine("------------------");
40. Console.Out.WriteLine("Clearing the main list of alerts");
41.  
42. alerts.Clear();
43.  
44. GC.Collect();
45. GC.WaitForPendingFinalizers();
46. Console.Out.WriteLine("------------------");
47. Console.Out.WriteLine("ConditionalWeakTable without cleanup");
48.  
49. ConditionalWeakTable<Alert, CacheData> table = new ConditionalWeakTable<Alert, CacheData>();
50. for (int i = 1; i <= 10; i++)
51. {
52.   Alert alert = new Alert();
53.   if (i % 2 == 0)
54.     alerts.Add(alert);
55.   table.Add(alert, new CacheData());
56. }
57.  
58. GC.Collect();
59. GC.WaitForPendingFinalizers();
60. Console.Out.WriteLine("------------------");

and the output is:

WeakDictionary without cleanup
* Finalizing Alert 8
* Finalizing Alert 0
* Finalizing Alert 6
* Finalizing Alert 4
* Finalizing Alert 2
------------------
WeakDictionary after cleanup
*** Finalizing CacheData 2
*** Finalizing CacheData 4
*** Finalizing CacheData 6
*** Finalizing CacheData 0
*** Finalizing CacheData 8
------------------
Clearing the main list of alerts
* Finalizing Alert 7
* Finalizing Alert 3
* Finalizing Alert 1
* Finalizing Alert 5
------------------
ConditionalWeakTable without cleanup
* Finalizing Alert 9
*** Finalizing CacheData 18
* Finalizing Alert 18
*** Finalizing CacheData 16
* Finalizing Alert 16
*** Finalizing CacheData 14
* Finalizing Alert 14
*** Finalizing CacheData 12
* Finalizing Alert 12
*** Finalizing CacheData 10
* Finalizing Alert 10
------------------

As you can see when running garbage collection in the first example the even numbered alerts are freed because they are only in the weak dictionary and not in the list. The cache data is collected only after CleanUp is called. On the other hand in the ConditionalWeakTable both the alerts and the data of even ids are cleared immediately after the collection just as we wanted.

Thank you for reading,

Boris