Alois Kraus

blog

  Home  |   Contact  |   Syndication    |   Login
  113 Posts | 8 Stories | 297 Comments | 162 Trackbacks

News



Article Categories

Archives

Post Categories

Image Galleries

Programming

If you want to write scalable applications with a high throughput you need to take care of good data structure design to make your application scale. If you want to read for example 200 MB data from a file and process it you can finish it in 5 or 30s. To be on the 5s side it is educational to see how fast you actually can get. To measure the raw disc performance I do read the file into a pre allocated byte array.

[Test]
public void ReadFile_Store_In_ByteArray()
{
    var sw = Stopwatch.StartNew();
    int read = 0;
    int numRead = 0;
    using (FileStream rStream = new FileStream(TestData, FileMode.Open, FileAccess.Read, FileShare.ReadWrite, 4096, FileOptions.SequentialScan))
    {
        byte[] bytes = new byte[210 * 1024 * 1024];

        while ((numRead = rStream.Read(bytes, read, 4096)) > 0)
        {
            read += numRead;
        }
    }
    Console.WriteLine("Did read {0:N0} bytes in {1:F2}s", read, sw.Elapsed.TotalSeconds);
}

***** UnitTests.PushingLimits.ReadFile_Store_In_ByteArray
Did read 216.000.003 bytes in 0,60s

Not bad. The Windows cache does deliver 360 MB/s to my application. If I read the file  the first time I see the real disc performance which is around 160 MB which is still quite good for my Intel PostVille X25M. One common myth many believe in is that if you are reading from disc you can process the data much faster than you can read. Lets try it out. This time we do simply read the file line by line and store the lines in a List<string>.

 

[Test]
public void ReadFile_Store_InList()
{
    var sw = Stopwatch.StartNew();
    FileStream rStream = new FileStream(TestData, FileMode.Open, FileAccess.Read, FileShare.ReadWrite, 4096, FileOptions.SequentialScan);
    int lineNo = 0;
    List<string> lines = new List<string>(2*1000*1000);
    using (StreamReader reader = new StreamReader(rStream))
    {
        string line;
        while ((line = reader.ReadLine()) != null)
        {
            lineNo++;
            lines.Add(line);
        }
    }
    Console.WriteLine("Did read {0:N0} lines in {1:F2}s", lineNo, sw.Elapsed.TotalSeconds);
}

***** UnitTests.PushingLimits.ReadFile_Store_In_List
Did read 2.000.000 lines in 4,92s

Why the heck ware we over 8 times slower? I did not do anything with them! Ok to read form the files the strings we need a StreamReader which needs to convert the byte array into a char array and then into a string. The input file was an ASCII file which means that while we convert a 200 MB file into strings we consume 400 MB of memory because .NET strings are UTF-16. These things do certainly cost us some performance but not 8 times. Lets do the same but this time we do only count the lines of the file.

 

[Test]
public void ReadFile()
{
    var sw = Stopwatch.StartNew();
    FileStream rStream = new FileStream(TestData, FileMode.Open, FileAccess.Read, FileShare.ReadWrite, 4096, FileOptions.SequentialScan);
    int lineNo = 0;
    using (StreamReader reader = new StreamReader(rStream))
    {
        string line;
        while ((line = reader.ReadLine()) != null)
        {
            lineNo++;
        }
    }
    Console.WriteLine("Did read {0:N0} lines in {1:F2}s", lineNo, sw.Elapsed.TotalSeconds);
}

 

***** UnitTests.PushingLimits.ReadFile
    Did read 2.000.000 lines in 1,57s

Thats more like it. From 0,6s to 1,6s is still slower but here we do see what decoding the byte array into .NET strings actually cost. It is not as bad as it looks since we did not yet process (e.g. parse, convert,…) the lines yet which does also add a significant amount of time. But why are we getting over 3 times faster when we throw away our read data instead of keeping it? The Garbage Collector should not have any work to do if we keep all our data in a list. As it turns out this is the point.

The GC has a lot more to do if we store the strings in a list since we add 2 million string references to an array. The GC kicks in from time to time to clean up any garbage and needs to traverse the complete object graph which just becomes more and more complex if we add more managed references to our list.

