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.