How fast is .NET Garbage Collector? Part 2.

by Miłosz Orzeł 12. June 2014 20:58

Read the first part of the article if you haven’t done so already. Part 1 has a brief overview of what GC is and how it performs its magic. It contains a test of GC performance with regards to large array of bytes. You can also find there a detailed information about my test environment…

This part will focus on scenarios which put a lot more pressure on GC and appear more commonly in real world applications. You will see that even a tree of more than 100 million objects can be handled quickly… But first let’s see how GC responds to big array of type object:

static void TestSpeedForLargeObjectArray()
{
    Stopwatch sw = new Stopwatch();

    Console.Write(string.Format("GC.GetTotalMemory before creating array: {0:N0}. Press key any to create array...", GC.GetTotalMemory(true)));
    Console.Read();
    object[] array = new object[100 * 1000 * 1000]; // About 800 MB (3.2 GB when filled with object instances)
             
    sw.Start();
    for (int i = 0; i < array.Length; i++)
    {
        array[i] = new object();
    }
    Console.WriteLine("Setup time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after creating array: {0:N0}. Press Enter to set array to null...", GC.GetTotalMemory(true)));

    if (Console.ReadKey().Key == ConsoleKey.Enter)
    {
        Console.WriteLine("Setting array to null");
        array = null;
    }
    
    sw.Restart();
    GC.Collect();
    Console.WriteLine("Collection time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after GC.Collect: {0:N0}. Press any key to finish...", GC.GetTotalMemory(true)));

    Console.WriteLine(array); // To avoid compiler optimization...
    Console.ReadKey();
}

Above test creates and array of 100 million items. Initially such array takes about 800 megabytes of memory (on x64 platform). This part is allocated on LOH. When object instances are created total heap allocation jumps to 3.2 GB. Array items are tiny so they are part of Small Object Heap and initially belong to Gen 0.

Here are the test results for situation when array is set to null:

GC.GetTotalMemory before creating array: 41,736. Press key any to create array...
Press any key to fill array...
Setup time: 00:00:07.7910574
GC.GetTotalMemory after creating array: 3,200,057,616. Press Enter to set array to null...
Setting array to null
Collection time: 00:00:00.7481998
GC.GetTotalMemory after GC.Collect: 57,624. Press any key to finish...

It took only about 700 ms to reclaim over 3 GB of memory!

Take a look at this graph from Performance Monitor:

Managed memory counters for large object[] array; setting array to null... Click to enlarge...

You can see that while program was filling the array, Gen 0 and Gen 1 changed size (notice though that the scale for these is 100x bigger than scale for other counters). This means that GC cycles were triggered while items were created - this is expected behavior. Notice how Gen 2 and LOH size adds up to total bytes on managed heap.

What if instead of setting array reference to null we set array items to null?

Let’s see. Here’s the graph:

Managed memory counters for large object[] array; setting array items to null... Click to enlarge...

Notice that after GC.Collect is done 800 MB are still allocated - this is LOH memory held by array itself…

Here are the results:

GC.GetTotalMemory before creating array: 41,752. Press key any to create array...
Press any key to fill array...
Setup time: 00:00:07.7707024
GC.GetTotalMemory after creating array: 3,200,057,632. Press Enter to set array elements to null...
Setting array elements to null
Collection time: 00:00:01.0926220
GC.GetTotalMemory after GC.Collect: 800,057,672. Press any key to finish...

Ok, enough with arrays. One can argue that as continues blocks of memory they are easier to handle then complex objects structures that are abundant in real word programs.

Let’s create a very big tree of small reference types:

static int _itemsCount = 0;

class Item
{
    public Item ChildA { get; set; }
    public Item ChildB { get; set; }
    
    public Item()
    {
        _itemsCount++;
    }           
}

static void AddChildren(Item parent, int depth) 
{
    if (depth == 0)
    {
        return;
    }
    else
    {
        parent.ChildA = new Item();
        parent.ChildB = new Item();

        AddChildren(parent.ChildA, depth - 1);
        AddChildren(parent.ChildB, depth - 1);                
    }
}

