Simply Explained – Async

 

Hi All,

The blog is back after a somewhat long break. The break was due to two major changes in my life, the first is that I moved to a new apartment and had to deal with lots of new apartment stuff. The second is that I made a career change of 180 degrees (in terms of technological stack) and moved from Windows-.NET-WPF to Linux-Javascript-NodeJS. This means that you will probably see a change in content in future posts.

Anyway…

Modern applications are becoming more demanding in CPU resources. The CPU manufacturers used to deal with this demand by increasing the clock speed of the processor and by improving the internal architecture. In recent years (~10) this trend has changed to building multi-code processors and the dependence on multi threaded designs to speed up the application. In the world of .NET dealing with threads was usually done by experts as there are many pitfalls such as race conditions and mutual exclusion to be considered. In the last two versions of .NET framework this entire area was dramatically improved by introducing many new classes and the TPL framework and integration into the language in C# 5. You can read more about it in Pavel’s blog here and in this nice post that summarizes some of the key features of multi threaded libraries in .NET 4.

Parallel to the trend of multi-threaded design another trend evolved (or rather forced). The event loop design. It is not new by any means and in fact Windows is using this concept from the very first versions. The basic idea is that there is a queue of events and a process that de-queues the events one by one and handles them. The events may come from external sources like IO or internally from the process. In this post I will demonstrate how to implement a simple factorial method in the three paradigms:

Simple Code

In this paradigm we don’t do anything special and just write the code ignoring the implications of a long running method. The code would look something like that:

The simple way.

Code Snippet

62. private BigInteger Factorial(int n)
63. {
64.   BigInteger result = 1;
65.   for (int i = 2; i <= n; i++)
66.   {
67.     result = result * i;
68.   }
69.  
70.   return result;
71. }

 

This is how you would use it.

Code Snippet

38. myLabel.Content = Factorial(50000).ToString();

The main problem here is that when this code is run, everything else doesn’t. The UI will appear to be stuck since it is not being refreshed and no interactions are possible with the process.

What you would probably do in this case is jump straight to the multi-threaded paradigm.

Multi-Threaded

In this paradigm we want to call our calculation on a background thread and once it is done let it report the result on the UI thread (updating the label). The code would be something like this:

Running the calculation in the background.

Code Snippet

44. Thread thread = new Thread(new ParameterizedThreadStart(ThreadedFactorial));
45. thread.IsBackground = true;
46. thread.Start(50000);

 

The code that runs on the background thread.

Code Snippet

74. public void ThreadedFactorial(object n)
75. {
76.   BigInteger result = Factorial(Convert.ToInt32(n));
77.   this.Dispatcher.Invoke(new Action<string>(PrintResult), new object[] { result.ToString() });
78. }

 

The result is reported on the UI thread.

Code Snippet

80. public void PrintResult(string result)
81. {
82.   myLabel.Content = result;
83. }

This implementation solves the issues with the simple implementation and is quite simple. The problems begin when there are resources shared between threads. You have to use locks, semaphores, and other thread synchronization constructs to make things work right. When the code gets larger you find yourself thinking “but what if the context switch is between the “if” statement and the assignment” and end up adding a lock on the entire method. We all been there. (And I will not start with how hard it is to debug concurrency issues.)

One more thing to take into account is that some environments don’t have threads (not .NET). Your browser running JavaScript probably does it on a single thread (the JavaScript not the browser).

The next paragraph shows how to write the same functionality on a single threaded system.

Event-Loop

The dispatcher is a “magical” object. It allows you not only to sync calls from different threads but also to schedule calls on the same thread (the UI thread in our case). Note the second parameter of the method Dispatcher.BeginInvoke is DispatcherPriority which allows you to add your method execution to a specific priority within the event loop of the UI thread. If you are able to break the calculation (or any other task) to small enough pieces then you can schedule those pieces one after the other on the event loop. This will insure that other events such as repaints and IO inputs are still handled by the process since they are interlaced within your calculation. The code may look something like this:

 

Calling the factorial method. Note the last parameter is the callback that should be run once the method is finished. Passing the callback as the last parameter is a common practice in this paradigm.

Code Snippet

54. PartialFactorial(1, 1, 50000, new Action<string>(PrintResult));

 

The partial factorial method.

Code Snippet

80. public void PartialFactorial(BigInteger result, int current, int end, Action<string> callback)
81. {
82.   BigInteger tempResult = result;
83.   int i;
84.   for (i = current; i <= current + 100 && i <= end; i++)
85.   {
86.     tempResult = tempResult * i;
87.   }
88.  
89.   if (i <= end)
90.   {
91.     this.Dispatcher.BeginInvoke(new Action<BigInteger, int, int, Action<string>>(PartialFactorial), System.Windows.Threading.DispatcherPriority.Background, new object[] { tempResult, i, end, callback });
92.   }
93.   else
94.   { callback(tempResult.ToString()); }
95. }

There are a couple things to notice here. First, I perform only 100 calculations and then schedule the rest by invoking the same method with the new parameters. The scheduling is done with the Background priority which is after all the IO and rendering is already finished. If the calculation is complete I call the callback provided for me by the original caller. I could schedule the callback call as well.

The main advantage here is that you don’t need to deal with any threads as everything is done on a single thread. There are several disadvantages that I should mention:

