Running with Code Like with scissors, only more dangerous

7Aug/082

Speedy C#, Part 2: Optimizing Memory Allocations – Pooling and Reusing Objects

Posted by Rob

In C#, Visual Basic .NET, C++/CLI, J# - the list goes on - we're freed from having to worry about our memory management.  Objects take care of themselves, and when the CLR garbage collector detects that an object is no longer in use, it frees the associated memory.  That doesn't mean that we should run around allocating and deallocating objects all willy-nilly; in fact, since we have less control over memory, we arguably have the opportunity to be more careful with the way we use high-frequency objects.

Memory Regions in .NET

In .NET, and generally in most programming, we can think of two places in which we can access memory: the stack and the heap.  We can think of Stack memory as temporary workspace, or scratch space; when we leave a function, all of our stack goes away.  Way, way down in the machine architecture, the stack also stores the return addresses of functions.  The stack also stores function parameters.  It's generally very orderly, inexpensive, but its volatile nature makes it a poor candidate for long-term storage.  In .NET, all types that derive from the ValueType class are stored on the stack unless they are boxed into an object reference; this includes types defined with the struct and enum keywords, as well as all of the primitive types except string (including int, double, and bool).

Heap memory is another matter.  The heap is a region of memory reserved for the use of the program and is intended to store objects that aren't quite so transient.  This might be something like a database connection, a file or buffer, or a window.

The Enemy: Fragmentation

Over time, objects are allocated and eventually released, and because there's not really any rhyme or reason, the heap becomes chaotic.  Allocations grab the first free block that's large enough (sometimes larger than necessary) and hold onto it until they go into the abyss.  This leads to fragmentation - all the free memory must be tracked somehow, and here's the real killer: contiguous blocks of free memory may not always be recognized as such.  Check this out: let's say we have a heap allocated at memory location 0x4000 that is 32 bytes wide:

An un-used heap

(Yes, my awesome artwork was done with none other than Excel!)

Suppose we allocate an 8-byte object and another 8-byte object, then a 16-byte object.  The first is in red, the second in orange, and the third in gray:

The heap after it was filled

Now I'll free the first and the third objects; we'll have 24 bytes of total free memory:

A fragmented heap

Either we need to keep track of every little piece of memory, which might be the fastest algorithm for releasing but slow for allocating (not to mention potentially VERY wasteful), or try to come up with another solution.  This type of memory fragmentation is referred to as external fragmentation.

The Garbage Collector and Compaction

The garbage collector has two components: a reference counter and a compaction engine.  The reference counter is responsible for determining when objects no longer have references to them; this frees programmers from having to explicitly destroy objects (as is the practice in C++ with the delete operator, or in C with the free function).  A lazy thread is then able to release and compact memory as needed, avoiding much of the overhead of external fragmentation and also allowing unused memory to be reclaimed.  The garbage collector in .NET is generational; it checks the newest objects first (what are called "gen-0"), and if the newest objects are still in use, they get moved to gen-1.  If the memory pressure requires, gen-1 objects are evaluated, and if they are still in use, they get moved to gen-2.  Gen-2 objects are considered long-lasting, and are only checked when memory pressure is severe.

Let's go back to our heap example; supposing I had an 8-byte, another 8-byte, and a 12-byte allocation, here's my heap graph:

A new heap

Object 1 (in red) has gone out of scope, but objects 2 and three are sticking around.  Using normal memory freeing rules, the largest object that could be allocated would still only be 8 bytes, because that would be the largest contiguous free space.  However, using .NET's compacting garbage collector, we could expect something along these lines:

A compacted heap graph

Here we can see we've dealt with the problem of external fragmentation by compacting the heap.  This convenience doesn't come without a cost, though; while the garbage collector performed the compaction, all of your application threads were suspended.  The GC can't guarantee object integrity if memory is getting abused during a garbage collection!

Preventing Compaction: Stop Killing off Objects!

Object pooling is a pattern to use that allows objects to be reused rather than allocated and deallocated, which helps to prevent heap fragmentation as well as costly GC compactions.  A pool can be thought of as an object factory; in essence, the most rudimentary pool could look like this:

   1: public class Pool<T> where T : new()
   2: {
   3:     private Stack<T> _items = new Stack<T>();
   4:     private object _sync = new object(); 
   5:  
   6:     public T Get()
   7:     {
   8:         lock (_sync)
   9:         {
  10:             if (_items.Count == 0)
  11:             {
  12:                 return new T();
  13:             }
  14:             else
  15:             {
  16:                 return _items.Pop();
  17:             }
  18:         }
  19:     }
  20:  
  21:     public void Free(T item)
  22:     {
  23:         lock (_sync)
  24:         {
  25:             _items.Push(item);
  26:         }
  27:     }
  28: }

Here, objects are created entirely on-demand and, when freed, are stored in a stack.  The reason we want to use a Stack is the performance characteristic of adding and removing objects; operations are always performed at the end of the list, which makes it highly efficient to add or remove items.  If possible, it may be prudent to pre-create a number of objects for use throughout the lifetime of your application. 