static void TestSpeedForLargeTreeOfSmallObjects()
{
    Stopwatch sw = new Stopwatch();

    Console.Write(string.Format("GC.GetTotalMemory before building object tree: {0:N0}. Press any key to build tree...", GC.GetTotalMemory(true)));
    Console.ReadKey();

    sw.Start();
    _itemsCount = 0;       
    Item root = new Item();            
    AddChildren(root, 26);
    Console.WriteLine("Setup time: " + sw.Elapsed);
    Console.WriteLine("Number of items: " + _itemsCount.ToString("N0"));

    Console.WriteLine(string.Format("GC.GetTotalMemory after building object tree: {0:N0}. Press Enter to set root to null...", GC.GetTotalMemory(true)));

    if (Console.ReadKey().Key == ConsoleKey.Enter)
    {
        Console.WriteLine("Setting tree root to null");
        root = null;                
    }
    
    sw.Restart();
    GC.Collect();
    Console.WriteLine("Collection time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after GC.Collect: {0:N0}. Press any key to finish...", GC.GetTotalMemory(true)));
                
    Console.WriteLine(root); // To avoid compiler optimization...            
    Console.ReadKey();
}

The test presented above creates a tree with over 130 million nodes which take almost 4.3 GB of memory.

Here’s what happens when tree root is set to null:

GC.GetTotalMemory before building object tree: 41,616. Press any key to build tree...
Setup time: 00:00:14.3355583
Number of items: 134,217,727
GC.GetTotalMemory after building object tree: 4,295,021,160. Press Enter to set root to null...
Setting tree root to null
Collection time: 00:00:01.1069927
GC.GetTotalMemory after GC.Collect: 53,856. Press any key to finish...

Managed memory counters for large tree of small objects; setting tree root to null... Click to enlarge...

It took only 1.1 second to clear all the garbage! When root reference was set to null all nodes below it became useless as defined by mark and sweep algorithm… Notice that this time LOH is not utilized as no single object instance is over 85 KB threshold.

Now let’s see what happens when the root is not set to null and all the objects survive GC cycle:

GC.GetTotalMemory before building object tree: 41,680. Press any key to build tree...
Setup time: 00:00:14.3915412
Number of items: 134,217,727
GC.GetTotalMemory after building object tree: 4,295,021,224. Press Enter to set root to null...
Collection time: 00:00:03.7172580
GC.GetTotalMemory after GC.Collect: 4,295,021,184. Press any key to finish...

This time it took 3.7 sec (less than 28 nanoseconds per reference) for GC.Collect to run – remember that reachable references put more work on GC then dead one!

There is one more scenario we should test. Instead of setting root = null let's set root.ChildA = null. This way half of the tree would became unreachable. GC will have a chance to reclaim memory and compact it to avoid fragmentation. Check the results:

GC.GetTotalMemory before building object tree: 41,696. Press any key to build tree...
Setup time: 00:00:15.1326459
Number of items: 134,217,727
GC.GetTotalMemory after creating array: 4,295,021,240. Press Enter to set root.ChildA to null...
Setting tree root.ChildA to null
Collection time: 00:00:02.5062596
GC.GetTotalMemory after GC.Collect: 2,147,537,584. Press any key to finish...

Time for final test. Let’s create a tree of over 2 million complex nodes that contain some object references, small array and unique string. Additionally lets fill some of the MixedItem instances with byte array big enough to be put on Large Object Heap.

static int _itemsCount = 0;

class MixedItem
{
    byte[] _smallArray;
    byte[] _bigArray;
    string _uniqueString;

    public MixedItem ChildA { get; set; }
    public MixedItem ChildB { get; set; }

    public MixedItem()
    {
        _itemsCount++;

        _smallArray = new byte[1000];
        if (_itemsCount % 1000 == 0)
        {
            _bigArray = new byte[1000 * 1000];
        }

        _uniqueString = DateTime.Now.Ticks.ToString();
    }
}

static void AddChildren(MixedItem parent, int depth)
{
    if (depth == 0)
    {
        return;
    }
    else
    {
        parent.ChildA = new MixedItem();
        parent.ChildB = new MixedItem();

        AddChildren(parent.ChildA, depth - 1);
        AddChildren(parent.ChildB, depth - 1);
    }
}