1. The code is a bit awkward. One can get used to this but it will always seem a bit clogged compared to the clean code of the multi-threaded approach. This is mainly due to the specific example I give here. Many processes can be broken into very small work units without making the flow so hard to understand.
2. There is a loss of call stacks. Every time you schedule a method to the event-loop you are basically starting a new call stack. This is for better and for worse (no stack overflow as in recursion).
3. The framework has to support this approach. In the example above one of the most time consuming methods was actually converting the BigInt to string (if you talk binary you know why it takes so long). There was no simple way to break this method to smaller bits so the UI is stuck while in this method. Frameworks like NodeJS which are built on the principle of event loop will make sure that no method blocks for that long.

 

I ran a small performance test on all three methods. And the event loop approach was a little slower than the other two but not by a factor. For a factorial of 50000 it took the first two methods ~7.5 seconds to complete while the event loop method took ~8 seconds. I tried different number of iterations within the PartialFactorial methods. Values above 300 made the UI cough a little bit. With a value of 100 there were no visible penalties.

Thank you for reading,

Boris

LongString: When things become unequal (comparing two long strings) – Part 2

 

Hi All,

In Part 1 of the LongString post I have shown how we can tackle the problem of running out of memory when manipulating long string using a class similar to the LongString. In Part 2 I will discuss a problem which arises from my implementation of LongString class when implementing the IEquatable<LongString> interface. As you may recall, the LongString is an aggregation of regular strings which are less or equal than a given value. The direct result of this definition is that two equal long strings may have a completely different representation (even if the given value is the same). I will discuss editing operations in Part 3 of this series but you may consider the case where for the given value of 3 the long string (“AB”,”CD”) is equal to the long string (“ABC”,”D”) but they have a different internal representation.

Implementing Equality

The first thing I did was to check how the framework string implements the equality method. You can see the code below but essentially since the strings are represented as a continues memory block the code simply goes over all the bytes and bitwise compares them (with a small optimization which I will not discuss).

10. private unsafe static bool EqualsHelper(string strA, string strB)
11.     {
12.       int i = strA.Length;
13.       if (i != strB.Length)
14.       {
15.         return false;
16.       }
17.       char* ptr = &strA.m_firstChar;
18.       char* ptr2 = &strB.m_firstChar;
19.       while (i >= 12)
20.       {
21.         if (*(long*)ptr != *(long*)ptr2 || *(long*)(ptr + (IntPtr)8 / 2) != *(long*)(ptr2 + (IntPtr)8 / 2) || *(long*)(ptr + (IntPtr)16 / 2) != *(long*)(ptr2 + (IntPtr)16 / 2))
22.         {
23.         IL_7D:
24.           while (i > 0 && *(int*)ptr == *(int*)ptr2)
25.           {
26.             ptr += (IntPtr)4 / 2;
27.             ptr2 += (IntPtr)4 / 2;
28.             i -= 2;
29.           }
30.           return i <= 0;
31.         }
32.         ptr += (IntPtr)24 / 2;
33.         ptr2 += (IntPtr)24 / 2;
34.         i -= 12;
35.       }
36.       goto IL_7D;
37.     }

I wanted to implement something similar and therefore my first implementation was like this:

99. public bool EqualsVerySlow(LongString other)
100. {
101.   if (Length != other.Length) return false;
102.   for (int i = 0; i < Length; i++)
103.   {
104.     if (this[i] != other[i])
105.     { return false; }
106.   }
107.   return true;
108. }

But then I discovered that I didn’t implement the indexer yet so I simply use the method from Part 1 which returns the internal indices (within the array of strings and in a string) GetItemIndexForCharIndex which resulted in this simple code:

90. public char this[int index]
91. {
92.   get
93.   {
94.     Tuple<int, int> innerIndex = GetItemIndexForCharIndex(index);
95.     return _items[innerIndex.Item1][innerIndex.Item2];
96.   }
97. }

The main problem here is that the implementation of GetItemIndexForCharIndex calculates the indices by going over the entire array of strings. This is OK for the indexer but it is not very good when used in a loop therefore it is time to implement the enumerator. A simple enumerator which “remembers” the current position and moves forward should be enough for this case.

148. class LongStringEnumerator : IEnumerator<char>
149. {
150.   LongString _innerString;
151.   int _currentIndex;
152.   int _currentCharIndex;
153.  
154.   public LongStringEnumerator(LongString target)
155.   {
156.     _innerString = target;
157.     _currentIndex = 0;
158.     _currentCharIndex = 0;
159.   }
160.  
161.   public char Current
162.   {
163.     get
164.     { return _innerString._items[_currentIndex][_currentCharIndex]; }
165.   }
166.  
167.   public void Dispose(){}
168.  
169.   object System.Collections.IEnumerator.Current
170.   {
171.     get
172.     { return Current; }
173.   }
174.  
175.   public bool MoveNext()
176.   {
177.     _currentCharIndex++;
178.     if (_currentCharIndex >= _innerString._items[_currentIndex].Length)
179.     {
180.       _currentCharIndex = 0;
181.       _currentIndex++;
182.       if (_currentIndex >= _innerString._items.Count)
183.       {
184.         return false;
185.       }
186.     }
187.     return true;
188.   }
189.  
190.   public void Reset()
191.   {
192.     _currentCharIndex = 0;
193.     _currentIndex = 0;
194.   }
195. }

