Foundations of Programming – pt 7 – Back to Basics: Memory

I’m back. Readers can expect a quality free pdf ebook once the series is complete (end of may at the latest hopefully).

Try as they might, modern programming language can’t fully abstract fundamental aspects of computer systems. This is made evident by the various exceptions thrown by high level languages. For example, it’s safe to assume that you’ve likely faced the following .NET exceptions: NullReferneceException, OutOfMemoryException, StackOverflowException and ThreadAbortException. As important as it is for developers to embrace various high level patterns and techniques, it’s equally important to understand the ecosystem in which your program runs. Looking past the layers provided by the C# (or VB.NET) compiler, the CLR and the operating system, we find memory. All programs make extensive use of system memory and interact with it in marvelous ways, it’s difficult to be a good programmer without understanding this fundamental interaction.

Much of the confusion about memory stems from the fact that C# and VB.NET are managed languages and that the CLR provides automatic garbage collection. This has caused many developers to erroneously assume that they need not worry about memory.

Memory Allocation

In .NET, as with most languages, every variable you define is either stored on the stack or in the heap. These are two separate spaces allocated in system memory which serve a distinct, yet complimentary purpose. What goes where is predetermined: value types go on the stack, while all reference types go on the heap. In other words, all the system types, such as char, int, long, byte, enum and any structures (either defined in .NET or defined by you) go on the stack. The only exception to this rule are value types belonging to reference types – for example the Id property of a User class goes on the heap along with the instance of the User class itself.

The Stack

Although we’re used to magical garbage collection, values on the stack are automatically managed even in a garbage collectionless world (such as C). That’s because whenever you enter a new scope (such as a method or an if statement) values are pushed onto the stack and when you exit the stack the values are popped off. This is why a stack is synonymous with a LIFO – last-in first-out. You can think of it this way: whenever you create a new scope, say a method, a marker is placed on the stack and values are added to it as needed. When you leave that scope, all values are popped off up to and including the method marker. This works with any level of nesting.

Until we look at the interaction between the heap and the stack, the only real way to get in trouble with the stack is with the StackOverflowException. This means that you’ve used up all the space available on the stack. 99.9% of the time, this indicates an endless recursive call (a function which calls itself ad infinitum). In theory it could be caused by a very very poorly designed system, though I’ve never seen a non-recursive call use up all the space on the stack.

The Heap

Memory allocation on the heap isn’t as straightforward as on the stack. Most heap-based memory allocation occurs whenever we create a new object. The compiler figures out how much memory we’ll need (which isn’t that difficult, even for objects with nested references), carves up an appropriate chunk of memory and returns a pointer to the allocated memory (more on this in moments). The simplest example is a string, if each character in a string takes up 2 bytes, and we create a new string with the value of “Hello World”, then the CLR will need to allocate 22 bytes (11×2) plus whatever overhead is needed.

Speaking of strings, you’ve no doubt heard that string are immutable – that is, once you’ve declared a string and assigned it a value, if you modify that string (by changing its value, or concatenating another string onto it), then a new string is created. This can actually have negative performance implications, and so the general recommendation is to use a StringBuilder for any significant string manipulation. The truth though is that any object stored on the heap is immutable, and any changes to the underlying size will require new allocation. The StringBuilder, along with some collections, partially get around this by using internal buffers. Once the buffer fills up though, the same reallocation occurs and some type of growth algorithm is used to determined the new size (the simplest being oldSize * 2). Whenever possible it’s a good idea to specify the initial capacity of such objects in order to avoid this type of reallocation (the constructor for both the StringBuilder and the ArrayList (amongst many other collections) allow you to specify an initial capacity).

Garbage collecting the heap is a non-trivial task. Unlike the stack where the last scope can simply be popped off, objects in the heap aren’t local to a given scope. Instead, most are deeply nested references of other referenced objects. In languages such as C, whenever a programmer causes memory to be allocated on the heap, he or she must also make sure to remove it from the heap when he’s finished with it. In managed languages, the runtime takes care of cleaning up resources (.NET uses a Generational Garbage Collector which is briefly described on Wikipedia).

There are a lot of nasty issues that can sting developers while working with the heap. Memory leaks aren’t only possible but very common, memory fragmentation can cause all types of havoc, and various performance issues can arise due to strange allocation behavior or interaction with unmanaged code (which.NET does a lot under the covers).

Pointers

