Large Objects and Iterator Blocks

Arrays can cause memory issues in .Net. Frances Buontempo shows how iterator blocks can help to relieve the pressure.

C# is a garbage collected language. This allows you to create new objects at will, and the garbage collector will clear them up as and when needed. Despite this, out of memory errors seem to be frighteningly common in some large scale C# applications I have come across. It isn’t just me: Stackoverflow [SO] gives nearly 3,000 questions related to C# and ‘out of memory’. How is this possible, given the hype about automatic memory management through the garbage collector?

Previous articles [ Overload63] have dealt with the IDisposable pattern, with reference to avoiding leaks. This article will instead focus on objects that are likely to make it to the large object heap and therefore probably persist for the lifetime of an application. Let us begin with a brief overview of garbage collection.

Garbage

Garbage collection has a long history. Wikipedia claims ‘ Garbage collection was invented by John McCarthy around 1959 to solve problems in Lisp ’ [GC] . It is an active area of research, used by a variety of languages including python, Java and C# [REJ] . Garbage collection can be implemented in a variety of ways, for example reference counting with cycle detection versus generational, blocking versus concurrent, and many other variations.

.Net uses a generational garbage collector, which ‘moves’ or compacts objects after a collection. Every time a new object is created, it is placed in generation zero. When the garbage collector runs, it drops unused objects from generation zero, queuing up finalizers. The surviving objects are then compacted, unless they have been pinned. Anything that survives the next run gets promoted to generation one. The same happens from time to time with generation one and surviving objects get promoted to generation two. Less frequently, generation two is inspected along with the large object heap. These objects might well last for the lifetime of an application.

This begs the question, ‘What does ‘large’ mean?’

Objects that are greater than approximately 85,000 bytes are treated as large objects by the garbage collector and are directly allocated in a special heap; they are not promoted through the generations. [LOH]

This decision appears to be a performance decision [LOH-MS] . For example, compacting large objects takes longer than compacting small objects. As noted, large objects are only collected when a generation two collection happens, so they could stay around for a very long time, thereby using up a large amount of memory. This can clearly cause problems.

Avoiding arrays

How could an object of approximately 85,000 bytes get created? Though many applications end up with gigantic strings, for example reading a whole file into memory or working with huge amounts of xml, we will focus on numbers rather than strings. Or at least arrays, which frequently crop up in mathematical contexts and contain doubles, for example in a MonteCarlo simulation with, say 100,000 paths, immediately providing over 85,000 bytes. The internet also suggests that arrays of 1,000 or more doubles get placed on the large object heap [LOH-Doubles] , again for performance reasons: ‘ The LOH is aligned to 8 bytes so access to ‘big’ arrays is much faster if it is allocated on the LOH...the best tradeoff is when the array is bigger than 1000 elements. ’

It is hard to imagine why you would ever need all the numbers in the array to be in memory at once. Frequently, an average, maximum or minimum of these numbers will be required. This can be calculated if functions return an IEnumerable<double> rather than a double[] , in other words, if we provide an iterator block instead. These have been around since .Net 2 and a clear and thorough explanation is given in [Skeet] . Put simply, they are ‘syntactic sugar’ which causes the compiler to build a state machine, allowing each request for the next item to be lazily evaluated.

Iterator blocks will work for other objects besides doubles, but without loss of generality consider the following fictitious function.

  public static double[] Value()
  {
    double[] res = new double[10000];
    for (int i = 0; i < 10000; ++i) res[i] = 42.0;
    return res;
  }

The calling code is likely to take the form

  var v = Value();
  foreach (double d in v)
  {
    //do something
  }

The following simple change to the function will reduce the lines of code, which is always a good thing, and reduce the memory it uses, without changing the client code.

  public static IEnumerable<double> Value()
  {
    for (int i = 0; i < 10000; ++i)
        yield return 42.0;
  }

This no longer allocates an array. Since the calling code simply iterates over the items, the iterator block can now yield the required numbers one at a time, using less memory. Significantly, this will no longer shove an array on the large object heap, potentially leaving it hanging around for the lifetime of the application.

Prove it

A high level view of total memory usage is provided by the System.GC object.

  static public void ShowMemory(string explanation)
  {
    long memory = GC.GetTotalMemory(true);
    Console.WriteLine("{0,]30} {1}",
    explanation + ":", memory);
  }

Calling our first value function which allocates a large array of doubles gives 635056 bytes, whereas the second version gives 555088. Though this high level view doesn’t say exactly where the memory is, it does show less is being used. In order to see exactly which objects are taking up how much space, we’d need to use a profiler, such as Microsoft’s CLRProfiler [CLRProfiler4] , or use SOS in Windebug, which is beyond the scope of this article. Clues can be provided by the Performance counters which will give further details about memory usage in each generation and on the large object heap. Sample code is shown in by the ShowGensAndLOHMemory function. Note that some counters update at the end of a garbage collection, not at each allocation [LOH] , so you need to provoke a garbage collection in order to get accurate counts back. The ShowMemory function will do this, since we send true to the GC’s GetTotalMemory function, which forces a full collection (Listing 1).

