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

Serializing Primitive Types to Byte Array–Analysis

 

Hi All,

Today I am going to consider the following case: You want to transmit a class over some sort of a protocol and of course you want to minimize the serialization size and maximize the serialization speed of your class. Since every class is essentially a set of primitive types we can simply consider the cost of serializing these primitive types to simple byte arrays (buffers) which can be sent over some medium.

My wife did an extensive research on this case at work and eventually came down with two possible methods (I am summarizing her work as there were many possible solutions to this case)

Method 1 – Using List<byte>

14. public static byte[] GetBytes()
15. {                                       
16.   List<byte> result = new List<byte>(400000);
17.   for (int i = 0; i < 100000; i++)
18.     result.AddRange(BitConverter.GetBytes(i));
19.  
20.   return result.ToArray();
21. }

Method 2 – Using MemoryStream

26. public static byte[] GetBytes()
27. {
28.   using (MemoryStream ms = new MemoryStream(400000))
29.   {
30.     using (BinaryWriter writer = new BinaryWriter(ms))
31.     {
32.     for (int i = 0; i < 100000; i++)
33.       writer.Write(i);
34.     }
35.     return ms.GetBuffer();
36.   }
37.  
38. }

At first glance these two methods should not differ by much. Perhaps Method 1 should be a bit slower but here are the results of this run:

45. Stopwatch sw = new Stopwatch();
46. sw.Start();
47. byte[] result = ArrayFormatter.GetBytes();
48. sw.Stop();
49. Console.WriteLine(string.Format("ArrayFormatter time = {0} value = {1} length = {2}",sw.ElapsedMilliseconds,result[12],result.Length));
50.            
51. sw.Reset();
52.  
53. sw.Start();
54. result = MemoryStreamFormatter.GetBytes();
55. sw.Stop();
56. Console.WriteLine(string.Format("MemoryStreamFormatter time = {0} value = {1} length = {2}",sw.ElapsedMilliseconds,result[12],result.Length));

ArrayFormatter time = 3439 value = 3 length = 400000
MemoryStreamFormatter time = 343 value = 3 length = 400000

Method 1 is ten times slower than Method 2. When my wife told me about this result I said she probably measured something wrong. I simply couldn’t believe it so I ran the analysis myself and got the following results:

First, we look at the results of Method 2. We can see that the MemoryStream was initialized with a single allocation of 400000 bytes just as we would expect. But there is something nice happening here. The result of the method GetBytes is taken directly from the memory stream buffer by using the GetBuffer method (the memory stream is disposed when we leave the method) so no additional allocations are required.

Now we look at Method 2. Oh the horror… The constructor of the List allocates 400000 bytes just as we expected. We did it so that AddRange would not need to allocate additional bytes and therefore relocate the entire collection in memory. Next we see that BitConverter.GetBytes allocated 100,000 arrays of 4 bytes each, the result of converting a single int  into byte array but since an Array is a class we paid a great penalty here. For every class allocated in 32bit architecture we pay 8 bytes of system managed space (two pointers, one for the syncblock and one for the MT of that class) and probably each instance of Array contains a single int variable that contains its size (I am not sure about this if you know otherwise please leave a comment). All and all each such intermediate array takes 16 bytes and therefore there are 1600000 bytes allocated by this method. The big surprise comes with the AddRange method. You would expect that no allocations would be done in this method since we pre-allocated all the needed space in the List constructor but it seems that for each call to AddRange a temporary array is allocated (the number of byte allocated is the same as in the BitConverter.GetBytes calls). Lets look at the code using ILSpy -