For many developers, learning pointers in school was a painful experience. They represent the very real indirection which exists between code and hardware. Many more developers have never had the experience of learning them – having jumped into programming directly from a language which didn’t expose them directly. The truth though is that anyone claiming that C# of Java are pointerless languages is simply wrong. Since pointers are the mechanism by which all languages manage values on the heap, it seems rather silly not to understand how they are used.

Pointers represent the nexus of a system’s memory model – that is, pointers are the mechanism by which the stack and the heap work together to provide the memory subsystem required by your program. As we discussed earlier, whenever you instantiate a new object, .NET allocates a chunk of memory on the heap and returns a pointer to the start of this memory block. This is all a pointer is: the starting address for the block of memory containing an object. This address is really nothing more than an unique number, generally represented in hexadecimal format. Therefore, a pointer is nothing more than a unique number that tells .NET where the actual object is in memory. When you assign a reference type to a variable, your variable is actually a pointer to the object. This indirection is transparent in Java or .NET, but not in C or C++ where you can manipulate the memory address directly via pointer arithmetic. In C or C++ you could take a pointer and add 1 to it, hence arbitrarily changing where it points to (and likely crashing your program because of it).

Where it gets interesting is where the pointer is actually stored. They actually follow the same rules outlined above: as integers they are stored on the stack – unless of course they are part of a reference object and then they are on the heap with the rest of their object. It might not be clear yet, but this means that ultimately, all heap objects are rooted on the stack (possibly through numerous levels of references). Let’s first look at a simple example.

static void Main(string[] args)
{
  int x = 5;
  string y = "codebetter.com";
}

From the above code, we’ll end up with 2 values on the stack, the integer 5 and the pointer to our string, as well as the actual string on the heap. Here’s a graphical representation:

Stack and Heap Figure 1

When we exit our main function (forget the fact that the program will stop), our stack pops off all local values, meaning both the x and y values are lost. This is significant because the memory allocated on the heap still contains our string, but we’ve lost all references to it (there’s no pointer pointing back to it). In C or C++ this results in a memory leak – without a reference to our heap address we can’t free up the memory. In C# or Java, our trusty garbage collector will detect the unreferenced object and free it up.

We’ll look at a more complex examples, but asside from having more arrows, it’s basically the same.

public class Employee
{
  private int _employeeId;
  private Employee _manager;
  public int EmployeeId
  {
    get { return _employeeId; }
    set { _employeeId = value; }
  }
  public Employee Manager
  {
    get { return _manager; }
    set { _manager = value; }
  }
  public Employee(int employeeId)
  {
    _employeeId = employeeId;
  }
}
public class Test
{
  private Employee _subordinate;
  void DoSomething(
  {
    Employee boss = new Employee(1);
    _subordinate = new Employee(2);
    _subordinate.Manager = _boss;
  }
}

Stack and Heap Figure 2

Interestingly, when we leave our method, the boss variable will pop off the stack, but the subordinate, which is defined in a parent scope, won’t. This means the garbage collector won’t have anything to clean-up because both heap values will still be referenced (one directly from the stack, and the other indirectly from the stack through a referenced object).

As you can see, pointers most definitely play a significant part in both C# and VB.NET. Since pointer arithmetic isn’t available in either language, pointers are greatly simplified and hopefully easily understood.

Memory Model in Practice

We’ll now look at the actual impact this has on our applications. Keep in mind though that understanding the memory model in play won’t only help you avoid pitfalls, but it will also help you write better applications.

Boxing

Boxing occurs when a value types (stored on the stack) is coerced onto the heap. Unboxing happens when these value types are placed back onto the stack. The simplest way to coerce a value type, such as an integer, onto the heap is by casting it:

int x = 5;
object y = x;

A more common scenario where boxing occurs is when you supply a value type to a method that accepts an object. This was common with collections in .NET 1.x before the introduction of generics. The non-generic collection classes mostly work with the object type, so the following code results in boxing and unboxing:

ArrayList userIds = new ArrayList(2);
userIds.Add(1);
userIds.Add(2);
int firstId = (int)userIds[0];

The real benefit of generics is the increase in type-safety, but they also address the performance penalty associated with boxing. In most cases you wouldn’t notice this penalty, but in some situations, such as large collections, you very well could. Regardless of whether or not it’s something you ought to actually concern yourself with, boxing is a prime example of how the underlying memory system can have an impact on your application.

ByRef

Without a good understanding of pointers, it’s virtually impossible to understand passing a value by reference and by value. Developers generally understand the implication of passing a value type, such as an integer, by reference, but few understand why you’d want to pass a reference by reference. ByRef and ByVal affect reference and value types the same – provided you understand that they always work against the underlying value (which in the case of a reference type means they work against the pointer and not the value). Using ByRef is the only common situation where .NET won’t automatically resolve the pointer indirection (passing by reference or as an output parameter isn’t allowed in Java).

First we’ll look at how ByVal/ByRef affects value types. Given the following code:

public static void Main()
{
  int counter1 = 0;
  SeedCounter(counter1);
  Console.WriteLine(counter1);

  int counter2 = 0;
  SeedCounter(ref counter2);
  Console.WriteLine(counter2);
}
private static void SeedCounter(int counter)
{
  counter = 1;
}
private static void SeedCounter(ref int counter)
{
  counter = 1;
}

We can expect an output of 0 proceeded by 1. The first call does not by pass counter1 by reference, meaning a copy of counter1 is passed into SeedCounter and changes made within are local to the function. In other words, we’re taking the value on the stack and duplicating it onto another stack location.

In the second case we’re actually passing the value by reference which means no copy is created and changes aren’t localized to the SeedCounter function.

The behavior with reference types is the exact same, although it might not appear so at first. We’ll look at two examples. The first one uses a PayManagement class to change the properties of an Employee. In the code below we see that we have two employees and in both cases we’re given them a $2000 raise. The only difference is that one passes the employee by reference while the other is passed by value. Can you guess the output?

public class Employee
{
  private int _salary;
  public int Salary
  {
    get {return _salary;}
    set {_salary = value;}
  }
  public Employee(int startingSalary)
  {
    _salary = startingSalary;
  }
}
public class PayManagement
{
  public static void GiveRaise(Employee employee, int raise)
  {
    employee.Salary += raise;
  }
  public static void GiveRaise(ref Employee employee, int raise)
  {
    employee.Salary += raise;
  }
}
public static void Main()
{
  Employee employee1 = new Employee(10000);
  PayManagement.GiveRaise(employee1, 2000);
  Console.WriteLine(employee1.Salary);

  Employee employee2 = new Employee(10000);
  PayManagement.GiveRaise(ref employee2, 2000);
  Console.WriteLine(employee2.Salary);
}

In both cases, the output is 12000. At first glance, this seems different than what we just saw with value types. What’s happening is that passing a reference type by value does indeed pass a copy of the value, but not the heap value. Instead, we’re passing a copy of our pointer. And since a pointer and a copy of the pointer point to the same memory on the heap, a change made by one is reflected in the other.

When you pass a reference type by reference, you’re passing the actual pointer as opposed to a copy of the pointer. This begs the question, when would we ever pass a reference type by reference? The only reason to pass by reference is when you want to modify the pointer itself – as in where it points to. This can actually result in nasty side effects – which is why it’s a good thing functions wanting to do so must specifically specify that they want the parameter passed by reference. Let’s look at our second example.

public class Employee
{
  private int _salary;
  public int Salary
  {
    get {return _salary;}
    set {_salary = value;}
  }
  public Employee(int startingSalary)
  {
    _salary = startingSalary;
  }
}
public class PayManagement
{
  public static void Terminate(Employee employee)
  {
    employee = null;
  }
  public static void Terminate(ref Employee employee)
  {
    employee = null;
  }
}
public static void Main()
{
  Employee employee1 = new Employee(10000);
  PayManagement.Terminate(employee1);
  Console.WriteLine(employee1.Salary);

  Employee employee2 = new Employee(10000);
  PayManagement.Terminate(ref employee2);
  Console.WriteLine(employee2.Salary);
}

Try to figure out what will happen and why. I’ll give you a hint: an exception will be thrown. If you guessed that the call to employee1.Salary outputted 10000 while the 2nd one threw a NullReferenceException then you’re right. In the first case we’re simply setting a copy of the original pointer to null – it has no impact whatsoever on what employee1 is pointing to. In the second case, we aren’t passing a copy but the same stack value used by employee2. Thus setting the employee to null is the same as writing employee2 = null;.

It’s quite uncommon to want to change the address pointed to by a variable from within a separate method – which is why the only time you’re likely to see a reference type passed by value is when you want to return multiple values from a function call (in which case you’re better off using an out parameter, or using a purer OO approach). The above example truly highlights the dangers of playing in an environment whose rules aren’t fully understood.

Managed Memory Leaks

We already saw an example of what a memory leak looks like in C. Basically, if C# didn’t have a garbage collector, the following code would leak:

private void DoSomething()
{
  string name = "dune";
}

Our stack value (a pointer) will be popped off, and with it will go the only way we have to reference the memory created to hold our string. Leaving us with no method of freeing it up. This isn’t a problem in .NET because it does have a garbage collector which tracks unreferenced memory and frees it. However, a type of memory leak is still possible if you hold on to references indefinitely. This is common in large applications with deeply nested references. They can be hard to identify because the leak might be very small and your application might not run for long enough – even ASP.NET applications tend to be recycled fairly often.

Ultimately when your program terminates the operating system will reclaim all memory, leaked or otherwise. However, if you start seeing OutOfMemoryException and aren’t dealing with abnormally large data, there’s a good chance you have a memory leak. .NET ships with tools to help you out, but you’ll likely want to take advantage of a commercial memory profiler such as dotTrace or ANTS Profiler. When hunting for memory leaks you’ll be looking for your leaked object (which is pretty easy to find by taking 2 snapshots of your memory and comparing them), tracing through all the objects which still hold a reference to it and correcting the issue.

Fragmentation

Another common cause for OutOfMemoryException has to do with memory fragmentation. When memory is allocated on the heap it’s always a continuous block. This means that the available memory must be scanned for a large enough chunk. As your program runs its course, the heap becomes increasingly fragmented (like your hard drive) and you might end up with plenty of space, but spread out in a manner which makes it unusable. Under normal circumstances, the garbage collector will compact the heap as it’s freeing memory. As it compacts memory, addresses of objects change, and .NET makes sure to update all your references accordingly. Sometimes though, .NET can’t move an object: namely when the object is pinned to a specific memory address.

Pinning

Pinning occurs when an object is locked to a specific address on the heap. Pinned memory cannot be compacted by the garbage collector resulting in fragmentation. Why do values get pinned? The most common cause is because your code is interacting with unmanaged code. When the .NET garbage collector compacts the heap, it updates all references in managed code, but it has no way to jump into unmanaged code and do the same. Therefore, before interoping it must first pin objects in memory. Since many methods within the .NET framework rely on unmanaged code, pinning can happen without you knowing about it (the scenario I’m most familiar with are the .NET Socket classes which rely on unmanaged implementations and pin buffers).

A common way around this type of pinning is to declare large objects which don’t cause as much fragmentation as many small ones (this is even more true considering large objects are placed in a special heap (called the Large Object Heap (LOH) which isn’t compacted at all)). For example, rather than creating hundreds of 4KB buffers, you can create 1 large buffer and assign chunks of it yourself. For an example as well as more information on pinning, I suggest you read Greg Young’s advanced post on pinning and asynchronous sockets.

There’s a second reason why an object might be pinned – when you explicitly make it happen. In C# (not in VB.NET) if you compile your assembly with the unsafe option you can pin an object via the fixed statement. While extensive pinning can cause memory pressures on the system, judicial use of the fixed statement can greatly improve performance. Why? Because a pinned object can be manipulated directly with pointer arithmetic – this isn’t possible if the object isn’t pinned because the garbage collector might reallocate your object somewhere else in memory.

Take for example this efficient ASCII string to integer conversion which runs over 6 times faster than using int.Parse.

public unsafe static int Parse(string stringToConvert)
{
  int value = 0;
  int length = stringToConvert.Length;
  fixed(char* characters = stringToConvert)
  {
    for (int i = 0; i &lgt; length; ++i)
    {
      value = 10 * value + (characters[ i ] - 48);
    
    }
  }
  return value;
}

Unless you’re doing something abnormal, there should never be a need to mark your assembly as unsafe and take advantage of the fixed statement. The above code will easily crash (pass null as the string and see what happens), isn’t nearly as feature rich as int.Parse, and in the scale of things is extremely risky while providing no benefits.

Setting things to null

So, should you set your reference types to null when you’re done with them? Of course not. Once a variable falls out of scope, it’s popped of the stack and the reference is removed. If you can’t wait for the scope to exit, you likely need to refactor your code.

Conclusion

Stacks, heaps and pointers can seem overwhelming at first. Within the context of managed languages though, there isn’t really much to it. The benefits of understanding these concepts are tangible in day to day programming, and invaluable when unexpected behavior occurs. You can either be the programmer who causes weird NullReferenceExceptions and OutOfMemoryExceptions, or the one that fixes them.

This entry was posted in Foundations. Bookmark the permalink. Follow any comments here with the RSS feed for this post.

16 Responses to Foundations of Programming – pt 7 – Back to Basics: Memory

  1. Ishmael says:

    You’re right, the example is in C#. Equivalent code in C/C++could very well use malloc or new but since C/C++ code isn’t provided in the article we must imagine what you meant ourselves. The root of my misunderstanding is I translated the C# into the C/C++ of my comment above and then was affronted by the sentence “In C or C++ this results in a memory leak …”.

    If I forget the code example and just interpret the sentence which so offended me in the context of the diagram and immediately preceding sentence then it is correct.

    It is only a small misunderstanding in an otherwise excellent article. It would be impossible to remove all ambiguity for all readers anyway.

    Regards.

  2. karl says:

    Ishmael:
    You’re right. Although I didn’t give that example in c/c++, I gave it in C# and said the equivillant in C would leak. In my mind, I was thinking of a malloc call (since C doesn’t have strings), which _would_ have resulted in a leak. Using a C++ string, or a using fixed allocation in C (which I agree would be the most direct comparison), wouldn’t leak either.

  3. Ishmael says:

    The code:

    string y = “codebetter.com”;

    will not result in a memory leak in C++, contrary to what you stated in the ‘Pointers’ section above. The string object will be placed on the stack. The object may internally manage the string’s data on the heap but when the scope is exited the destructor will clean it up without any need for manual intervention.

    The C version of the code:

    char * y = “codebetter.com”;

    will not result in a memory leak either, I forget the reason why.

    The section “Managed Memory Leaks”, using a similar example of a string object, implies that unmanaged languages would leak the heap data when leaving the scope. It may be true that without a garbage collector the memory would be leaked in C# but it is not the case that an unmanaged language like C++ would leak the string’s data.

    It is common when discussing a new technology to attribute disadvantages to the older technology that don’t actually apply. This should be resisted.

    Otherwise, a good article and overview of memory in .NET. I think with a slightly better choice of examples and a cleanup it could also make the point about the benefits of garbage collection without containing inaccuracies about unmanaged languages.

    Cheers!

  4. o.s. says:

    Thanks for the reply Karl. Back when I was in college I asked this very same question to my professor in my Data Structures with C++ class and he thought that I was an absolute boob for even asking. At first site the distinction really isn’t super clear (in terms of just accessing memory) especially in C++ when the operator used differs from & (reference) and -> (pointer). I’ll definetely be looking out for more of your posts they’re quite good.

  5. karl says:

    o.s.:
    I don’t think the terms are particuarly well defined or set in stone. But it’s generally accepted that a reference is simply a pointer who’s behavior cannot be unexpected. That it, it will always point to a valid reference or to some default value (null).

  6. o.s. says:

    Karl or anyone else I was wondering what’s the biggest difference between a reference and a pointer? From my understanding they both hold memory addresses and that the ponter can allow pointer arithmetic and the reference can’t but is this really all or am I wrong?

  7. vkelman says:

    Karl, one more thing. Isn’t “which is why the only time you’re likely to see a reference type passed by value is when you want to return multiple values from a function call” should be “which is why the only time you’re likely to see a reference type passed by *reference* is when you want to return multiple values from a function call” ?

    Thank you for your articles. They were among the triggers for me to start to learn about architectural things like DDD, N-Tier, DI, etc. It’s hard but exciting.

  8. karl says:

    vkelman: Yes I did. I’ll clean up the wording of it in the PDF version. I knew at the time of writing it that it was somewhat ambiguous.

  9. vkelman says:

    Karl, you said, “The truth though is that any object stored on the heap is immutable, and any changes to the underlying size will require new allocation.” Did you mean that a size of any object located on heap is immutable, while its internal state is mutable?

  10. Very well written article! I have used your article in a class I’m teaching. Their response was very positive. Your style of writing is very accessible and easy, you should try your hand at writing a book!

  11. Dan Martin says:

    Another awesome article. I look forward to the next.

  12. karl says:

    Good idea greg, I’ve included it in the ebook version

  13. What About Thad? says:

    This is the best article in the series, which itself has been great. I knew the basics of the stack, heap, pointers, etc., but didn’t know the details to the extent they are illuminated here.

  14. Dave Laribee says:

    Great post, Karl. This one’s a lifer!

  15. Marshal says:

    Excellent!, looking forward for new posts!

  16. Greg says:

    awesome post as usual Karl.

    it might be worth writing up a side note for the most common managed leak I see (leaks through delegates/events as they hold a strong handle to the callee)