static public void ShowGensAndLOHMemory()
{
  PerformanceCounter loh =
     new PerformanceCounter(".NET CLR Memory",
     "Large Object Heap size",
     Process.GetCurrentProcess().ProcessName,
     true);
  PerformanceCounter perfGen0Heap =
     new PerformanceCounter(".NET CLR Memory",
     "Gen 0 heap size",
     Process.GetCurrentProcess().ProcessName,
     true);
  PerformanceCounter perfGen1Heap =
     new PerformanceCounter(".NET CLR Memory",
     "Gen 1 heap size",
     Process.GetCurrentProcess().ProcessName,
     true);
  PerformanceCounter perfGen2Heap =
     new PerformanceCounter(".NET CLR Memory",
     "Gen 2 heap size",
     Process.GetCurrentProcess().ProcessName,
     true);

  Console.WriteLine("(loh) memory: {0}",
     loh.NextValue());
  Console.WriteLine("(Gen0) memory: {0}",
     perfGen0Heap.NextValue());
  Console.WriteLine("(Gen1) memory: {0}",
     perfGen1Heap.NextValue());
  Console.WriteLine("(Gen2) memory: {0}",
     perfGen2Heap.NextValue());
}

Listing 1

If this is called on the Value functions above we see a reduction in large object heap memory usage. This proves we have used less overall memory, and specifically less of the large object heap. See Table 1 for details.

	Arrays	Iterator Block
(loh) memory	126248	46216
(Gen0) memory	4194300	4194300
(Gen1) memory	12	12
(Gen2) memory	520004	520052

Table 1

A final example

Suppose we wish to do something a bit more complicated, such as bale out without returning values if a condition is met (Listing 2).

public static double[] ValueAtTime(double t)
{
  Dictionary<double, double> data =
     new Dictionary<double, double> {{-1.0,10.0},
     {0.0, 20.0}, {1.0, 30.0}, {2.0, 40.0}};
  var dates = data.Where(a => a.Key < t);
  if (!dates.Any())
    return new double[0];
  double amount =
     dates.OrderBy(a => a.Key).Last().Value;
  double[] res = new double[10000];
  for (int i = 0; i < 10000; ++i)
      res[i] = amount;
  return res;
}

Listing 2

It is likely the calling code will be very similar to the initial simpler example, though the function returning the numbers is now a little more complicated. This can still be changed to use iterator blocks, most likely without changing the calling code (see Listing 3).

public static IEnumerable<double> 
   ValueAtTime (double t)
{
  Dictionary<double, double> data =
     new Dictionary<double, double> {
       { -1.0, 10.0 }, { 0.0, 20.0 }, 
       { 1.0, 30.0 }, { 2.0, 40.0 } };
  var dates = data.Where(a => a.Key < t);
  if (!dates.Any())
     yield break;
  double amount =
     dates.OrderBy(a => a.Key).Last().Value;
  for (int i = 0; i < 10000; ++i)
      yield return amount;
}

Listing 3

In this case, we yield break when there is nothing to return. It does not have to be at the start of the iterator block function, for example it could happen if a condition was met within the main loop instead. In this example, data is small, but a more realistic example with a huge amount of data will reduce the memory, because we don’t create an array upfront.

.Net 4 allows us to write this with even fewer lines of code, using Enumerable (see Listing 4).

public static IEnumerable<double> 
   ValueAtTime (double t)
{
  Dictionary<double, double> data =
     new Dictionary<double, double> {
       { -1.0, 10.0 }, { 0.0, 20.0 },
       { 1.0, 30.0 }, { 2.0, 40.0 } };
  var dates = data.Where(a => a.Key < t);
  if (!dates.Any())
     return Enumerable.Empty< double >();
  return Enumerable.Repeat
     ( dates.OrderBy(a => a.Key).Last().Value,
       10000 );
}

Listing 4

Caveats

We have seen that iterator blocks can help with memory issues, however a couple of things need to be borne in mind. You need to take care where you place yield statements. In particular, you can’t yield from a try block with a catch block, or in a catch block or a finally block. In addition, the client code may never consume the whole iteration. This means if it contains a finally block, either explicitly or through a using statement, that may never be executed, unless the iterator block is wrapped in a using statement. Locks and threading can be dangerous too. See [Skeet] for more details.

Conclusion

It is surprisingly easy to run out of memory in .Net, but there are some simple things you can do to reduce memory usage. This article has shown how iterator blocks can reduce memory footprint without changing the client code. Significantly, if an object is large enough to end up on the LOH, swapping to iterator blocks where possible could stop your application falling over due to a System.OutOfMemory exception. There are many other ways to reduce memory that we have not considered here, such as using IDisposable , interning strings and remembering to state a capacity of a List<T> on construction, since calling Add will possibly do a reallocation, dumping the previous list, which could potentially be on the large object heap already, giving you two large objects with the price of one.