Riddle me this

We recently published some code riddles,

It was really fun writing them and we had a lot of good responses from Software developers who enjoyed solving them.

The solvers of the riddles got a nice T-Shirt:

For those of you who enjoy riddles here they are:

1. Follow the bread crumb trail from here:
   
2. Go to http://riddle.guru 

Enjoy :-)

How to split an array in C#?

Every now and then, we need to perform mundane operations that are very simple but don't have a built-in function in the language. So we write some ad-hoc code, maybe even copy something from StackOverflow and are done with it. What we sometimes fail to notice, however, is the affect this has on performance.

This entry will focus on splitting an array, but this is relevant for other operations as well.

The time it takes to perform an operation is only important if the code is in a time-critical section and/or is performed a large amount of times. If this is not the case, whatever implementation you choose will probably be OK.

Having said that, let's look at some of the ways to split an array. We'll use a medium sized byte array for this purpose (256), splitting it to a short array (16 bytes) and the rest.

Assuming you are using .Net 3.5+, the most natural way to go about this is to use LINQ:

private static void SplitArayUsingLinq(byte[] data)
{
         byte[] first = data.Take(16).ToArray();
         byte[] second = data.Skip(16).ToArray();
}

As you can see, the method is very elegant, only 1 line of code required to create each part. In addition, it seems like using Take and Skip on a small number of runs can't cause a performance issue.

However, running the above code a 1,000,000 times takes around 10 seconds, which is a considerable amount of time.

Let's compare the LINQ version to a good old for loop:

private static void SplitUsingForLoop(byte[] data)
{
 byte[] first = new byte[16];
 for (int i = 0; i < first.Length; i++)
 {
  first[i] = data[i];
 }
 byte[] second = new byte[data.Length - first.Length];
 for (int i = 0; i < second.Length; i++)
 {
  second[i] = data[i + first.Length];
 }
}

This yields a run time of less than 2 seconds – more than x5 improvement! The looping method seems to be much more efficient. Let's try to improve this some more.

If we do our Googling right, we find that copying arrays actually is a library function – Array.Copy. Let's test this:

private static void SplitArrayUsingArrayCopy(byte[] data)
{
         byte[] first = new byte[16];
         Array.Copy(data, first, first.Length);
         byte[] second = new byte[data.Length - first.Length];
         Array.Copy(data, first.Length, second, 0, second.Length);
}

We get a result of 250ms – another x8 improvement, a total of x40 compared to the LINQ version!

Digging even dipper and only in the case of byte[], we can use another method called Buffer.BlockCopy that actually performs a low level byte copy:

private static void SplitArrayUsingBlockCopy(byte[] data)
{
         byte[] first = new byte[16];
         Buffer.BlockCopy(data, 0, first, 0, first.Length);
         byte[] second = new byte[data.Length - first.Length];
         Buffer.BlockCopy(data, first.Length, second, 0, second.Length);
}

Now the results are 180ms, which is yet another improvement, albeit not as dramatic as the previous ones.

In conclusion:

Method	Time for 1,000,000 splits (s)	Improvement factor
LINQ	10.2	-
for loop	1.93	x5
Array.Copy	0.25	x40
Buffer.BlockCopy	0.18	x56

Kids, don't trust LINQ blindly for what really matters J

Consumption of Large Json objects from the IIS

In my previous post I talked about binary serialization of Large Objects. Today, I‘m going to talk about the consumption of such objects from the IIS.

In this case our recommendation is: always stream objects, don't create intermediate strings or similar, because you will find yourself with "Out of memory etc..." exceptions.

First, let’s update our client so it will ask for “gzip” stream:

public class SpecialisedWebClient :  WebClient
{
      protected override WebRequest GetWebRequest(Uri address)
      {
           HttpWebRequest request = base.GetWebRequest(address) as HttpWebRequest;
           request.AutomaticDecompression = DecompressionMethods.Deflate | DecompressionMethods.GZip;
           request.Timeout = 90 * 60 * 1000;
           return request ;
      }
}

