Some years ago I worked on a project where I built a small rules engine. The rules runs anytime a user logs into the application and it deals with a fairly large amount of data. Therefore its performance is a key consideration.
In this article I discuss:
- How Value Types are stored in memory
- How the default Object methods can cause performance issues
- Solutions for these issues
Value Types and Memory
.Net stores values types in the Stack, or inline within the containing type. What this means is that if you have a Struct such as:
public struct MyStruct
{
public int Index;
public bool IsInitialized;
}The memory for the Index and IsInitialized values are stored within the memory allocated for each MyStruct instance. For example, an array of MyStruct stores in sequential memory like so:
For comparison, a Reference Type does not contain the data directly, it contains a memory reference to the data. Reference types are stored in the Garbage Collected Heap and it contains two header fields, in addition to the data. This looks something like this:
An array of the Boxed MyStruct values would store in non-sequential memory and look something like this:
Reference types (boxed values) take up more memory than its Value Type version due to the added Headers. The process of Boxing and Unboxing is also very expensive (computationally). Therefore avoiding it is key in order to achieve performance gains.
Default Object Methods
In .Net all types are derived from System.Object (or just Object). Object is a Reference type and also a base type of Value Types, but how can this be?
The reason for this is that Value Types derive from a class called ValueType, which is part of the System namespace. The ValueType class overrides virtual methods from Object with more appropriate implementations for Value Types. This mean that when a Value Type is expected to behave like a Reference Type, a wrapper that makes the Value Type behave like a Reference Type is created (and allocated on the GC Heap), also known as Boxing.
System.Object defines an Equals method. If we look at its signature, we notice that it takes an Object (Reference Type) as the “compare to” value.
public virtual bool Equals (object obj);
The default Value Type implementation of this method uses Reflection and causes the value to be Boxed for each comparison. Therefore understanding this is key to improving its performance.
In this example, I use the following struct to make large number of comparison using the default ValueType.Equals() implementation. The results are shown below. It lists the average time per call to ValueType.Equals() and the number of Garbage Collections performed.
public struct MyStruct
{
public int Index;
public bool IsInitialized;
}
The Solution to the Performance Problem
Once you know how to resolve the issue, the solution is quite simple. The first step is to Override the Equals method to prevent unnecessary Reflection. The second is to implement the IEquatable<T> interface, which requires an overload of the Equals() method that takes the type T as the parameter. By implementing IEquatable for a Value Type, you create a strong-typed implementation of Equals method. Therefore effectively eliminating the need for Boxing. The next iteration of the MyStruct shows how this is done.
public struct MyStructV2 : IEquatable<MyStructV2>
{
public int Index;
public bool IsInitialized;
public override bool Equals(object obj)
{
// If the types is not MyStructV2 return false
if ((obj is MyStructV2) == false)
{
return false;
}
// Cast the incoming object to a Value Type
MyStructV2 other = (MyStructV2) obj;
// Perform the comparison on the value
return Index == other.Index;
}
public bool Equals(MyStructV2 other)
{
return Index == other.Index;
}
}The performance improvement is over 73 fold with 0 Garbage Collection. This is significant since it can become exponentially expensive at scale.
One last thing to note is that the ValutType.GetHashCode is an override of the Object.GetHashCode implementation and not suitable for Value Types . Therefore it is worth providing an implementation of the GetHashCode method for your Value Type. Especially when you override the Equals method because the Hash Code for two equal instances, should also be equal.
HashSets and Dictinonaries make use of the GetHashCode. Therefore if there is any chance your Value Type will be used in one of those collections you should provide a custom implementation of GetHashCode.