108. public void InsertRange(int index, IEnumerable<T> collection)
109. {
110.   if (collection == null)
111.   {
112.     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
113.   }
114.   if (index > this._size)
115.   {
116.     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
117.   }
118.   ICollection<T> collection2 = collection as ICollection<T>;
119.   if (collection2 != null)
120.   {
121.     int count = collection2.Count;
122.     if (count > 0)
123.     {
124.       this.EnsureCapacity(this._size + count);
125.       if (index < this._size)
126.       {
127.         Array.Copy(this._items, index, this._items, index + count, this._size - index);
128.       }
129.       if (this == collection2)
130.       {
131.         Array.Copy(this._items, 0, this._items, index, index);
132.         Array.Copy(this._items, index + count, this._items, index * 2, this._size - index);
133.       }
134.       else
135.       {
136.         T[] array = new T[count];
137.         collection2.CopyTo(array, 0);
138.         array.CopyTo(this._items, index);
139.       }
140.       this._size += count;
141.     }
142.   }
143.   else
144.   {
145.     using (IEnumerator<T> enumerator = collection.GetEnumerator())
146.     {
147.       while (enumerator.MoveNext())
148.       {
149.         this.Insert(index++, enumerator.Current);
150.       }
151.     }
152.   }
153.   this._version++;
154. }

Look at lines 136 – 138! Our assumption was correct. There is an allocation of a temporary array in the middle of AddRange but why? I found a cryptic answer in StackOverflow. In simple words the answer is this: Since the input collection is cast to ICollection<T> we have to use it's CopyTo method to copy the elements because it may have a custom implementation. The CopyTo method expects we send it the full array and not only the area to which it should copy the elements. If we would send the internal array of the List<T> (this._items) we would expose it to an external method of unknown implementation, this is very dangerous because it can change other elements in this array. As a rule of thumb it’s a good practice to not send reference type (mutable) private members to methods of unknown implementation. The solution here is to create a temporary array with the exactly needed size and make the input collection copy all the members there and then use the standard implementation of CopyTo to copy the elements to the internal array.

All things combined we get ten times more bytes allocated in Method 1 over Method 2 which accounts for the difference in performance. Mystery solved.

Thanks for reading,
Boris.

Writing an Extensible Application – Part 4: MEF

 

Hi All,

This is the 4th and final part of the extensibility series and this time I will talk about MEF (Managed Extensibility Framework). MEF was an open source project on codeplex but in .Net framework 4 (and SL 4) it was included within the framework itself. MEF is a very simple way to allow extensibility in your application.

A short reminder: We have an application consisting of two projects, the main application and the interfaces Dll which we ship to our clients. The client references the interfaces Dll and implements the required interfaces. This time the extensibility project is called Extensibility and it uses MEF to extend our application. To use MEF in .Net 4 project you simply have to reference System.ComponentModel.Composition (from the framework). Now things couldn’t be simpler. All you need to do is to mark your implemented classes with the Export attribute which will allow the MEF mechanism to identify these implementations as your extensibility implementations. You can pass a type to this attribute stating under which type the implemented class will be imported.

So the code didn’t change too much except these things:

10. [InheritedExport(typeof(ICollider))]
11. public class BasicCollider : ICollider

13. [InheritedExport(typeof(IDrawer))]
14. public class BasicDrawer : IDrawer

10. [InheritedExport(typeof(IMover))]
11. public class BasicMover : IMover

and in the main application the loading is much simpler now:

95. private void LoadExtensibility()
96. {
97.   Assembly applicationAssembly =  Assembly.GetAssembly(GetType());
98.   string extensibilityPath = System.IO.Path.Combine(System.IO.Path.GetDirectoryName(applicationAssembly.Location), ConfigurationManager.AppSettings["Extensibility"]);
99.  
100.   AggregateCatalog catalog = new AggregateCatalog();
101.   catalog.Catalogs.Add(new DirectoryCatalog(extensibilityPath));
102.   _container = new CompositionContainer(catalog);
103.  
104.   try
105.   {
106.     this._container.ComposeParts(this);
107.   }
108.   catch (CompositionException compositionException)
109.   {
110.     Console.WriteLine(compositionException.ToString());
111.   }
112.  
113.   IEnumerable<Lazy<ICollider>> tempColliders = _container.GetExports<ICollider>();
114.   foreach (Lazy<ICollider> collider in tempColliders)
115.     Colliders.Add(new StrategyAdapter(collider.Value));
116.  
117.   IEnumerable<Lazy<IMover>> tempMovers = _container.GetExports<IMover>();
118.   foreach (Lazy<IMover> mover in tempMovers)
119.     Movers.Add(new StrategyAdapter(mover.Value));
120.  
121.   IEnumerable<Lazy<IDrawer>> tempDrawers = _container.GetExports<IDrawer>();
122.   foreach (Lazy<IDrawer> drawer in tempDrawers)
123.     Drawers.Add(new StrategyAdapter(drawer.Value));
124.  
125. }

