Full Text Search: The Key to Better Natural Language Queries for NoSQL in Node.js
Programmers new to C# can encounter less than ideal performance and even unexpected results due to boxing and unboxing of value types. This article explains the concept of boxing and unboxing and how its subtle behavior, if not fully understood, can adversely affect application performance and cause unexpected, difficult-to-locate bugs.
What Are Value Types?
Value types are lightweight objects that are allocated on the current thread's stack. (An exception to this rule occurs when a value type is allocated as an element of an array.) All primitive types (byte, char, int, long, and so on) and structures are value-based types derived from System.ValueType. Because value types are stack-based, they can be created and accessed more efficiently than reference types, which are heap-based and must be accessed by using references.
This is an oversimplification of what actually occurs when a value type instance is boxed or unboxed. Let's explore in greater detail how these operations are actually performed.
How Does Boxing Really Work?
When an instance of a value type is converted to its base "object" type or to an interface it implements, the CLR (Common Language Runtime) allocates enough memory from the managed heap to hold a copy of the value type instance along with the necessary internal data required to create a valid reference object. The CLR then copies the value type instance to the newly allocated area in the managed heap. The following code fragment demonstrates boxing of a value type.
In this code fragment, the structure myRect is implicitly converted to an instance of type "object" when assigned to the variable obj.
Let's take a look at the IL assembler code emitted by the C# compiler.
The first instruction loads a managed pointer to myRect on the evaluation stack in preparation for initialization. Using the managed pointer, the next instruction (initobj) initializes myRect to all zeroes.
Following initialization, myRect, located in local variable slot 0, is loaded on the stack. The box instruction pops myRect off the stack, creates a new instance of myRect as a reference object on the managed heap, and then pushes the resulting reference on the stack. Finally, the reference is stored in local variable slot 1.
(Note: Every method has an internal table used for temporarily storing local variables. This is known as the local variable table. Each entry or slot is identified by a zero-based ordinal number, and is associated with a static type -- static in the sense that the type is set at compile-time and does not change during runtime execution.)
Clearly, boxing operations result in significant overhead attributed to heap allocation and copying of the value type's state. Now let's take a look at how unboxing operations work.
How Does Unboxing Really Work?
When an instance of an "object" type or interface, created as a result of boxing, is explicitly converted back to its true value type, the CLR merely returns a managed pointer to the value type instance contained within the reference object. The "unboxed" instance is typically copied to a stack-based instance through an assignment operation. The following code fragment demonstrates unboxing of a value type.
Here, we are explicitly converting the variable obj back to the structure myRect.
Now, let's look at the IL assembler code emitted by the C# compiler.
The first instruction loads a reference to the boxed value type on the stack. The unbox instruction pops the reference off the stack and pushes a managed pointer to the object's contained Rectangle instance on the stack. Next, the ldobj instruction pops the managed pointer off the stack and, using the managed pointer, copies the Rectangle instance on the stack. Finally, the Rectangle copy is stored in local variable slot 0 (the assignment to myRect.)
Note that the boxed value type still exists on the managed heap. This heap object will continue to exist until garbage collection reclaims the space (after no further references to the object exists).
From the preceding example, it's clear that unboxing does not incur the same cost that boxing does. However, in many cases, an assignment operation is associated with the conversion. This assignment causes a copy operation to be performed.
Now that you understand what boxing and unboxing is, let's take a look at the subtle problems that can arise from this behavior.
All Is Not As It Seems
It's not always obvious or intuitive when boxing or unboxing occurs. Nor are the potential side effects readily understood. You may encounter a situation where updating an instance of a value type does not actually update the instance at all. You're probably wondering what I'm talking about. Let me use the following section of code to explain.
In this example, an ArrayList is created to hold five items. The first loop creates and adds five Rectangle instances, each with a width and height of 100 pixels, to the ArrayList instance. The second loop increases the width and height of each Rectangle instance by an additional 400 pixels. Finally, the last loop merely prints out the values of each Rectangle instance.
This code appears quite trivial at first glance. However, let's take a look at the output.
The widths and heights of all the Rectangle instances are still 100 pixels! What happened to our updates? To answer this question, we need to look at the IL assembler code of the second loop.
Statement IL_0035 unboxes the reference object retrieved from the ArrayList by placing a managed pointer to the contained Rectangle instance on the evaluation stack. The next statement, IL_003a, pops the managed pointer off the stack, copies the Rectangle instance it points to, and pushes this copy on the stack.
From this point on, we are working with a temporary, stack-based copy of the Rectangle instance rather than the heap-based instance referred to by the ArrayList. As we look at the remainder of the IL assembler code, you'll notice that the boxed Rectangle instance never gets updated with the stack-based copy. Therefore, when we print the contents of the ArrayList we see only their original values.
This example demonstrated how boxing and unboxing can cause subtle programming errors that are difficult to locate (even when using a debugger). Next, we look at how boxing and unboxing can affect application performance.
It's not always obvious to those new to C# where boxing may be occurring in their applications. Nor is it obvious that these boxing operations may be affecting their application's performance.
The FCL (Framework Class Library) has many types with methods and properties that can cause implicit boxing to occur when used with value types. You can determine which methods and properties will cause boxing of value types by looking at their signatures in the Visual Studio .NET documentation. If a method takes an argument of type "object" or an interface then the value type instance will be boxed.
The following code is an example of commonly used constructs that cause boxing operations with value types.
Here's the IL assembly code for those who are curious.
This may not seem like a significant amount of overhead at first glance. However, given enough of these statements sprinkled throughout your application or, worse yet, enclosed within loops, you'll soon discover that the overhead quickly becomes significant. Keep in mind that each boxing operation consists of a heap allocation and a copy operation. In addition, there's overhead in maintaining the heap-based object: reference tracking, heap compaction, and garbage collection.
So how do we work around this boxing problem? Remember that value types ultimately derive from "object" and that "object" exposes a ToString() method. In certain cases, calling the ToString() method, which returns a string instance, is more efficient than allowing a boxing operation to occur.
Here's a code fragment that allows boxing to occur when writing to the console.
The loop in the above code fragment took 150 milliseconds on average to execute. (Benchmarks are based on a 700 Mhz Pentium III processor with 256 MB of RAM.)
Now let's avoid the boxing operation altogether by calling the ToString() method on each value type instance passed to the WriteLine() call.
As you can see from the following screen capture, we saved an average of 30 milliseconds by calling the ToString() method.
Let's switch our attention to array usage. Using arrays to store a collection of value types is a common area where boxing can hurt application performance. First, we'll cover the ubiquitous ArrayList, then we'll look at conventional arrays.
The ArrayList type, located in the System.Collections namespace, is not actually a true array (although one can index through the elements like a conventional array). It is a reference type that implements an array-like collection using a linked-list. It exposes an indexer property that allows you to index through the elements, using the bracket operator like a conventional array. This indexer property exposes a "get" method that returns a reference of type "object" and a "set" method that takes an argument of type "object." The ArrayList also supports an "Add" method that allows you to add a new element of type "object" to the array. So, it's no surprise to see that boxing and unboxing operations occur when adding or indexing through an ArrayList containing value types.
The following code fragment demonstrates adding 100,000 Rectangle instances to an ArrayList. (The ArrayList was allocated with a capacity of 100,000 entries prior to the loop.)
This loop averaged 50.079 milliseconds to complete.
Now, let's take a look at conventional arrays, those defined using the bracket notation. Like the ArrayList, conventional arrays are also allocated from the managed heap. Unlike the ArrayList, however, elements are located contiguously in the managed heap. (For reference object arrays, the references are located contiguously not necessarily the objects themselves.)
The following code shows the previous example using an "object" array rather than an ArrayList.
This loop also took on average 50.079 milliseconds, as shown in the following screen shot. Surprisingly, using an array of objects isn't any more efficient than using the ArrayList in this example. (However, for non-trivial applications you can expect the ArrayList to be far less efficient than the object array due to its linked-list implementation.)
We can do much better if we can manage to remove the boxing operation. What happens if we use a Rectangle array rather than an object array?
Removing the boxing operation has dramatically brought the execution time down to 10.0154 milliseconds!
Now, let's look at the performance of accessing the elements in these arrays. The following code fragment shows a loop that iterates through each element in the ArrayList. (I purposely left the code block empty to avoid coloring the performance of the loop with additional instructions.)
The execution of this loop took about 20 milliseconds.
The next code fragment shows a loop that iterates through each element of an "object" array.
As you would expect (because of unboxing), the execution time is equivalent to that of the ArrayList.
Finally, we see a loop that iterates through each element of a "Rectangle" array.
This time, the execution time is cut by over ten milliseconds.
This fast execution time is due in part to the avoidance of unboxing operations and from locality of reference. We derive good locality of reference because the Rectangle instances in the array reside contiguously in the managed heap. In contrast, the boxed Rectangle instances contained in the ArrayList and in the "object" array may occupy non-contiguous space in the managed heap. This can potentially cause undue paging when accessing elements in a fragmented heap.
Throughout this article, you have seen how boxing and unboxing of value types can cause subtle programming errors and affect application performance. When using value types in your applications, evaluate how you are using them and understand how they are being handled by the CLR. In short, learn the .NET IL assembler and use the ILDASM utility to open the hood on your C# code.
About the Author
Stuart Fujitani is a software consultant in Silicon Valley with thirteen years of experience designing and developing commercial software on the Windows platform. He can be reached at email@example.com.
Lidin, Serge. Inside Microsoft .NET IL Assembler,
Microsoft Press, 2002.
Richter, Jeffrey. Applied Microsoft .NET Framework Programming,
Microsoft Press, 2002.