Next, an Asp .NET application usually has a controller which returns some JsonResult. We introduced the new class LargeJsonResult which is returned instead:

public class LargeJsonResult : JsonResult
{
       public override void ExecuteResult(ControllerContext context)
       {
            context.HttpContext.Response.ContentType = "application/json";

            if(ReturnCompressedStream())
            {
                 context.HttpContext.Response.AppendHeader("Content-encoding", "gzip");

                 using (GZipStream gZipStream = new GZipStream(response.OutputStream, CompressionMode.Compress))
                 {
                      SerializeResponse(gZipStream, Data); 
                 }
            }
            else
            {
                 SerializeResponse(gZipStream, Data); 
            }
       }

       private bool ReturnCompressedStream(ControllerContext context)
       {
            string acceptEncoding = context.HttpContext.Request.Headers["Accept-Encoding"];
            if (!string.IsNullOrEmpty(acceptEncoding) && acceptEncoding.ToLowerInvariant().Contains("gzip"))
            {                
               return true;
            }

            return false;
      }

      private static void SerializeResponse(Stream stream, object data)
      {
           using (StreamWriter streamWriter = new StreamWriter(stream))
           using (JsonWriter writer = new JsonTextWriter(streamWriter))
           {
                JsonSerializer serializer = new JsonSerializer();

                streamWriter.AutoFlush = true;
                serializer.Serialize(writer, data);
           }
      }
}

Here we use the Newtonsoft Json Serializer. As you can see, the Json object is streamed to the Client, so the last thing what we need to do is to update the Clients' code for the consumption of this object:

using (SpecialisedWebClient client = new SpecialisedWebClient())
{
      client.Headers.Add("Content-Type: application/json");

      using (Stream stream = client.OpenRead(serviceUri))   
      using (StreamReader reader = new StreamReader(stream, System.Text.Encoding.UTF8))
      using (JsonReader jreader = new JsonTextReader(reader))
      {
           JsonSerializer js = new JsonSerializer();    

           return js.Deserialize<JObject>(jreader);
      }
}

That's it. Now you can transfer GBs of Json data over the wire.

Note: In my previous post, I talked about large objects serialization and our custom implementation of ISerializable. Apparently, when the Json re-presentation of this object is streamed from the IIS using Newtonsoft serializer it calls to ISerializable method and instead of Json the binary stuff is displayed. In order to disable this behavior we need to add the attribute [JsonObjectAttribute] on top of the object.

Large objects serialization with C#.

Preface, I’m going to talk about the serialization of Large objects (with size of hundreds of MBs or even GBs). It's better to keep things small, but it's not always possible due to large architecture changes, so we've decided to take it to the limits (where we actually are limited only by PC’s physical memory).

Let’s say we have the classes:

[Serializable]
public class Result
{
    public string Uri { get; set; }
    public List<Data> AData{ get; set; }
}

[Serializable]
public class Data
{  
    public string Data1{ get; set; }  
    public string Data2{ get; set; }
}

We want to Binary serialize the Result class with, for example, 10 million Data objects inside in order to persist to storage. Later, it should be de-serialized back.

First,we used the .Net binary serializer and got:

System.Runtime.Serialization.SerializationException: The internal array cannot expand to greater than Int32.MaxValue elements. You could find the explanation of that issue here.

Next step was to implement the ISerializable interface and handle the serialization of the Datas collection explicitly. We used the Newtonsoft Json serializer: 

[Serializable]
public class Result : ISerializable
{
    public string Uri { get; set; }
    public List<Data> AData{ get; set; }

    public Result()
    {
    }

    protected Result(SerializationInfo info, StreamingContext context)
    {
        Uri = info.GetString("Uri");
        AData= JsonConvert.DeserializeObject<List<Data>>(info.GetString("AData"));  
    }

    public void GetObjectData(SerializationInfo info, StreamingContext context)
    {
        info.AddValue("Uri", Uri, typeof(string));
        info.AddValue("AData", (JsonConvert.SerializeObject(AData, Formatting.None)));
    }    
}