static void TestSpeedForLargeTreeOfMixedObjects()
{
    Stopwatch sw = new Stopwatch();

    Console.Write(string.Format("GC.GetTotalMemory before building object tree: {0:N0}. Press any key to build tree...", GC.GetTotalMemory(true)));
    Console.ReadKey();

    sw.Start();
    _itemsCount = 0;
    MixedItem root = new MixedItem();
    AddChildren(root, 20);
    Console.WriteLine("Setup time: " + sw.Elapsed);
    Console.WriteLine("Number of items: " + _itemsCount.ToString("N0"));

    Console.WriteLine(string.Format("GC.GetTotalMemory after building object tree: {0:N0}. Press Enter to set root to null...", GC.GetTotalMemory(true)));

    if (Console.ReadKey().Key == ConsoleKey.Enter)
    {
        Console.WriteLine("Setting tree root to null");
        root = null;
    }

    sw.Restart();
    GC.Collect();
    Console.WriteLine("Collection time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after GC.Collect: {0:N0}. Press any key to finish...", GC.GetTotalMemory(true)));

    Console.WriteLine(root); // To avoid compiler optimization...
    Console.ReadKey();
}

How will GC perform when subjected to almost 4.5 GB of managed heap memory with such complex structure? Test results for setting root to null

GC.GetTotalMemory before building object tree: 41,680. Press any key to build tree...
Setup time: 00:00:11.5479202
Number of items: 2,097,151
GC.GetTotalMemory after building object tree: 4,496,245,632. Press Enter to set root to null...
Setting tree root to null
Collection time: 00:00:00.5055634
GC.GetTotalMemory after GC.Collect: 54,520. Press any key to finish...

Managed memory counters for large tree of mixed objects; setting tree root to null... Click to enlarge...

And in case you wonder, here's what happens when root is not set to null:

GC.GetTotalMemory before building object tree: 41,680. Press any key to build tree...
Setup time: 00:00:11.6676969
Number of items: 2,097,151
GC.GetTotalMemory after building object tree: 4,496,245,632. Press Enter to set root to null...
Collection time: 00:00:00.5617486
GC.GetTotalMemory after GC.Collect: 4,496,245,592. Press any key to finish...

So what it all means? The conclusion is that unless you are writing applications which require extreme efficiency or total guarantee of uninterrupted execution, you should be really glad that .NET uses automatic memory management. GC is a great piece of software that frees you from mundane and error prone memory handling. It lets you focus on what really matters: providing features for application users. I’ve been professionally writing .NET applications for past 8 years (enterprise stuff, mainly web apps and Windows services) and I’m yet to witness1 a situation when GC cost would be a major factor. Usually performance bottleneck lays in things like: bad DB configuration, inefficient SQL/ORM queries, slow remote services, bad network utilization, lack of parallelism, poor caching, sluggish client side rendering etc. If you avoid basic mistakes like creating to many strings you probably won’t even notice that there is a Garbage Collector :)

1. I’ve met some out of memory exceptions related to LOH fragmentation. The good thing is that LOH algorithms are improving and x86 platform, which is especially susceptible to such errors, is becoming a thing of the past…

How fast is .NET Garbage Collector? Part 1.

by Miłosz Orzeł 29. May 2014 21:08

.NET GC is very fast! Well... I hope you need more than this reassuring statement, if so, read on :) I will show you some test results to prove that I’m not lying but first I will give you a quick reminder about what GC is:

Garbage Collector is fundamental component of .NET CLR. It takes care of freeing managed heap memory so a programmer doesn’t have to think about deallocation. Contrary to popular belief, GC handles memory occupied for both reference and value types. Why? Because quite often space for things like structures or integers is allocated on the heap. It happens for example when value type is an item of array or is a field in a class instance.

GC in .NET uses mark and sweep algorithm: it walks through objects graph starting from root elements (such us statics, references on stack or registers) and marks every object it can reach. When the walk is done, GC knows it can safely free the memory of objects that have not been marked – because as unreachable they are useless for the application.

For efficiency purposes GC supports notion of generations. When the object is created it belongs to Gen 0 (except for so called large objects). If Gen 0 object survives GC cycle it’s moved to Gen 1. If it survives one more cycle it goes to Gen 2 and stays there (there’s no Gen 31). Most objects are short lived – they don’t get pass Gen 0 or Gen 1 so .NET GC tries to free memory from lower generations first. It does Gen 2 (aka full collection) far less often then Gen 0 collection. If the object is big – above 850002 bytes it is allocated in Large Object Heap (LOH) and goes straight to Gen 2. Treating big objects the same way as small objects would have negative impact on heap defragmentation3 algorithms because moving such objects is time-consuming.

GC supports different modes for workstation and server configurations, is able to do some work in background threads, has to consider special cases like finalizers or pined memory buffers, its settings vary between platforms (e. g. CLR on PC is not the same as the one on Xbox)… well let’s stop here – I’ve promised a “quick reminder”! 