If your managed application consumes over a few hundred MB of memory it will become much slower if the data is stored in the object graph which needs to be traversed by the GC. It is as simple as that. The more managed references you add the more work the GC has to do for each full GC. To prove this point lets look what happens if we switch from classes to structs which are value types and not under GC control.

First we define a class which has 10 long values stored

class ClassContainer
{
    public ClassContainer(long value)
    {
        v1 = value++;
        v2 = value++;
        v3 = value++;
        v4 = value++;
        v5 = value++;
        v6 = value++;
        v7 = value++;
        v8 = value++;
        v9 = value++;
        v10 = value++;
    }
    long v1,v2,v3,v4,v5,v6,v7,v8,v9,v10;
}

A long value consumes 8 bytes which attributes to 80 bytes of payload of our class.

[Test]
public void Create_Class_List()
{
    var start = GC.GetTotalMemory(true);
    var sw = Stopwatch.StartNew();
    var arr = new ClassContainer[N];
    for (int i = 0; i < arr.Length; i++)
    {
        arr[i] = new ClassContainer(i);
    }
    sw.Stop();
    Console.WriteLine("Did insert {0:N0} classes into list. {1:F2}s, GC Memory: {2:N0}",
                        arr.Length, sw.Elapsed.TotalSeconds, GC.GetTotalMemory(true)-start);
}

***** UnitTests.StructVsClass.Create_Class_List
Did insert 5.000.000 classes into list. 3,74s, GC Memory: 459.996.312

 

Now lets to the same thing for a struct with the same content.

[Test]
public void Create_Struct_List()
{
    var start = GC.GetTotalMemory(true);
    var sw = Stopwatch.StartNew();
    var arr = new StructContainer[N];
    for (int i = 0; i < arr.Length; i++)
    {
        arr[i] = new StructContainer(i);
    }
    sw.Stop();
    Console.WriteLine("Did insert {0:N0} structs into list. {1:F2}s, GC Memory: {2:N0}",
        arr.Length, sw.Elapsed.TotalSeconds, GC.GetTotalMemory(true)-start);

    Console.WriteLine("Class Memory = N*(10*8+Reference+9) = {0:N0}, Struct Memory = N*10*8 = {1:N0}",
        N * (10 * 8 + IntPtr.Size+9), N * 10 * 8);
}

***** UnitTests.StructVsClass.Create_Struct_List
Did insert 5.000.000 structs into list. 0,58s, GC Memory: 400.00.096
Class Memory = N*(10*8+Reference+9) = 465.000.000, Struct Memory = N*10*8 = 400.000.000

 

Although we do insert the same amount of data the performance does differ over a factor 6! This is the price you pay if the GC needs to do more work. Things will become worse if you are a 64 bit application with several GB of memory consumption. Did you notice that (especially managed) applications with a high memory consumption react slowly on user input? It could be that the application does not do much but the GC brings it down. If you want to write an application with a high data throughput and high memory consumption you will hit a wall if you do not take care to design your application more GC friendly.

To declare all classes as structs is not the solution since you are then copying the data by value with every function call you pass the data around which is for my 80 byte structure a quite big overhead. Luckily you can create data structures which do play well with the GC. I will give you some unique data structures in my next posts. It is possible to use structures as general purpose data container with very little overhead …

posted on Saturday, August 13, 2011 12:03 AM

Feedback

# re: Do You Know The Costs Of Garbage? 8/13/2011 6:51 AM Omer Raviv
Very interesting! looking forward to reading more.

# re: Do You Know The Costs Of Garbage? 12/30/2012 1:59 PM Ark-kun
>This is the price you pay if the GC needs to do more work.
You've never proved that's the cause. I don't think so.

# re: Do You Know The Costs Of Garbage? 1/2/2013 10:03 AM Alois Kraus
If my test is wrong please tell me where it is wrong. I want to make correct tests of course and I do want to eradicate any false statements here. Could you elaborate a bit more what is wrong?

Post A Comment
Title:
Name:
Email:
Comment:
Verification: