The Design of the .Net Compact Framework CLR, Part III: GC Heap Management

  • [アーティクル]

Here's Part III of the series on the design of the .Net Compact Framework CLR. Previous posts in this series provided an overview of how the CLR manages memory and described the basic design tenants of the JIT compilers:

Part I, Overview and Background

Part II, Jit Compiler Design Considerations

This post focuses on the design of the garbage collector from the perspective of how the GC heap is managed.

---------

Garbage collection is typically the topic that first comes to mind when discussing how memory is managed on the .Net platform. Not surprisingly, the Compact Framework’s garbage collector differs in many respects from its desktop counterpart due to the constraints in which it must run. Like most other subsystems within the Compact Framework CLR, the garbage collector has been designed to free all the memory it can when the amount of memory available on the device is low.

At a high level, the GC performs two basic functions: it allocates memory to hold instances of reference types and it collects the instances that are no longer needed.

Allocating Reference Types

As described in Part 1, the GC heap lives in the per-application 32 MB virtual address space. As with the JIT heap, the GC heap starts small and grows incrementally as more space is needed. However, there are two important differences in the way the GC heap grows when compared to the JIT heap: the GC heap grows in fixed increments, and it does not grow unbounded.
 

The growth increment for the GC heap is generally 64K. When a new 64K “segment” is created, allocations occur from that segment until no more room is available, at which point another segment is created. The Compact Framework GC allocates new segments using the standard Win32 API VirtualAlloc. Allocations within a segment are very fast. Performance tests on version 2 of the .Net Compact Framework show that the allocator can create up to 7.5 million instances of a small reference type per second. The allocator is so fast because the algorithm it uses is simple. A pointer is maintained to the “next available location” in the GC heap. To allocate space for a new instance, the allocator simply moves the pointer by the number of bytes needed to hold the object as shown in Figure 4:

Figure 4
Allocating a new reference type is simply a matter of adjusting the “next object” pointer.

While the default growth increment for the GC heap is 64K, the allocator will grow the heap in larger increments to accommodate objects greater than 64K. For example, if a program attempts to create an object that is 70k, the allocator will create a new segment of that size to store the larger object.
 

The GC heap grows in increments as described until it reaches 1 MB, at which point a collection begins (more on this later). The GC heap may continue to grow after that, but a collection occurs whenever 1MB of objects has been allocated since the last collection occurred.

Collecting Reference Types

Now that we’ve seen how the GC heap grows, let’s take a look at how it shrinks. Again, the ability to reduce the size of the GC heap under memory pressure is key to helping applications run well on memory constrained devices. In this section, we’ll look at what causes a collection to occur and when memory is freed and returned to the operating system.
 

There are several triggers that can cause a garbage collection to occur. As described, one of those triggers is the allocation of 1MB of managed objects. Other triggers include resource failures such as the inability to allocate more memory, create more window handles and so on. See An Overview of the .Net Compact Framework Garbage Collector for more details on what triggers a collection.
 

Memory is not freed and returned to the operating system every time a GC occurs. To understand when memory is freed from the operating system’s perspective, let’s take a closer look at what happens when the collector runs.

Unreferenced Objects

During every collection, the GC looks through the heap to find objects that are no longer referenced. The memory for these unneeded objects is freed in the sense that more space is now available in the GC heap. After freeing the unreferenced types, it’s possible that some number of 64K segments may be completely empty. If a segment is completely empty, and the GC still has 1MB of allocated segments, the empty 64K segments will be returned to the operating system by calling VirtualFree. With the exception of a “full” GC (described below), the collector always keeps a 1MB cache of 64K segments, even if some of them are empty. By caching segments in this way, performance is improved by reducing the number of calls to VirtualAlloc and VirtualFree.

Compacting the GC Heap

The GC may optionally compact the heap during a collection. When the heap reaches a state where it is sufficiently fragmented, the collector “compacts” the heap by moving all live objects close to each other. The primary goal in compacting the heap is to make larger blocks of memory available in which to allocate more objects. Figure 5 represents the contents of a GC heap before and after compaction.

Figure 5
The contents of a sample GC heap before and after compaction

As with the “simple” object collection, the GC will return empty 64K segments to the operating system as long as the 1MB segment cache is full.

A "Full" GC

Under the normal course of events, the GC works as described above: periodic collections are made after every 1MB of allocations, the heap is compacted if it gets too fragmented, and empty segments are returned to the operating system as long as the collector’s 1 MB cache is full.

There three scenarios, however, in which more drastic steps are taken to make more memory available. These scenarios align exactly with the times at which the JIT reduces the size of it’s heap as described in Part II: when a failure to allocate memory or other resource occurs, when an application is moved to the background, or when an application receives the WM_HIBERNATE message from the operating system. At these times, the GC will hot hold onto its 1MB segment cache. It will collect all unreferenced objects, compact the heap, and free any memory it can.

Pulling it All Together

Now that we’ve seen how the GC allocates and frees memory, let’s look at the size of the GC heap over the lifetime of an application.

Figure 6

The size of the GC heap over the lifetime of an application.

The graph in Figure 6 tracks two pieces of data. The yellow line shows the cumulative number of bytes the garbage collector has been asked to allocate over the lifetime of the application. This number will continue to grow without bounds as long as the application continues to allocate new objects.
 

The blue line in Figure 6 shows the size of the GC heap over time. There are several points worth noting. First, when the application starts and continues to run, we see the size of the GC heap growing in a consistent stair-step fashion. Each “step” in the graph corresponds to a newly created 64K GC segment. Second, we can see that the blue line levels off after some time. As you’d expect from the earlier description of the allocation and collection algorithms, the point at which the size of the heap flattens out is at 1MB. Next, you can see a dramatic drop in the size of the heap. In this case, the drop occurs when I moved the application I was monitoring into the background. After the application switches to the foreground, we start to see the heap growing in 64K chunks again.
 

This series of posts has now covered the basics of how the .Net Compact Framework managed memory, and the design decisions made while building the JIT compilers and the garbage collector. In my next post, I’ll look at how the need to run efficiently on memory constrained devices has affected the design of the CLR’s class loader.

This posting is provided "AS IS" with no warranties, and confers no rights.

Comments