Ok, time for the test! 

In this first post I will show you how fast .NET GC can handle large arrays of value (non-reference) types. The test will involve an array of bytes that occupies about two gigabytes of memory. Despite its large size, such object does not put much pressure on the Garbage Collector. This is because the only reference GC has to check is the one for the array itself. If array becomes unreachable all memory occupied by its elements can be safely reused. Additionally, such array, being part of LOH, is not copied (to avoid heap fragmentation) when it survives collection cycle… In the second installment of this article I will show you how GC can handle more complex scenarios. We will examine performance for object array, and more importantly, a tree of objects with thousands of references… 

Note about test environment: I’ve run the test code on desktop PC with Intel i-5 2400 3.1 GHz 4 Core CPU, 12 GB of DDR 3/1333 RAM, running Windows 7 Ultimate x64. The program was a .NET 4.0 console application compiled in Release mode and run without debugger attached.

Here’s the test code:

static void TestSpeedForLargeByteArray()
{
    Stopwatch sw = new Stopwatch();

    Console.Write(string.Format("GC.GetTotalMemory before creating array: {0:N0}. Press any key to create array...", GC.GetTotalMemory(true)));
    Console.ReadKey();
    byte[] array = new byte[2000 * 1000 * 1000]; // About 2 GB
   
    sw.Start();
    for (int i = 0; i < array.Length; i++)
    {
        array[i] = 1; // Touch array elements to fill working set              
    }          
    Console.WriteLine("Setup time: " + sw.Elapsed);

    Console.WriteLine(string.Format("GC.GetTotalMemory after creating array: {0:N0}. Press Enter to set array to null...", GC.GetTotalMemory(true)));
    if (Console.ReadKey().Key == ConsoleKey.Enter)
    {
        Console.WriteLine("Setting array to null");
        array = null;
    }
               
    sw.Restart();
    GC.Collect();                 
    Console.WriteLine("Collection time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after GC.Collect: {0:N0}. Press any key to finish...", GC.GetTotalMemory(true)));

    Console.WriteLine(array); // To avoid compiler optimization...
    Console.ReadKey();
}

As you can see test is very simple. The code uses two methods of static GC class: GC.GetTotalMemory and GC.Collect. The former returns the amount of allocated managed memory and the latter forces Garbage Collector to do its job and free unused memory. The only thing that might be surprising is the loop that touches array items. Without it you will witness “strange” phenomenon: after array is defined GC.GetTotalMemory would report about 2 GB but you will not see memory usage increase in Task Manager! This is because taskmgr.exe shows Working Set data. You can run more advanced tool: Resource Monitor (resmon.exe) to see what’s happening: 

This is the screenshot before the “touch”:

Memory usage before access to array items. Click to enlarge...

And this is the one after the loop is executed:

Memory usage after access to array items. Click to enlarge...

Here are the test results (yeah, finally):

GC.GetTotalMemory before creating array: 41,568. Press any key to create array...
Setup time: 00:00:01.0633903
GC.GetTotalMemory after creating array: 2,000,053,864. Press Enter to set array to null...
Setting array to null
Collection time: 00:00:00.1443391
GC.GetTotalMemory after GC.Collect: 53,800. Press any key to finish...

What you can see here is that it took GC just around 150 milliseconds to free about 2 GB of memory. Nice, huh? You can appreciate the speed especially if you compare it with 1 second it took to just iterate over the array!

Below is a screenshot from Performance Monitor (perfmon.exe) running couple of .NET memory counters:

Performance Monitor with managed memory counters. Click to enlarge...

Our array is a big object (well over LOH threshold) – hence after it is defined memory of LOH increases yet Gen 0 heap size remains flat. 

Below are the results for GC.Collect run when reference to the array was not set to null:

GC.GetTotalMemory before creating array: 41,568. Press any key to create array..
Setup time: 00:00:01.0385779
GC.GetTotalMemory after creating array: 2,000,053,864. Press Enter to set array to null...
Collection time: 00:00:00.0001287
GC.GetTotalMemory after GC.Collect: 2,000,053,824. Press any key to finish...

Fraction of a millisecond. Totally negligible! Why I’m even mentioning a test for situation when memory is not collected? Well, in part two you will see that GC usually has more work to do when heap items survive collection cycle…

I hope to post the second part of the article in about a week or two. No promises though – you know, life… ;)

