A case for the struct

C#, caching, finance, garbage collection, low latency, performance, realtime, struct.

Minimizing time spent in a single garbage collection

If you have ever implemented a C# component caching huge amounts of data, with a low latency requirement, it is likely that you have run into garbage collection performance problems.  The problem is that the garbage collector will scan through the hierarchy of all allocated objects and mark them.  When this is done it knows that the remaining objects are not referenced from anywhere and can be safely deleted (or finalized, delaying their deletion until next garbage collection).  The more objects you have allocated, the slower this process will be, even if they never change.

You can keep the number of garbage collections at a minimum by allocating as little as possible while your application is running.  But there is only so much you can do without crippling yourself, and in a typical busy server you will have frequent garbage collections.  And they can be really bad.

In financial institutions data often changes so fast that querying a database is not an option (no pun intended).  Instead a service maintains an in-memory cache of the data, which is queried by clients of the service.  Consider this sample class, simulating a simplified cache with a large number of financial instruments, each keeping track of the last few hundred bid and ask prices of said instrument.

using System.Collections.Generic;

namespace GcTest
{
    public class Price
    {
        public double val1 { get; internal set; }
        public double val2 { get; internal set; }
        public double val3 { get; internal set; }
        public double val4 { get; internal set; }
        public double val5 { get; internal set; }
        public double val6 { get; internal set; }
        public double val7 { get; internal set; }
        public double val8 { get; internal set; }
    }

    class Instrument
    {
        public Instrument(string id)
        {
            Id = id;
            Bid = new List<Price>();
            Ask = new List<Price>();
        }

        public string Id { get; internal set; }
        public List<Price> Bid { get; internal set; }
        public List<Price> Ask { get; internal set; }
    }

    class MegaCache
    {
        public List<Instrument> Instruments { get; private set; }

        // This method fills the cache with some random data
        public void Fill(int instrumentCount, int pricesPerInstrument)
        {
            Instruments = new List<Instrument>(instrumentCount);
            for (int i = 0; i < instrumentCount; ++i)
            {
                Instrument ins = new Instrument("ID" + i);

                for (int j = 0; j < pricesPerInstrument; ++j)
                {
                    ins.Bid.Add(new Price());
                    ins.Ask.Add(new Price());
                }
                Instruments.Add(ins);
            }
        }
    }
}

And then a test program to force garbage collections and measure time spent.

using System;
using System.Threading;
using System.Diagnostics;

namespace GcTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("GC Server: {0}, {1}\n",
                System.Runtime.GCSettings.IsServerGC,
                System.Runtime.GCSettings.LatencyMode);

            MegaCache cache = new MegaCache();
            cache.Fill(50000, 500);

            while (true)
            {
                Stopwatch sw = Stopwatch.StartNew();
                GC.Collect();
                long ms = sw.ElapsedMilliseconds;

                long bytes = GC.GetTotalMemory(false);

                Console.WriteLine(
                    string.Format("Gen2 collections: {0,2} - Memory usage: {1,4}mb, GC time: {2,4}ms",
                    GC.CollectionCount(2),
                    bytes / (1024 * 1024),
                    ms));

                // Pause a moment to not spam console
                Thread.Sleep(500);

                // Cache will be optimized away in release builds if not referenced somewhere
                GC.KeepAlive(cache);
            }
        }
    }
}

Running this program we get the following result:

image

We can see that the first garbage collection took 2.5 seconds and from then on it is pretty stable just below 1.4 seconds.  The cache uses 4.2GB of memory, which is a lot, but not unrealistic.  I’ve worked on projects caching such amounts of data in C#.  But back to the timings.  1.4 seconds is an unacceptably long stall for a low latency application and this is just static data.  In a live environment the garbage collector would have even more work.

Enter the struct

So we have a problem.  What can we do about it?  If we change the class Price to be a struct instead a class, and run the test program again, we get the following result:

public struct Price
{
    public double val1 { get; internal set; }
    public double val2 { get; internal set; }
    public double val3 { get; internal set; }
    public double val4 { get; internal set; }
    public double val5 { get; internal set; }
    public double val6 { get; internal set; }
    public double val7 { get; internal set; }
    public double val8 { get; internal set; }
}

image

There are two major differences.  First, the memory usage is much lower.  This is because the Bid and Ask lists are now one big contiguous block of memory (each) due to struct being a value type, instead of being lists of references to objects allocated elsewhere.  So that is nice, but not the important part.

The garbage collection now takes  ~20-50 ms, instead of 1.4 seconds.  That is on average 40 times faster.

The reason is quite simple.  When the garbage collector reaches the Bid and Ask lists it knows their types and thus it knows that Price is a value type only containing other value types (doubles).  So it doesn’t need to go through them all and look for references to other objects, since there cannot be any.  So instead of scanning through 50000 instruments x (2 x 500 Prices) = 50 mill. objects, it is just 50000 instruments x 2 lists = 100K objects.

A heed of warning

Now, before you go and change all your classes to struct, make sure that you understand the implications of using a value type instead of a reference type and why immutable value types are a good idea.  There is a good read on StackOverFlow and another one on Eric Lippert’s blog.

- 00sharp

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s