Here's an example: the project I've been discussing lately uses a pool of byte arrays to handle incoming network messages received and sent via a Socket.  When pooling is enabled, over the course of the application's lifetime, there were 17 Gen-0 collections, 5 Gen-1 collections, and 3 Gen-2 collections; a total of 270 byte[] instances were allocated, of which 44 were eligible for pooling and were pooled.  When pooling is disabled, there were 22 Gen-0 collections, 5 Gen-1 collections, and 3 Gen-2 collections; a total of 11,660 byte[] instances were allocated, of which approximately 10,900 were eligible for pooling.  That's a lot of memory!

Summary - When and Why

Object pooling is a powerful optimization technique, and if you're already using factory patterns it shouldn't be terribly foreign to you.  The .NET Framework includes the ThreadPool class as part of System.Threading.  Other objects you might consider pooling are database connections, any expensive links to unmanaged code, or anything that needs to be allocated frequently and can then be thrown away.  In my example, byte arrays are exceptionally good for this because they can be overwritten easily.

Further Reading

The "Speedy C#" Series:

29Jan/080

The Madness of Remoting

Posted by Rob

My latest project has been pretty much my first real distributed application - it involves securely storing and encrypting credit card data in a system that makes it nigh impossible to access the information.  It's actually been really fun, delving into the depths of secure programming and trying to come up with security measures to thwart perceived avenues of attack against the system.

Part of the way that this system works is by encrypting sensitive data as soon as it arrives to the application servers.  However, to prevent recovery of the data should the application servers be compromised, we chose to use a public key infrastructure system - a server elsewhere on the network issues public/private key pairs, and only the public key is stored on the application server.  The private key never actually leaves that server, and specialized trust relationships are configured so that when decryption needs to take place, it happens on the server where the private key was stored, and data exchange requires a secure channel.

The fun part about figuring out how all of this was going to work together was determining where the system lived.  One of the kicks about the application is that the encryption keys aren't allowed to be stored in "plain text" anywhere - they themselves are encrypted, and the encryption key we use to encrypt those is absolutely forbidden from being stored - we keep it in memory throughout the lifetime of the application (it is backed up with a physical backup mechanism that involves division of responsibility).

Well, with the requirement that the key encrypting key could not just disappear, I knew that we couldn't use ASP.NET to manage it - we'd have a catastrophe in the event that the process recycled.  The obvious solution was to use a Windows Service.  But the only way for a Windows Service to communicate with the outside world (in .NET anyway) is via remoting.

I'd played with remoting a small bit in the past - an app I wrote used remoting to activate objects in another AppDomain so that I could inspect the object for supported interfaces - as far as plugin systems go, it was one of my more in-depth ones.  And I'd achieved my MCTS credential in distributed applications.  But I really had (and I still really don't have) no idea what I was headed for.

Because I need to manage object lifetime myself, I am unable to use the automatic .NET Remoting configuration scheme; I need to make sure that the server has access to certain services as soon as it starts and until it ends.  I don't have the luxury of client-activated objects, even singleton ones.  So I need to set up the remoting infrastructure myself; I defined a series of service interfaces in a DLL that will be accessible from both the client and server applications, and then implement the interfaces in the server.  Seems straightforward enough.  Internal to the server-side, I also created an IService interface that defined Start() and Stop() methods - a series of objects that I could control from within the Windows Service and also work with from a factory-style utility class.

Here's sample code for the Start and Stop methods:

   1:   
   2:          public void Start()
   3:          {
   4:              m_wellKnown = RemotingServices.Marshal(this, string.Format("{0}.svc", m_config.Name), typeof(IEncryptionKeyGeneratorService));
   5:          }
   6:   
   7:          public void Stop()
   8:          {
   9:              if (!RemotingServices.Disconnect(this))
  10:                  throw new InvalidOperationException("Error disconnecting this object.");
  11:              m_wellKnown = null;
  12:          }

In this example, the ObjRef specified by the m_wellKnown field is initialized by the call to RemotingServices.Marshal.  The object actually marshals itself, but limits the type hierarchy by specifying exactly which interface it is casting to.  My current class, EncryptionKeyGeneratorService, inherits MarshalByRefObject and implements IEncryptionKeyGeneratorService and IService.  IEncryptionKeyGeneratorService does not inherit from IService; otherwise I would risk allowing a cast to IService, which could compromise the integrity of the application.

The part that I don't get, and really the whole purpose of this, is to explain why the call to RemotingServices.Disconnect(this) fails.

I always look at it and wonder, "Why did I get an InvalidOperationException?"  And then I realize: it's because I threw it.

The RemotingServices class is already obscure enough in that calls to Marshal are paired with calls to Disconnect, and that calls to Connect are paired with calls to Unmarshal (but not always... or something).  What I don't understand is why Disconnect() would ever return false.  It's pretty clear: I'm telling you to stop acting as an object that can be accessed elsewhere.  You're not a two-year-old child; stop telling me no.

The really scary part is that I can close out my client application altogether and still have RemotingServices be stubborn.

WHY?