Update 26.07.2014: I've changed the screenshot from perfmon (Gen 0 and Gen 1 scale is bigger now).

Update 24.06.2014: I wrote the second part of this article few days ago. Click here to read it.

1. You can use GC.GC.MaxGeneration method to check it.

2. LOH threshold is an implementation detail. Most sources mention 85KB as the limit but it's not always the case - array of doubles with as little as 1000 items goes on LOH (on x86)...

3. .NET 4.5 introduces LOH improvements for better fragmentation prevention through balancing and enhanced free list usage. Future releases will probably have compaction option too.

Why the use of GetPixel and SetPixel is so inefficient!

by Miłosz Orzeł 5. April 2011 23:28

Bitmap class provides two simple methods: GetPixel and SetPixel used respectively to retrieve a point of image (as the Color structure) and set a point of image. The following code illustrates how to retrieve/set all the pixels in the bitmap:

private void GetSetPixel(Bitmap image) {
   for (int x = 0; x < image.Width; x++) {
      for (int y = 0; y < image.Height; y++) {
         Color pixel = image.GetPixel(x, y);
         image.SetPixel(x, y, Color.Black);
      }
   } 
}

As shown, review and modification of pixels is extremely simple. Unfortunately behind the simplicity of the code lies a serious performance trap. While for a small number of references to image points, the speed at which GetPixel and SetPixel work is good enough, for larger images it is not the case. Graph presented below can serve as a proof of that. It shows results of 10 tests* which consisted of 10-fold invocation of previously shown GetSetPixel method for images 100x100 and 1000x1000 pixels in size.

Wyniki testów prędkości operacji na pikselach obrazu z użyciem metod GetPixel i SetPixel klasy Bitmap.

The average test time for an image measuring 100 by 100 pixels was 543 milliseconds. This speed is acceptable if the image processing is not done frequently. Performance problem is, however, clearly visible when you try to use an image of size 1000 per 1000 pixels. Execution of the test in this case takes an average of more than 41 seconds - more than 4 sec. on a single call to GetSetPixel (seriously!).

Why so slow?

Low efficiency is due to the fact that access to the pixel is not a simple reference to a memory area. Each getting or setting of color is associated with invocation of .NET Framework method, which is a wrapper for native function contained in gdiplus.dll. This call is through the mechanism of P/Invoke (Platform Invocation), which is used to communicate from managed code to unmanaged API (API outside of the .NET Framework). So for a bitmap of 1000x1000 pixels there will be 1 million calls to GetPixel method that besides the validation of parameters uses the native GdipBitmapGetPixel function. Before returning color information, GDI+ function has to perform such operations as calculating the position of bytes responsible for description of desired pixel… Similar situation occurs in the case SetPixel method.

Look at the following code of Bitmap.GetPixel method obtained with the .NET Reflector (System.Drawing.dll, .NET Framework 2.0):

public Color GetPixel(int x, int y) {
   int argb = 0;
   if ((x < 0) || (x >= base.Width)) {
      throw new ArgumentOutOfRangeException(“x”, SR.GetString(“ValidRangeX”));
   }
   if ((y < 0) || (y >= base.Height)) {
      throw new ArgumentOutOfRangeException(“y”, SR.GetString(“ValidRangeY”));
   }
   
   int status = SafeNativeMethods.Gdip.GdipBitmapGetPixel(new HandleRef(this, base.nativeImage), x, y, out argb);
   if (status != 0) {
      throw SafeNativeMethods.Gdip.StatusException(status);
   }
   return Color.FromArgb(argb);
}

Here is import of GDI + function:

[DllImport(“gdiplus.dll”, CharSet=CharSet.Unicode, SetLastError=true, 
ExactSpelling=true)]
internal static extern int GdipBitmapGetPixel(HandleRef bitmap, int x, int y, out int argb);

* I have tested on such laptop: HP Pavilion dv5, AMD Turion X2 Dual-Core Mobile RM-70, 3 GB RAM, Vista Home Premium

What for?

I can’t imagine working as a programmer without hundreds of web pages on which people "wasting" their free time share what they managed to find out. Therefore I will try to add a bit of useful information to the web’s resources myself...  - about me

Also on CodeProject!

 207K reads since may 2012 :)

Language

This blog is my first attempt to write in English so if you see any language mistakes please let me know. I didn’t have enough time to translate most of my old posts but I will try to make new ones both in Polish and in English.
Znasz polski? Kliknij tutaj.

History