Saturday, December 31, 2011

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>

  1. public static byte[] GetBytes()
  2. {                                       
  3.   List<byte> result = new List<byte>(400000);
  4.   for (int i = 0; i < 100000; i++)
  5.     result.AddRange(BitConverter.GetBytes(i));
  6.  
  7.   return result.ToArray();
  8. }

Method 2 – Using MemoryStream

  1. public static byte[] GetBytes()
  2. {
  3.   using (MemoryStream ms = new MemoryStream(400000))
  4.   {
  5.     using (BinaryWriter writer = new BinaryWriter(ms))
  6.     {
  7.     for (int i = 0; i < 100000; i++)
  8.       writer.Write(i);
  9.     }
  10.     return ms.GetBuffer();
  11.   }
  12.  
  13. }


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:

  1. Stopwatch sw = new Stopwatch();
  2. sw.Start();
  3. byte[] result = ArrayFormatter.GetBytes();
  4. sw.Stop();
  5. Console.WriteLine(string.Format("ArrayFormatter time = {0} value = {1} length = {2}",sw.ElapsedMilliseconds,result[12],result.Length));
  6.            
  7. sw.Reset();
  8.  
  9. sw.Start();
  10. result = MemoryStreamFormatter.GetBytes();
  11. sw.Stop();
  12. 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:p1

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 -

  1. public void InsertRange(int index, IEnumerable<T> collection)
  2. {
  3.   if (collection == null)
  4.   {
  5.     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
  6.   }
  7.   if (index > this._size)
  8.   {
  9.     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
  10.   }
  11.   ICollection<T> collection2 = collection as ICollection<T>;
  12.   if (collection2 != null)
  13.   {
  14.     int count = collection2.Count;
  15.     if (count > 0)
  16.     {
  17.       this.EnsureCapacity(this._size + count);
  18.       if (index < this._size)
  19.       {
  20.         Array.Copy(this._items, index, this._items, index + count, this._size - index);
  21.       }
  22.       if (this == collection2)
  23.       {
  24.         Array.Copy(this._items, 0, this._items, index, index);
  25.         Array.Copy(this._items, index + count, this._items, index * 2, this._size - index);
  26.       }
  27.       else
  28.       {
  29.         T[] array = new T[count];
  30.         collection2.CopyTo(array, 0);
  31.         array.CopyTo(this._items, index);
  32.       }
  33.       this._size += count;
  34.     }
  35.   }
  36.   else
  37.   {
  38.     using (IEnumerator<T> enumerator = collection.GetEnumerator())
  39.     {
  40.       while (enumerator.MoveNext())
  41.       {
  42.         this.Insert(index++, enumerator.Current);
  43.       }
  44.     }
  45.   }
  46.   this._version++;
  47. }

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.

Friday, December 16, 2011

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:

  1. [InheritedExport(typeof(ICollider))]
  2. public class BasicCollider : ICollider
  1. [InheritedExport(typeof(IDrawer))]
  2. public class BasicDrawer : IDrawer
  1. [InheritedExport(typeof(IMover))]
  2. public class BasicMover : IMover

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

  1. private void LoadExtensibility()
  2. {
  3.   Assembly applicationAssembly =  Assembly.GetAssembly(GetType());
  4.   string extensibilityPath = System.IO.Path.Combine(System.IO.Path.GetDirectoryName(applicationAssembly.Location), ConfigurationManager.AppSettings["Extensibility"]);
  5.  
  6.   AggregateCatalog catalog = new AggregateCatalog();
  7.   catalog.Catalogs.Add(new DirectoryCatalog(extensibilityPath));
  8.   _container = new CompositionContainer(catalog);
  9.  
  10.   try
  11.   {
  12.     this._container.ComposeParts(this);
  13.   }
  14.   catch (CompositionException compositionException)
  15.   {
  16.     Console.WriteLine(compositionException.ToString());
  17.   }
  18.  
  19.   IEnumerable<Lazy<ICollider>> tempColliders = _container.GetExports<ICollider>();
  20.   foreach (Lazy<ICollider> collider in tempColliders)
  21.     Colliders.Add(new StrategyAdapter(collider.Value));
  22.  
  23.   IEnumerable<Lazy<IMover>> tempMovers = _container.GetExports<IMover>();
  24.   foreach (Lazy<IMover> mover in tempMovers)
  25.     Movers.Add(new StrategyAdapter(mover.Value));
  26.  
  27.   IEnumerable<Lazy<IDrawer>> tempDrawers = _container.GetExports<IDrawer>();
  28.   foreach (Lazy<IDrawer> drawer in tempDrawers)
  29.     Drawers.Add(new StrategyAdapter(drawer.Value));
  30.  
  31. }

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

Saturday, December 3, 2011

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?

  1. class Program
  2. {
  3.   static void Main(string[] args)
  4.   {
  5.     Task t0 = new Task(() => { PrintNumber(0); });
  6.     Task t1 = new Task(() => { PrintNumber(1); });
  7.     t0.Start();
  8.     t1.Start();
  9.     Task.WaitAll(t0, t1);
  10.   }
  11.  
  12.   public static void PrintNumber(int number)
  13.   {
  14.     lock ("Monkey")
  15.     {
  16.       for (int i = 0; i < 10; i++)
  17.       {
  18.         Console.Out.Write(number);
  19.         Thread.Sleep(200);
  20.       }
  21.     }
  22.   }
  23. }

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:

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

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 Smile

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.