It didn't work either: 

System.OutOfMemoryException: Exception of type 'System.OutOfMemoryException' was thrown.

   at System.Text.StringBuilder.ToString()

   at Newtonsoft.Json.JsonConvert.SerializeObject(Object value, Formatting formatting, JsonSerializerSettings settings) in JsonConvert.cs:line 755

The next one is the protobuf-net. You have to add attributes to your classes:

[Serializable]
[ProtoContract]
public class Data
{
     [ProtoMember(1)]
     public string Data1{ get; set; }
     [ProtoMember(2)]
     public string Data2{ get; set; }
}

Also in the Result class we added support to GzipStream:

[Serializable]
public class Result : ISerializable
{

    public void GetObjectData(SerializationInfo info, StreamingContext context)
    {
        info.AddValue("Uri", Uri, typeof(string));
        PopulateFieldWithData(info, "AData", AData);   
    }

    protected Result(SerializationInfo info, StreamingContext context)
    {
        Uri = info.GetString("Uri");
        AData= GetObjectsByField<List<Data>>(info, "AData");
    }

    private static void PopulateFieldWithData<T>(SerializationInfo info, string fieldName, T obj)
    {
        using (MemoryStream compressedStream = new MemoryStream(),
               MemoryStream byteStream = new MemoryStream())
        {
              Serializer.Serialize<T>(byteStream, obj);
              byteStream.Position = 0;

              using (GZipStream zipStream = new GZipStream(compressedStream, CompressionMode.Compress))
              {
                  byteStream.CopyTo(zipStream);
              }

              info.AddValue(fieldName, compressedStream.ToArray());
       }
   }

   private static T GetObjectsByField<T>(SerializationInfo info, string dataField)
   {
         byte[] byteArray = (byte[])info.GetValue(dataField, typeof(byte[]));

         using (MemoryStream compressedStream = new MemoryStream(byteArray))
         using (MemoryStream dataStream = new MemoryStream())
         using (GZipStream uncompressedStream = new GZipStream(compressedStream, CompressionMode.Decompress))
         {
               uncompressedStream.CopyTo(dataStream);

               dataStream.Position = 0;
               return Serializer.Deserialize<T>(dataStream);
         }
   }
}

It didn't work as well. Even though it didn't crashed, apparently it entered to an endless loop.

Here, we realized that we need to split the Datas collection during the serialization/de-serilization.

Main idea is to take each time, let’s say, 1 million Data objects, serialize them and add to the Serialization Info as a separate field. During the de-serialization these objects should be taken separately and merged to one collection. I updated the Result class with a few more functions:

private const string ADataCountField= "ADataCountField";
private const int NumOfDataObjectsPerSerializedPage = 1000000;

public void GetObjectData(SerializationInfo info, StreamingContext context)
{
       info.AddValue("Uri", Uri, typeof(string));
       SerializeAData(info);   
}

private void SerializeAData(SerializationInfo info)
{
       int numOfADataFields = Datas == null ? 0 :
              (int)Math.Ceiling(Datas.Count / (Double)NumOfDataObjectsPerSerializedPage );

       info.AddValue(ADataCountField, numOfADataFields );

       for (int i = 0; i < numOfADataFields ; i++)
       {
             List<Data> page = Datas.Skip(NumOfDataObjectsPerSerializedPage * i).Take(NumOfDataObjectsPerSerializedPage ).ToList();
             PopulateFieldWithData(info, "AData" + i, page);
       }
}

protected Result(SerializationInfo info, StreamingContext context)
{
        Uri = info.GetString("Uri");
        DeserializeAData(info);
}

private void DeserializeAData(SerializationInfo info)
{
        AData = new List<Link>();
        int aDataFieldsCount = info.GetInt32(ADataCountField);

        for (int i = 0; i < aDataFieldsCount ; i++)
        {
            List<Data> dataObjects= GetObjectsByField<List<Data>>(info, "AData" + i);
            Datas.AddRange(dataObjects);
        }
}

Finally, it worked!