I won’t go into details about the use of MEF but basically I linked the extensibility folder “Extensibility” with the composition container which magically read the dlls from that folder and added the exported classes so that I can later read them using the GetExports method.

Summary

I have presented 3 ways of making your application extensible. The first involved reflection only and wasn’t a real extensibility framework but merely a poor man’s solution (which sometimes may be enough). The second solution involved an open source framework (IC#Core) which is a bit obsolete and gives only the infrastructure into which you need to add content. The third solution is the MEF framework which gives you some nice options (such as hot swapping) but if you use it without the source code there is too much “automagical” stuff going on there (at least for me). I think the main take-away here is the design of the application. If you followed the example throughout the four parts you have noticed that due to the design of the application the changes I had to make to move from one extensibility framework to the other were quite minor.

 

Thank you for reading,

Boris

String Interning or why you shouldn’t use string in a lock statement.

 

Hi All,

Today I want to talk about a nice and relatively unmentioned feature of the .Net framework – string interning. I will start with a small riddle. What do you think is the output of the following application?

10. class Program
11. {
12.   static void Main(string[] args)
13.   {
14.     Task t0 = new Task(() => { PrintNumber(0); });
15.     Task t1 = new Task(() => { PrintNumber(1); });
16.     t0.Start();
17.     t1.Start();
18.     Task.WaitAll(t0, t1);
19.   }
20.  
21.   public static void PrintNumber(int number)
22.   {
23.     lock ("Monkey")
24.     {
25.       for (int i = 0; i < 10; i++)
26.       {
27.         Console.Out.Write(number);
28.         Thread.Sleep(200);
29.       }
30.     }
31.   }
32. }

If you said a series of 0s and then a series of 1s (or vise versa) then you are right. But why? When we lock the string “Monkey” shouldn’t the compiler create two instances of the this string (one per call)? This string is a local variable of the method.

As you probably know the String class in .Net is immutable which means that once an instance of this class is created it cannot be edited in any way. Any operation that changes the content of the string will always create a new instance of the string, this instance reflects the changes done on the original string. This behavior is not cemented using some sort of a language directive and is more of a “word of mouth”, an agreements if you wish, between the framework and the coders. Nevertheless, this immutability allows the .Net framework to treat the string in a special way. If the compiler can infer the string content at compile time it will not be allocated on the local heap. It will be allocated on the System Appdomain and added to an interning hash table on the System Domain (called the intern pool). Every time a string is created the framework will search the intern pool to check if an instance of this string already exists and if so it will return a reference to that instance. Note that this would happen automatically only to strings which the compiler can infer during compilation but you can force a string to enter the intern pool by using the String.Intern method.

Here is a simple program to list some interesting cases of string interning:

10. static void Main(string[] args)
11.     {
12.       string s1 = "Hello World";
13.       string s2 = "Hello World";
14.       string s3 = s2;
15.       StringBuilder sb1 = new StringBuilder(s1);
16.       string s4 = sb1.ToString();
17.       string s5 = string.Intern(s4);
18.       string s6 = s1.Clone() as string;
19.       
20.  
21.       Console.Out.WriteLine(String.Format("s1 == s2 - {0}", s1 == s2));
22.       Console.Out.WriteLine(String.Format("Object.ReferenceEquals(s1,s2) - {0}", Object.ReferenceEquals(s1, s2)));
23.       Console.Out.WriteLine(String.Format("Object.ReferenceEquals(s1,s3) - {0}", Object.ReferenceEquals(s1, s3)));
24.       Console.Out.WriteLine(String.Format("Object.ReferenceEquals(s1,s4) - {0}", Object.ReferenceEquals(s1, s4)));
25.       Console.Out.WriteLine(String.Format("Object.ReferenceEquals(s1,s5) - {0}", Object.ReferenceEquals(s1, s5)));
26.       Console.Out.WriteLine(String.Format("Object.ReferenceEquals(s1,s6) - {0}", Object.ReferenceEquals(s1, s6)));
27.  
28.       StringBuilder sb2 = new StringBuilder();
29.       for (int i = 0; i < 20000; i++)
30.         sb1.Append("a");
31.  
32.       string[] strings = new string[2];
33.       for (int i = 0; i < 2; i++)
34.       {
35.         strings[i] = String.Intern(sb1.ToString());
36.       }
37.  
38.       
39.       Console.Out.WriteLine(String.Format("(s1,s6) - {0}", Object.ReferenceEquals(strings[0],strings[1])));
40.  
41.     }

And the output is:

s1 == s2 - True
Object.ReferenceEquals(s1,s2) - True
Object.ReferenceEquals(s1,s3) - True
Object.ReferenceEquals(s1,s4) - False
Object.ReferenceEquals(s1,s5) - True
Object.ReferenceEquals(s1,s6) - True
(s1,s6) – True

Couple of thigs to notice:

1. String operations that do not change the string (such as Clone or ToString) will return the same instance.
2. If an interend string is allocated on the System Appdomain it will never be released (Only when the CLR is terminated)
3. StringBuilder will always generate a new instance of a string (the compiler can’t infer what the StringBuilder contains).

I am not sure where interning can actually help (although I heard that there are some use cases in ASP.NET where this behavior is benefitial) but you should be aware that it exist and never use a string in a lock statement. Who knows where this string comes from

This is what MSDN has to say about the lock statement :

lock("myLock") is a problem because any other code in the process using the same string, will share the same lock.

I hope now you understand why.

 

I want to thank Ilya Kosaev for helping me with this blog post.

Thanks for reading,

Boris.

Memory leaks when implementing GetHashCode()

 

Hi All,

If you have been following my blog then you know I am trying to list as many possible memory leaks in managed code as possible. Most developers, when told about the garbage collection mechanism in .Net, think that memory leaks cannot happen (at least in pure managed code) but as we seen this is not true. The most common case for such memory leaks are static (or singleton events) but as I shown before, using lambda expressions incorrectly may also cause objects not to be disposed in a timely manner.

We consider a case where a simple object overrides the GetHashCode method to be used in a dictionary later. In our case the object (named Person) will be used as a key for a much larger data chunk (named LargeDataObject). Being a seasoned .Net developer I know that if I override the GetHashCode method I also have to override the Equals method and so I do:

8. public class Person
9. {
10.   public int Age { get; set; }
11.  
12.   public override int GetHashCode()
13.   {
14.     return Age.GetHashCode();
15.   }
16.  
17.   public override bool Equals(object obj)
18.   {
19.     if (!(obj is Person))
20.       return false;
21.  
22.     return (obj as Person).Age == this.Age;
23.   }
24. }

In my implementation lies the key to the memory leak (pun intended). We examine the following use of the person class:

12. Dictionary<Person, LargeDataObject> table = new Dictionary<Person, LargeDataObject>();
13. Person p1 = new Person() { Age = 10 };
14. table.Add(p1, new LargeDataObject());
15.  
16. Console.Out.WriteLine("Contains P1(10) = {0}", table.ContainsKey(p1));

So far so good, this application would print : Contains P1(10) = True

But now I add the following code:

17. p1.Age = 20;
18. Console.Out.WriteLine("Contains P1(20) = {0}", table.ContainsKey(p1));

I changed the age of the person thus changing the hash code of person instance. The GetHashCode and the Equal methods are still in sync but now p1 sits in the wrong bucket within the dictionary! For this case the application would print out : Contains P1(20) = False

In fact you can get to the original p1 instance only by iterating over the keys of this dictionary (but lets face it, you didn’t use dictionary in the first place to iterate over all the keys). What you probably have is something like this in your code:

20. Person p2 = new Person(){Age=10};
21.       LargeDataObject dataObject = new LargeDataObject();
22.       if (table.ContainsKey(p2))
23.         table[p2] = dataObject;
24.       else
25.         table.Add(p2, dataObject);

If we run this code after the previous code then another person (and most importantly LargeDataObject) will be added to the dictionary. This would happen if I try to add a new Person with Age = 20 because of what MSDN tells us (quite correctly) to do:

“If two objects compare as equal, the GetHashCode method for each object must return the same value. However, if two objects do not compare as equal, the GetHashCode methods for the two object do not have to return different values.”

What happens when you look for a Person with Age = 10: The dictionary goes to the bucket where the hash code is 10 and looks there. It finds p1 and checks if it equals to the current person. The age of p1 is 20 so the current person is not equal p1. Nothing found.

What happens when you look for a Person with Age = 20: The dictionary goes to the bucket where the hash code is 20 and looks there. It finds no items. Nothing found.

Conclusion: If you are implementing GetHashCode and Eqauls make sure they do not depend on mutable properties of an object or this object (if used in a hash based collection) may never be disposed or reached through your code.

Thanks for reading,

Boris.

Writing an Extensible Application – Part 3: IC#Code Addin Tree

 

Hi All,

This is the third part of my extensibility series and this time I would like to describe an open source extensibility mechanism which is part of SharpDevelop called the Addin Tree. To use the Addin Tree all you have to do is to download the latest version of SharpDevelop and reference the file ICSharpCode.Core.dll in your project. For my example I will be using the dll from version 4.1 which can be downloaded from the site.

The Addin Tree (AT for short) is a very simple mechanism based on XML files called Addins. Each Addin file may contain one or more Path elements which maps all child elements of the Path element to a specific node within the AT. The AT is a tree data structure where each node may contain one or more Codons that describe any user data. Each node in the tree can be reached using a path statement of the form “A/B/…/C/D” where A,B,C are the ids of the nodes to pass on the way to node D which is represented by this statement. When the application loads it can read any number of Addins and build the tree. Later, you may access any node of the tree and Build the codons within this node. Each codon is built by a Doozer which is mapped to that specific codon (the core mechanism provides some basic doozers to build elementary program elements).

The addins are defined using XML files that contain the following elements:

• Root Addin Element which contains some general data on the addin.
• The Manifest Element which describes the addin file.
• The Runtime Element which defines the Doozers and the assemblies needed in the addin.
• The Paths Elements which contain the codons of the addin.

Here is an example of such an Addin file (from SharpDevelop):

19.         <AddIn name= "AddInScout"
20.              author= "Satguru P Srivastava"
21.           copyright= "prj:///doc/copyright.txt"
22.                 url= "http://home.mchsi.com/~ssatguru"
23.        description = "Display AddIn Information"
24.        addInManagerHidden = "preinstalled">
25.  
26.   <Manifest>
27.     <Identity name = "ICSharpCode.AddInScout"/>
28.   </Manifest>
29.  
30.   <Runtime>
31.     <Import assembly="AddInScout.dll"/>
32.   </Runtime>
33.  
34.   <Path name = "/Workspace/Tools">
35.     <MenuItem id = "ShowAddInScout"
36.                   label = "AddIn Scout"
37.                   class = "AddInScout.AddInScoutCommand"/>
38.   </Path>
39. </AddIn>

The Balls Game

Back to our example… To use the Addin tree extensibility I made some small changes. First, the build process now builds the entire game into a single root Bin folder and all the Addins into an Addins folder. This structure is needed for the Runtime mechanism of the AT. I created a main addin file for the application called Main.addin which contains the definition of the three Doozers I will use to support the extensibility of my application. The doozers are defined in the Interfaces project as internal classes and they contain some logic to build the required class from the codon definition. The main addin file looks like this:

1. <AddIn name="Balls Main Addin"
2.        author="Boris Kozorovitzky"
3.        description="The main addin of the game"
4.        addInManagerHidden="preinstalled">
5.  
6.   <Manifest>
7.     <Identity name="MainAddin"/>
8.   </Manifest>
9.  
10.   <Runtime>
11.     <Import assembly=":BallsInterfaces">
12.       <Doozer name="Collider" class="BallsInterfaces.Doozers.ColliderDoozer"/>
13.       <Doozer name="Mover" class="BallsInterfaces.Doozers.MoverDoozer"/>
14.       <Doozer name="Drawer" class="BallsInterfaces.Doozers.DrawerDoozer"/>
15.     </Import>
16.   </Runtime>
17. </AddIn>

One important thing to notice here is that the Import element tells the extensibility mechanism where to find the doozers. In this case I use the “:” syntax to tell it that the required assembly is in the Bin folder. You will understand why this is important next.

The extensibility Addin may sit anywhere in the Addin folder (any directory structure) and it looks like this:

1. <AddIn name="Balls Addin"
2.        author="Boris Kozorovitzky"
3.        description="Adds some balls to the game"
4.        addInManagerHidden="preinstalled">
5.  
6.   <Manifest>
7.     <Identity name="AddinExtensibility"/>
8.   </Manifest>
9.  
10.   <Runtime>
11.     <Import assembly=":BallsInterfaces"></Import>
12.     <Import assembly="AddinExtensibility.dll"></Import>
13.   </Runtime>
14.  
15.   <Path name="/Balls/Colliders">
16.     <Collider type="AddinExtensibility.BasicCollider"></Collider>
17.     <Collider type="AddinExtensibility.StopperCollider"></Collider>
18.   </Path>
19.  
20.   <Path name="/Balls/Movers">
21.     <Mover type="AddinExtensibility.BasicMover"></Mover>
22.     <Mover type="AddinExtensibility.ParabolicMover"></Mover>
23.  
24.   </Path>
25.  
26.   <Path name="/Balls/Drawers">
27.     <Drawer type="AddinExtensibility.BasicDrawer" fill="Yellow"></Drawer>
28.       <Drawer type="AddinExtensibility.BlinkerDrawer"></Drawer>
29.  
30.   </Path>
31.  
32. </AddIn>

Note that the import section references the Dll where all the classes are defined – AddinExtensibility.dll and the BallsInterfaces assembly. The main section of the addin contains three Path elements (I chose the path randomly to something logical) and each path contains Codon which can be built by a specific doozer (see doozer mapping in the main addin file). The collider doozer code will reveal the nice trick which the import does for us:

9. internal class ColliderDoozer:IDoozer
10. {
11.   public object BuildItem(BuildItemArgs args)
12.   {
13.     string stringType = args.Codon.Properties["type"];
14.     object result = args.AddIn.CreateObject(stringType);
15.     return result;
16.   }
17.  
18.   public bool HandleConditions
19.   {
20.     get { return false; }
21.   }
22. }

The AT mechanism will call the BuildItem method on any codon which is mapped to that doozer. In this case I expect the element to have a “type” attribute where the type of the object is written. Now that the type is resolved I can call the CreateObject method which will do the magic for us and find the correct type from the assemblies referenced in the Runtime section and thus returning the correct item each time. To show you how the extensibility mechanism can work for us I added two editable properties to the BasicDrawer type. The Drawer doozer calls a new method – Configure which takes the codon and extracts the needed arguments from it. Now we can control the color and the diameter of the basic drawer directly from the addin file!

11. public class BasicDrawer : IDrawer
12.   {
13.     private static double _initialDiameter;
14.     private static Brush _initialBrush;
15.  
16.     public void Initialize(IBall ball)
17.     {
18.       ball.Diameter = _initialDiameter;
19.       ball.Fill = _initialBrush??Brushes.Blue;
20.     }
21.  
22.     public void Tick(IBall ball)
23.     {
24.  
25.     }
26.  
27.     public object Clone()
28.     {
29.       return new BasicDrawer();
30.     }
31.  
32.  
33.     public void Configure(ICSharpCode.Core.Codon codon)
34.     {
35.       _initialDiameter = 15;
36.       if (codon.Properties.Contains("diameter"))
37.       {
38.         string diameterString = codon.Properties["diameter"];
39.         double diameter = 15d;
40.         Double.TryParse(diameterString, out diameter);
41.         _initialDiameter = diameter;
42.       }
43.  
44.       _initialBrush = null;
45.       if (codon.Properties.Contains("fill"))
46.       {
47.         string fillString = codon.Properties["fill"];
48.         _initialBrush = (SolidColorBrush)new BrushConverter().ConvertFromString(fillString);
49.       }
50.  
51.     }
52.   }

In the example I set the color of all the balls created with the BasicDrawer to Yellow but the user may chose to edit this value as he wishes.

The extensibility initialization code changed slightly and now it loads all the addin files from the Addins path:

93. private void LoadExtensibility()
94. {
95.   Assembly applicationAssembly =  Assembly.GetAssembly(GetType());
96.   string extensibilityPath = System.IO.Path.Combine(System.IO.Path.GetDirectoryName(applicationAssembly.Location), ConfigurationManager.AppSettings["AddinsPath"]);
97.   string[] addinFiles = System.IO.Directory.GetFiles(extensibilityPath, "*.addin",System.IO.SearchOption.AllDirectories);
98.   AddInTree.Load(new List<string>(addinFiles), new List<string>());
99.   foreach (ICollider collider in AddInTree.BuildItems<ICollider>("/Balls/Colliders", null))
100.     Colliders.Add(new StrategyAdapter(collider));
101.  
102.   foreach (IMover mover in AddInTree.BuildItems<IMover>("/Balls/Movers", null))
103.     Movers.Add(new StrategyAdapter(mover));
104.  
105.   foreach (IDrawer drawer in AddInTree.BuildItems<IDrawer>("/Balls/Drawers", null))
106.     Drawers.Add(new StrategyAdapter(drawer));
107. }

This extensibility mechanism allows great flexibility and it is simple enough to cover many useful scenarios. In the worst case you can always take a look at the source code to see how things work under the hood. If you are looking for something simple yet powerful to extend your application you should definitely consider the Addin Tree.

Thank you for reading. You can get the new sources from my SkyDrive here:

 

Boris

Task Parallel Library (TPL)–The lambda strikes back

 

Hi All,

I would like to share an interesting insight I got when solving some problems at Project Euler.  I was trying to make my program run a little faster (because it was using only one CPU core) so I decided to use the TPL. I will spare you the details of the actual problem and instead present a simple piece of code which demonstrates the problem:

12. public static void Run()
13.     {
14.       Task[] tasks = new Task[10];
15.       for (int i = 0; i < 10; i++)
16.       {
17.         tasks[i] = Task.Factory.StartNew(() => { PrintNumber(i); });
18.       }
19.  
20.       Task.WaitAll(tasks);
21.     }
22.  
23.     private static void PrintNumber(int i)
24.     {
25.       Thread.Sleep(100);
26.       Console.Write(i);
27.       Console.Write(",");
28.     }

What do you think will be printed when I call Run?

 

If you think that this is not deterministic because the TPL may choose to run the tasks at any order you would be half right. Indeed, the TPL can run the tasks in any order but in this case we have a different problem. The evaluation of the lambda expression will be done only when the task is run and in the general case it would be after the loop is finished so the value of “i" would be 10 for all the tasks.

The correct answer is therefore that the program will print 10 times “10,” (in the general case because in some cases the task may start in the middle of the loop).

I remind you from a previous post on my blog that when you use a local variable in a lambda expression the compiler generates a “secret” class for you which holds a reference (for reference types) or a copy (for value types) of this variable until the lambda expression is run. Therefore to get the desired result we need a unique variable to be copied in each iteration. This can be achieved by adding a temp variable within the scope of the loop and use it in the lambda.

12. public static void Run()
13. {
14.   Task[] tasks = new Task[10];
15.   for (int i = 0; i < 10; i++)
16.   {
17.     int x = i;
18.     tasks[i] = Task.Factory.StartNew(() => { PrintNumber(x); });
19.   }
20.  
21.   Task.WaitAll(tasks);
22. }
23.  
24. private static void PrintNumber(int i)
25. {
26.   Thread.Sleep(100);
27.   Console.Write(i);
28.   Console.Write(",");
29. }

Now we get the correct results, the numbers 0 though 9 are printed (in some order).

My conclusion is (again): One should be extra careful when using local variables in lambda expressions.

 

Thanks for reading,

Boris.