Now I can fix the Equal code to use the enumerator instead of the indexer.

129. public bool Equals(LongString other)
130. {
131.   if (Length != other.Length)
132.     return false;
133.  
134.   LongStringEnumerator enumerator = new LongStringEnumerator(this);
135.   LongStringEnumerator enumerator2 = new LongStringEnumerator(other);
136.  
137.   do
138.   {
139.     if (enumerator.Current != enumerator2.Current)
140.       return false;
141.     enumerator2.MoveNext();
142.   }
143.   while (enumerator.MoveNext());
144.  
145.   return true;
146. }

One question remains… How bad is this solution? I have run some performance tests and it turns out that this equals method is about 30 to 50 times slower than the equals method of a regular string. In absolute terms, this equals method takes up to 20ms when comparing two 1,000,000 char long strings with only one different character (in a random position). The original method is so fast that it cannot be measured in ms .

Conclusion

The main problem with the long string is going to be performance (in terms of time) compared to the regular string. We see that if an algorithm required mainly comparisons then the LongString is not a good choice. Still, remember that the LongString was designed for a very specific scenario in which it should perform better. In the next part I will implement some editing methods.

A small note about concurrency. Just out of curiosity I have implemented the slow method using the TPL:

110. public bool EqualsSlow(LongString other)
111. {
112.   if (Length != other.Length)
113.     return false;
114.  
115.   bool isEqual = true;
116.   Parallel.For(0, Length, (i, loopState) =>
117.   {
118.     if (this[i] != other[i])
119.     {
120.       isEqual = false;
121.       loopState.Break();
122.     }
123.  
124.   });
125.  
126.   return isEqual;
127. }

This was indeed faster in some cases over the very slow implementation but I cannot compete with the concurrency done in the CPU (which will be used to run the original Equals method of string). This implementation may give you some ideas on how to improve the Equals implementation of LongString (e.g. run a forward and a backward enumerators in separate tasks).

Thank you for reading,

Boris

LongString: A long string for the small heap – Part 1

 

Hi All,

Today I am going to write about strings. I think that the most famous feature of the .Net string is its immutability and this property of the string is a source of comfort in many cases but also a source of pain in others. In this post I will describe a scenario where the immutability of a string may cause a serious degradation of performance and suggest a LongString class (with a partial implementation) which may somehow help in this case. To understand the problem in the scenario I am about to describe we have to throw in another .Net player – The large object heap (LOH for short). If you are unsure of how the LOH works you can read this Microsoft article but I will give a brief description of the relevant parts. The LOH is an additional heap used by the CLR to store large objects (and sometimes other object). How large? Currently (.Net 4) the magic number is 85,000 bytes and above. Every object allocated by the CLR which takes more than this number of byes will not be allocated on the regular heap but on the LOH. The problem is that the LOH has two undesirable properties:

1. The objects on the LOH are always Generation 2 (i.e. you need a full GC run to remove them from memory).
2. The memory in the LOH is not compacted because the CLR doesn’t want to copy such large objects around the memory. This may cause fragmentation in the LOH and sometimes to an OutOfMemory exception (even when there is plenty of memory remaining).

Now for the problematic scenario. Consider the case where you have a string which can be edited by the user and an internal mechanism that stores that string. Lets assume that for every change done by the user you must update some other data and display that data to the user immediately. In the general case this will not be a big problem because the strings will be pretty small. For every change you will be able to “edit” the internal string (by replacing it with a new instance) and the old instance will be garbage collected, probably as Generation 0. The problem begins when your string exceeds the magic number or actually half of the magic number since string characters are in Unicode. Then every generation of a new string will create a new instance on the LOH and the old instances will not be removed until full GC is run. If you are not careful enough and the string undergoes several manipulations then each such cycle may cause several objects to be allocated on the LOH and create fragmentation.

At this point some of you would stop me and say “Then use a StringBuilder, it is editable”. This is true, the StringBuilder is indeed a sort of editable version of the string class but internally it represents the data as a character array so the same problem remains (although not as severely as with String since the array will be reallocated much less).

I am going to propose an initial implementation of a LongString class which will be only rarely allocated on the LOH. The idea is simple, the LongString will keep an array of strings, each string is of length equal or less than a given number. It looks something like this:

8. public class LongString
9. {
10.   private int _runSize;
11.   private List<string> _items;
12.   private int _length;
13.  
14.   public LongString(string data, int runSize)
15.   {
16.     _runSize = runSize;
17.     _items = SplitString(data, runSize);
18.     _length = GetTotalLength();
19.   }
20.  
21.   private int GetTotalLength()
22.   {
23.     int count = 0;
24.     foreach (string item in _items)
25.     {
26.       count += item.Length;
27.     }
28.  
29.     return count;
30.   }

Note that for brevity reasons I have omitted all the range/null checks from the code. Those checks are very important and mandatory in any code!

So, what are the pros and what are the cons of this implementation? The main advantage is that with a high enough runSize we can avoid the LOH altogether. The only part of the object that may grow too large is the items list but for run size of 100 we would be able to represent a string 100 times larger than we could with the regular string class without it being allocated on the LOH. I doubt that in any practical use you will have strings which are over 400Mb big (and you can always increase the runSize even more). The main disadvantage is that we don’t use the regular string class which means compatibility issue with any other existing code and some time and space penalties for all the extra calculations we do and data we store for the functionality of the regular string.

I will start by implementing the Substring method.

32. private LongString(List<string> items, int runSize)
33. {
34.   _runSize = runSize;
35.   _items = items;
36.   _length = GetTotalLength();
37. }
38.  
39.  
40. public string Substring(int startIndex, int length)
41. {
42.   Tuple<int, int> innerStratIndex = GetItemIndexForCharIndex(startIndex);
43.   Tuple<int, int> innerEndIndex = GetItemIndexForCharIndex(startIndex + length - 1);
44.  
45.  
46.   if (innerStratIndex.Item1 == innerEndIndex.Item1) //This is the case when the substring is contained within one item
47.   {
48.     return _items[innerStratIndex.Item1].Substring(innerStratIndex.Item2, innerEndIndex.Item2 - innerStratIndex.Item2 + 1);
49.   }
50.  
51.   StringBuilder result = new StringBuilder(); //Can be optimized by calculating the exact length
52.  
53.   result.Append(_items[innerStratIndex.Item1].Substring(innerStratIndex.Item2));
54.  
55.   for (int i = innerStratIndex.Item1 + 1; i < innerEndIndex.Item1; i++)
56.   {
57.     result.Append(_items[i]);
58.   }
59.  
60.   result.Append(_items[innerEndIndex.Item1].Substring(0, innerEndIndex.Item2 + 1));
61.   return result.ToString();
62. }
63.  
64. public LongString LongSubstring(int startIndex, int length)
65. {
66.   Tuple<int, int> innerStratIndex = GetItemIndexForCharIndex(startIndex);
67.   Tuple<int, int> innerEndIndex = GetItemIndexForCharIndex(startIndex + length - 1);
68.  
69.   List<string> result = new List<string>();
70.   if (innerStratIndex.Item1 == innerEndIndex.Item1) //This is the case when the substring is contained within one item
71.   {
72.     result.Add(_items[innerStratIndex.Item1].Substring(innerStratIndex.Item2, innerEndIndex.Item2 - innerStratIndex.Item2 + 1));
73.   }
74.   else
75.   {
76.     result.Add(_items[innerStratIndex.Item1].Substring(innerStratIndex.Item2));
77.  
78.     for (int i = innerStratIndex.Item1 + 1; i < innerEndIndex.Item1; i++)
79.     {
80.       result.Add(_items[i]);
81.     }
82.  
83.     result.Add(_items[innerEndIndex.Item1].Substring(0, innerEndIndex.Item2 + 1));
84.   }
85.   return new LongString(result, _runSize);
86. }
87.  
88.  
89. /// <summary>
90. /// Returns a tuple where the first value is the index of the string that contains startIndex within the _items array
91. /// and the second value is the offset within that item (string)
92. /// </summary>
93. /// <param name="index">The index of the character within the full string</param>
94. /// <returns></returns>
95. private Tuple<int, int> GetItemIndexForCharIndex(int index)
96. {
97.   int indexRemaining = index;
98.   int itemIndex = 0;
99.   while (indexRemaining >= 0)
100.   {
101.     if (_items[itemIndex].Length <= indexRemaining)
102.     {
103.       indexRemaining -= _items[itemIndex].Length;
104.       itemIndex++;
105.       continue;
106.     }
107.     return new Tuple<int, int>(itemIndex, indexRemaining);
108.   }
109.   return null;
110. }

The code is quite simple. I have added a special private constructor that allows me to create a LongString from a list of strings. This allows me to speed up the internal cloning process without going through a regular string again. The substring operation is straight forward, cut away the start and the beginning of the target string from the saved string parts and copy all the parts in the middle as they are.

In the next post I will show more implementations of various methods of the LongString class.

Thank you for reading, Boris.

My programming tidbits – Clear Code

 

Hi All,

I know I didn’t write a full post for quite a while. I was quite busy with work and other personal issues but I assure you that I am working on something interesting for the next full post. Meanwhile, I will start a series of short posts where I describe my programming tidbits. I will try to write something different than the regular “Write tests! Don’t write long methods! Don’t use the mouse!” that you can read anywhere online. My number 1 tip is this (and if you are going to skip all the other tips, please still consider this one):

Write code that is clear for all the team members.

I will start with an example. I was sent a piece of code for code review which is similar to this one:

11. public string Foo()
12. {
13.   string fileName = Path.GetTempFileName();
14.   Func<string> func = () => { return Path.Combine(Directory.GetCurrentDirectory(), fileName); };
15.  
16.   string fullFileName = func();
17.   while (!File.Exists(fullFileName))
18.   {
19.     fileName = Path.GetTempFileName();
20.     fullFileName = func();
21.   }
22.  
23.   return fullFileName;
24. }

This code generates an inexistent temporary file name in the current directory. I kindly asked to change the code to the following:

26. public string Foo2()
27. {
28.   string fullFileName;
29.   do
30.   {
31.     fullFileName = Path.Combine(Directory.GetCurrentDirectory(), Path.GetTempFileName());
32.   }
33.   while (!File.Exists(fullFileName));
34.  
35.   return fullFileName;
36. }

After a short argument it was agreed that my code is slightly better in terms of readability (lets leave the performance considerations aside for this example). The main reason that initially this was not the code is because the engineer who wrote the code doesn’t like the do-while loop. To tell the truth, I don’t like do-while loop either. There is something not natural about its flow but in this case it saves a lambda expression, generation and allocation of a new class, and some readability.

When writing code please remember that not all your team members know everything you know. Some might not know lambda expressions well while others might not be familiar with the syntax of LINQ, some don’t like using “var” everywhere while others don’t want to clear unused “using”s because then they miss fundamental system namespaces by default. I am not saying you should not use these advanced framework features. I am saying you should not abuse these features (as in the above example). Think of the poor programmer that has to understand the entire logic of your algorithm and then he sees this method. He may not be best friends with lambdas but now he has to understand what this method does and why the hell did you not use a simple do-while loop instead.

My conclusion: Use advanced language features when they bring benefit to the code and not in order to make your code look cool.

 

Thanks for reading,

Boris.

 

P.S.

If the person who sent this code to me is reading this. Please don’t take this personally, this is just a good example of my tip.

Implementing CacheDictionary–A Dictionary with a limited number of items that can be used as cache.

 

Hi All,

Today we consider the following scenario: There is a process that needs to generate many resources. The generation process takes a long time and each generated resource is taking a considerable amount of memory (you don’t want to store more than a few such resources in the memory at a time). After analysis it is evident that when the process runs it often generates the same resource over and over again such that while the total number of generated resources is quite large, all these resources are the same. The solution would be to generate each resource only once and store it in some dictionary. Each subsequent request to generate this resource would simply retrieve it from this dictionary. To solve the issue I have implemented a CacheDictionary which holds only a specified amount of items and has a versatile removal strategy (when trying to add an item over the allowed limit).

It is possible to solve this problem using WeakReferenced values using a regular dictionary. In this solution a regular dictionary holds the resources as WeakReferences and therefore the GC may collect them at any time. The main advantage here is that you allow the CLR to manage the memory itself but you lose the ability to tailor the memory allocation and freeing behavior to your exact needs. At some cases this solution is probably very good but for other cases we need the CacheDictionary.

The CacheDictionary

My implementation encapsulates (and not inherits from) a regular dictionary. I have implemented the IDictionary<TKey,TValue> interface delegating the methods to an internal instance of the dictionary. The constructor requires two arguments: The maximum number of items allowed in the CacheDictionary and the RemovalStrategy. The RemovalStrategy is a class which controls which key is removed from the CacheDictionary when the Add method is called but a full capacity is reached. This class implements the following interface:

8. public interface ICacheDictionaryRemovalStrategy<TKey>
9. {
10.   /// <summary>
11.   /// Initialize the strategy and pass the maximum number of allowed items
12.   /// </summary>
13.   /// <param name="maxSize">The maximum number of allowed items</param>
14.   void Initialize(int maxSize);
15.  
16.   /// <summary>
17.   /// Notify the strategy that a key was added to the base collection
18.   /// </summary>
19.   /// <param name="key">The key that was added</param>
20.   void KeyAdded(TKey key);
21.  
22.   /// <summary>
23.   /// Notify the strategy that a key was removed from the base collection
24.   /// </summary>
25.   /// <param name="key">The key that was removed</param>
26.   void KeyRemoved(TKey key);
27.  
28.   /// <summary>
29.   /// Notify the strategy that a key was accessed (retrieved by the user) in the base collection
30.   /// </summary>
31.   /// <param name="key">The key that was retrieved</param>
32.   void KeyAccessed(TKey key);
33.  
34.   /// <summary>
35.   /// Notify the strategy that the base collection was cleared
36.   /// </summary>
37.   void Clear();
38.  
39.   /// <summary>
40.   /// Get the most appropriate key to remove, this is called when the base collection runs out of space
41.   /// </summary>
42.   /// <returns>The key that the base collection will remove</returns>
43.   TKey GetKeyToRemove();
44. }

Most of the methods are used to notify the strategy about changes in the underlying dictionary with two exceptions. Initialize method is called in the constructor of the CacheDictionary to allow the strategy run its initialization. The GetKeyToRemove is called when the user tries to add an item to the CacheDictionary but the items count is equal to the maxSize passed in the constructor. The CacheDictionary expects to get an existing key or an exception will be thrown. A noteworthy method is KeyAccessed. In my implementation this method is called whenever the user retrieves some value by using a key (see next section for details).

Tracking Access

As mentioned above, I define access to the CacheDictionary as retrieving some value by its key. The KeyAccessed method is therefore called in the following locations:

• TryGetValue method if the underlying call to TryGetValue was successful.
• The indexer property.
• The Current property of the custom enumerator.

The third point is worth elaborating upon. I am implementing the IDictionary interface and therefore I must provide a way to enumerate over the Key-Value pairs inside the dictionary. If I would just delegate these calls to the regular enumerator then I would miss an access done by the enumerator itself. For this reason I have added a wrapper class (CacheDictionaryEnumerator) which wraps the calls to the underlying enumerator but calls KeyAccessed method when needed.

The full implementation is therefore:

46. public class CacheDictionary<TKey, TValue> : IDictionary<TKey, TValue>
47. {
48.   private Dictionary<TKey, TValue> _data;
49.   private int _maxSize;
50.   private ICacheDictionaryRemovalStrategy<TKey> _removalStrategy;
51.  
52.   public CacheDictionary(int maxSize, ICacheDictionaryRemovalStrategy<TKey> removalStrategy)
53.   {
54.     if (removalStrategy == null)
55.       throw new ArgumentNullException("removalStrategy");
56.     if (maxSize == 0)
57.       throw new ArgumentException("maxSize must be a positive integer value");
58.     _maxSize = maxSize;
59.     _removalStrategy = removalStrategy;
60.     _data = new Dictionary<TKey, TValue>();
61.  
62.     _removalStrategy.Initialize(maxSize);
63.   }
64.  
65.   #region IDictionaty Implementation
66.  
67.   public void Add(TKey key, TValue value)
68.   {
69.     if (_data.ContainsKey(key))
70.       _data.Add(key, value); //I want to throw the same exception as the internal dictionary for this case.
71.  
72.     if (_data.Count == _maxSize)
73.     {
74.       TKey keyToRemove = _removalStrategy.GetKeyToRemove();
75.       if (_data.ContainsKey(keyToRemove))
76.         _data.Remove(keyToRemove);
77.       else
78.         throw new Exception(String.Format("Could not find a valid key to remove from cache, key = {0}", key == null ? "null" : key.ToString()));
79.     }
80.     _data.Add(key, value);
81.     _removalStrategy.KeyAdded(key);
82.   }
83.  
84.   public bool ContainsKey(TKey key)
85.   {
86.     return _data.ContainsKey(key);
87.   }
88.  
89.   public ICollection<TKey> Keys
90.   {
91.     get {return _data.Keys;}
92.   }
93.  
94.   public bool Remove(TKey key)
95.   {
96.     bool result = _data.Remove(key);
97.     if (result)
98.       _removalStrategy.KeyRemoved(key);
99.     return result;
100.   }
101.  
102.   public bool TryGetValue(TKey key, out TValue value)
103.   {
104.     bool result = _data.TryGetValue(key, out value);
105.     if (result)
106.       _removalStrategy.KeyAccessed(key);
107.     return result;
108.   }
109.  
110.   public ICollection<TValue> Values
111.   {
112.     get { return _data.Values; }
113.   }
114.  
115.   public TValue this[TKey key]
116.   {
117.     get
118.     {
119.       TValue result = _data[key];
120.       _removalStrategy.KeyAccessed(key);
121.       return result;
122.     }
123.     set
124.     {
125.       _data[key] = value;
126.       _removalStrategy.KeyAccessed(key);
127.     }
128.   }
129.  
130.   public void Add(KeyValuePair<TKey, TValue> item)
131.   {
132.     Add(item.Key, item.Value);
133.   }
134.  
135.   public void Clear()
136.   {
137.     _data.Clear();
138.     _removalStrategy.Clear();
139.   }
140.  
141.   public bool Contains(KeyValuePair<TKey, TValue> item)
142.   {
143.     return _data.Contains(item);
144.   }
145.  
146.   public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
147.   {
148.     ((IDictionary<TKey, TValue>)_data).CopyTo(array, arrayIndex);
149.   }
150.  
151.   public int Count
152.   {
153.     get { return _data.Count; }
154.   }
155.  
156.   public bool IsReadOnly
157.   {
158.     get { return ((IDictionary<TKey, TValue>)_data).IsReadOnly; }
159.   }
160.  
161.   public bool Remove(KeyValuePair<TKey, TValue> item)
162.   {
163.     bool result = ((IDictionary<TKey, TValue>)_data).Remove(item);
164.     if (result)
165.       _removalStrategy.KeyRemoved(item.Key);
166.     return result;
167.   }
168.  
169.   public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
170.   {
171.     return new CacheDictionaryEnumerator(_data.GetEnumerator(), _removalStrategy);
172.   }
173.  
174.   System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
175.   {
176.     return new CacheDictionaryEnumerator(_data.GetEnumerator(), _removalStrategy);
177.   }
178.   #endregion
179.  
180.   public class CacheDictionaryEnumerator : IEnumerator<KeyValuePair<TKey, TValue>>
181.   {
182.     private IEnumerator<KeyValuePair<TKey, TValue>> _innerEnumerator;
183.     private ICacheDictionaryRemovalStrategy<TKey> _removalStrategy;
184.  
185.     internal CacheDictionaryEnumerator(IEnumerator<KeyValuePair<TKey, TValue>> innerEnumerator, ICacheDictionaryRemovalStrategy<TKey> removalStrategy)
186.     {
187.       if (innerEnumerator == null)
188.         throw new ArgumentNullException("innerEnumerator");
189.       if (removalStrategy == null)
190.         throw new ArgumentNullException("removalStrategy");
191.  
192.       _innerEnumerator = innerEnumerator;
193.       _removalStrategy = removalStrategy;
194.     }
195.  
196.     public KeyValuePair<TKey, TValue> Current
197.     {
198.       get
199.       {
200.         KeyValuePair<TKey, TValue> result = _innerEnumerator.Current;
201.         _removalStrategy.KeyAccessed(result.Key);
202.         return result;
203.       }
204.     }
205.  
206.     public void Dispose()
207.     {
208.       _innerEnumerator.Dispose();
209.       _innerEnumerator = null;
210.     }
211.  
212.     object System.Collections.IEnumerator.Current
213.     {
214.       get {return this.Current;}
215.     }
216.  
217.     public bool MoveNext()
218.     {
219.       return _innerEnumerator.MoveNext();
220.     }
221.  
222.     public void Reset()
223.     {
224.       _innerEnumerator.Reset();
225.     }
226.   }
227. }

Strategy Implementations

For the solution to be useable out of the box (or out of the downloaded zip file) I have added three implementation of the ICacheDictionaryRemovalStrategy<TKey> interface. The three implementations are:

1. EmptyRemovalStrategy<TKey> – Removes the first item in it’s internal collection. Does not track access in any way.
2. MruRemovalStrategy<TKey> – Removes the most recently used (most accessed) item in the CacheDictionary.
3. LruRemovalStrategy<TKey> – Removes the least recently used (least accessed) item in the CacheDictionary.

These three implementation should allow you a basic use of the CacheDictionary right after download.

As usual you can download all the needed data from my skydrive (link below). The 7zip contains a small demo program on how to use the provided class. If you find bugs/improvements to my implementations I would be more than happy if you share those in the comments.

Thank you for reading,

Boris.

WinDbg 101–A step by step guide to finding a simple memory leak in your .Net application

 

Hi,

If you always wanted to learn how to use WinDbg to debug your .Net application but never had the courage to try, this guide is for you. In this post I will give step by step instructions on finding a very simple memory leak in a deployed application using WinDbg and SOS.

Let’s consider the following case: You come to work in the morning and the QA is rushing towards you. “I left the application MemoryLeakTest running at night and when I came in the morning it crashed!” he says in a disturbed tone. What should we do?

Step 1 – Get a crash dump

When a .Net application crashes it (usually) doesn’t close entirely. Instead, a window pops up and allows you to debug the crash or report to Microsoft (if error reporting is enabled). Reporting the error to Microsoft when your application crashes will usually not contribute to the resolution of the problem. Before closing the window we will create a crash dump of the application. I assume that debugging the application on the QA machine because is impossible because it simulates a customer machine. Creating a crash dump is made very simple in windows Vista and above (for older OSes this is a bit trickier. I advice you to use ADPlus , read here how). To create a crash dump, open the Task Manager, right click the crashed process and select Create Dump File, wait… A dialog will pop-up with the path to the created dump file.

Important – You have to pay special attention to the bitness of the process. I am using a 64bit OS but the application I want to debug is 32bit (I can see this by the *32 marker near the process name). If I create a dump file using the standard Task Manager, it will be a 64bit crash dump which is completely un-usable. I need to use the 32bit task manager. It is located in C:\<Windows Dir>\SysWOW64\taskmgr.exe. When running it you will see no indication that this is the 32bit version so be careful.

Step 2 – Installing WinDbg on your machine

If you already have a 32bit WinDbg installed, please skip this step. WinDbg comes as a component in Microsoft Windows SDK for Windows 7 and .NET Framework 4 (this is the iso version which I find more convenient). From the site at the link above you can download GRMSDK_EN_DVD.iso (the 32bit version) but don’t install it fully. Mount the image using your favorite mounting tool (I use VirtualCloneDrive) then install only \Setup\WinSDKDebuggingTools\dbg_x86.msi.

Step 3 – Mount the crash dump

Start WinDbg x86 and select File->Open Crash Dump (Control + D) then select the dump file. At this point you can simply run analyze –v and get all the information of this step but I will guide you through what actually happens in this command. First, you need to load SOS (the WinDbg extension which allows us to debug .NET applications). To do so type the command .loadby sos clr (or .loadby sos mscorwks in .Net 3.5 and below). This command will try to load the sos extension of the same version as the clr version you are running. Note that this might fail if you don’t have the exact same version of SOS and clr (the clr that was used to run the application on the remote machine). In that case you would need to copy the SOS dll from the machine that ran the application from the correct framework folder. If the command succeeds then you will see nothing. Now we want to see what was the exception that caused the application to crash. To do so use the !pe command (all SOS commands begin with “!”). Here is what I got when I ran it on my application:

0:000> !pe
Exception object: 7c93a534
Exception type: System.OutOfMemoryException
Message: <none>
InnerException: <none>
StackTrace (generated):
    SP       IP       Function
    0025E784 04E6C56A mscorlib_ni!System.Collections.Generic.List`1[[System.Byte, mscorlib]]..ctor(Int32)+0x1a
    0025E790 006104D9 MemoryLeakTest!MemoryLeakTest.DataHolder..ctor()+0x31
    0025E7A4 0061039C MemoryLeakTest!MemoryLeakTest.MainWindow.Button_Click(System.Object, System.Windows.RoutedEventArgs)+0x64
    0025E7DC 538571C8 PresentationCore_ni!System.Windows.RoutedEventHandlerInfo.InvokeHandler(System.Object, System.Windows.RoutedEventArgs)+0x78
<the rest is omitted for brevity>

We can see two important things here:

1. The exception is indeed and OutOfMemoryException so the problem could be a memory leak.
2. The OutOfMemoryException happened when the constructor of the DataHolder type in my application tried to allocate a list of bytes (List<byte>).

We should try to narrow things down to see what might cause the memory to get full.

Step 4 – Memory analysis

The first thing we want to do is to see what is consuming so much memory. SOS provides a command called dumpheap that allows us to do just that but if we run it without any flags we will get too much information. I run the following command: !dumpheap –stat . The –stat flag will cause the command to print out only the statistics for each object type. It will show the object MT, the number of such objects in memory and the total ammount of memory all objects of that type consume. The list will be ordered by the total memory consumed and in our case the last couple of lines look like this:

049e1cf0      544        10880 System.RuntimeType
54f731a4      192        11520 System.Windows.Markup.BamlAttributeInfoRecord
54f67bf4      496        13888 System.Windows.FrameworkPropertyMetadata
56ef2058      391        17204 System.Windows.DependencyProperty
049e32c0       58        35232 System.Collections.Hashtable+bucket[]
049e2d0c      214        59980 System.Int32[]
049e0b70     2719       143968 System.String
0029efc0       29      4066792      Free
049b4340      766      4284024 System.Object[]
00429b9c   811569     12985104 MemoryLeakTest.DataHolder
049c4034   811569     19477656 System.Collections.Generic.List`1[[System.Byte, mscorlib]]
049d9ddc   811634     25972288 System.EventHandler
049e35e0   811590   1227092812 System.Byte[]
Total 3259762 objects

Notice the last four lines. There is the DataHolder again and there are as many DataHolders as List<byte> so each DataHolder probably holds some list of bytes. This also accounts for the huge number of arrays of bytes since a List<byte> stores the data as an array of bytes internally. But something is out of place here. There are a lot of EventHandler objects, too many for any application to be alive at the same time and their number is very close to the number of DataHolder objects. This piece of information leads us to suspect that someone registers to a static/singleton event using a DataHolder but never unregisters. This causes the DataHolder objects to never be garbage collected.

Let’s investigate further!

Step 5 – Finding the Root cause

To confirm our suspicion and to see who is the singleton who holds the DataHolder objects in memory we will do the following: We need to find an instance of a DataHolder object and see who holds it (since there are so many, there is a high probability we will find the problem on the first try). To do so I will use the dumpheap command again but this time I will use it with the –mt flag to show the details of all objects of a certain type. I can see from the previous command that the MT of the DataHolder type is 00429b9c (see first column in the previous results). The command I run is therefore !dumpheap –mt 00429b9c (note that it is also possible to use the –type flag but in this casre it is important to be exact on the name of the type. The dumpheap commands uses "contains” condition when searching for type names so, for example if you write “!dumpheap –type String” it will show all the types with the word string contained in the name such as StringBuilder. Run !help dumpheap for more details). At this point WinDbg prints out a long list of all the instances of the DataHolder class. Since I am not looking for one particular class I stop the printing using Control+break and pick one instance to analyze. I pick the instance: 7c0a9fe4 00429b9c       16

Now I probe the specific object we found in the previous command. First lets get the details of that object by running the DumpObject command with the address of the object. I run !do 7c0a9fe4 :

0:000> !do 7c0a9fe4
Name: MemoryLeakTest.DataHolder
MethodTable: 00429b9c
EEClass: 00620d68
Size: 16(0x10) bytes
(C:\Projects\MemoryLeakTest\bin\Debug\MemoryLeakTest.exe)
Fields:
      MT    Field   Offset                 Type VT     Attr    Value Name
00000000  4000007        4                       0 instance 7c0a9ff4 Bytes
049e2dbc  4000008        8         System.Int32  1 instance       -1 <Id>k__BackingField
049e2dbc  4000006       24         System.Int32  1   static   811569 Counter

This is the correct object indeed. I can see its inner structure but to see which root is holding it I need to run !gcroot 7c0a9fe4. Wait until the command finishes. WinDbg shows the following output (note that in the general case there are many roots holding the same object):

Scan Thread 0 OSTHread 1618
ESP:25dd78:Root:02785bf8(MemoryLeakTest.App)->
0278c26c(MemoryLeakTest.MainWindow)->
7c93a4e0(System.EventHandler)->
03b5a7f8(System.Object[])->
7c0aa5f4(System.EventHandler)->
7c0a9fe4(MemoryLeakTest.DataHolder)

This is a linked list (hence the –> markers) of a path that leads from a system root to the DataHolder instance. Looks like our assumption was correct. There is indeed a registration of some event of the MainWindow class to a method of the DataHolder (it could be worse in case of a lambda expression).

Now it is the right time to find the problem in the code.

Step 6 – Finding the problem in the code

Only at this step I open the code of the application. I am looking for an event registration in the main window. A simple search for the += symbol leads me to the following line in the code:

34. DataHolder holder = new DataHolder();
35. ReportDeath += holder.ReportDeath;
36. holders.Add(holder);

There is a ReportDeath event in the MainWindow class and we register a method within the DataHolder class to that event. A simple search in the code shows that we never unregister from that event and therefore all the DataHolder instances are now “hanging” by the method ReportDeath on the MainWindow ReportDeath event.

Memory leak found!

Conclusion

I have shown how to use WinDbg to find a memory leak in the simplest possible scenario. In reality you would probably need to work harder to pinpoint what is causing the memory leak but your research will not be much different from the steps I took in this post. WinDbg is a powerful tool and a great compliment to Visual Studio. Knowing how to use it is a very important skill for both managed and unmanaged developers. I hope you enjoyed reading this post. Please leave a comment if you think I missed something or if you have something to add. The full source code of the MemoryLeakTest application can be found on my SkyDrive here:

Thank you for reading,

Boris

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