Beware of implicit boxing of value types

In the last post, we looked at some inef­fi­cien­cies with ref­er­ence types in .Net and per­haps over­sold val­ue types a lit­tle  In any case, now that we’ve made the ini­tial sale and you’re back for more, let’s talk about some pit­falls wrt the use of val­ue types you should be aware of. Specif­i­cal­ly let’s focus on cas­es where the CLR will cause implic­it box­ing on your val­ue types.

 

We all know that when we cast a val­ue type to object, we cause box­ing. For instance, if we need to shove an int into an object[] or an ArrayList.

This is not great, but at least we’re doing this con­scious­ly and have had the chance to make a deci­sion about it. How­ev­er, there are a num­ber of sit­u­a­tions where the CLR will emit a box IL instruc­tion for us implic­it­ly with­out us real­iz­ing. These are far worse.

 

When you invoke a virtual method

Val­ue types inher­it from the System.ValueType, which itself inher­its from System.Object. Amongst oth­er things, System.ValueType pro­vides an over­ride for Equals that gives val­ue types the default com­pare-by-val­ue behav­iour.

How­ev­er, a val­ue types is stored in mem­o­ry with­out the Method Table Point­er (see the last post) so in order to dis­patch a vir­tu­al method call it’ll first have to be boxed into a ref­er­ence type first.

There is an excep­tion to this though, as the CLR is able to call Equals direct­ly if the val­ue type over­rides the Equals method (which is why it’s a best prac­tice to do so).

Aside from ben­e­fit­ing from CLR’s short-cir­cuit behav­iour above, anoth­er good rea­son to over­ride Equals in your cus­tom val­ue type is because the default imple­men­ta­tion uses reflec­tion to fetch its fields to com­pare.

Fur­ther more, it then uses UnsafeGet­Val­ue to get the val­ue of the field on both the cur­rent object and the object being com­pared to, both of which caus­es fur­ther box­ing as FieldInfo.UnsafeGetValue takes an object as argu­ment.

But wait, there’s more…

Even if you over­ride Equals(object oth­er), it’ll still cause box­ing to the input argu­ment. To get around this you’ll need to over­load Equals to take in anoth­er Point2D instance instead, i.e. Equals(Point2D oth­er), which is of course anoth­er rec­om­mend­ed best prac­tice from the pre­vi­ous post.

Giv­en these three ver­sions of Point2D:

  • V1 = plain old struct
  • V2 = over­rides Equals(object oth­er)
  • V3 = over­loads Equals(Point2DV3 oth­er)

We can see how they fared when we iter­ate through 10M instances of each and call­ing Equals each time.

Cou­ple of things to note from the above:

  • V1 caus­es twice as much box­ing as V2 (makes sense giv­en the short-cir­cuit­ing behav­iour)
  • V1 also takes near­ly four times as long to exe­cute com­pared to V2
  • V3 caus­es no box­ing, and runs in near­ly half the time as V2!

side­bar : I chose to run the test in F# because it’s easy to get quick insight (real and CPU time + GC counts) when you enable the #time direc­tive. How­ev­er, I had to define the types in C# as by default F# com­piles struct types with all the opti­miza­tions we have talked about — which means:

a. it’s a good rea­son to use F#; but

b. defeats the pur­pose of run­ning the­ses tests!

 

Unfor­tu­nate­ly, there is still one more edge case…

 

When you call List<T>.Contains

When you call List<T>.Contains, an instance of EqualityComparer<T> will be used to com­pare the argu­ment against every ele­ment of the list.

This even­tu­al­ly caus­es a new EqualityComparer<T> to be cre­at­ed.

In the default case (where Point2D doesn’t imple­ment the IEquatable<T> inter­face), the ObjectEqualityComparer<T> will be returned. And it is in here, that the overridden/inherited Equals(object oth­er) method will be used and caus­es box­ing to occur for every com­par­i­son!

If, on the oth­er hand, Point2D imple­ments the IEquatable<T> inter­face then the out­come will be very dif­fer­ent. This allows some clever log­ic to kick in and use the over­loaded Equals(Point2D oth­er) instead.

 

So now, let’s intro­duce V4 of Point2D that imple­ments the IEquatable<T> inter­face and see how it com­pares to

  • V2 = over­rid­den Equals(Object oth­er) ; and
  • V3 = over­loaded Equals(Point2DV3 oth­er)

when used in a List<T>.

For V2, List<T>.Contains per­forms the same as our hand cod­ed ver­sion, but the improve­ments we made with V3 is lost due to the rea­sons out­lined above.

V4 rec­ti­fied this by allow­ing the opti­miza­tion in List<T> to kick in.

 

Which brings us to the next implic­it box­ing…

 

When you invoke an interface method

Like vir­tu­al meth­ods, in order to dis­patch an inter­face method you also need the Method Table Point­er, which means box­ing is required.

For­tu­nate­ly, the CLR is able to short-cir­cuit this by call­ing the method direct­ly if the com­pile-time type is resolved to the actu­al val­ue type (e.g. Point2D) rather than the inter­face type.

 

For this test, we’ll try:

  • invoke Equals(Point2DV4 oth­er) via the IEquatable<Point2DV4> inter­face; vs
  • invoke Equals(Point2DV4 oth­er) direct­ly on Point2DV4

 

As you can see, invok­ing the inter­face method Equals(Point2DV4 oth­er) does indeed incur box­ing once for each instance of Point2D.

 

When Dictionary<T> invokes GetHashCode

GetH­ash­Code is used by hash-based col­lec­tion types, the most com­mon being Dictionary<TKey, TVal­ue> and HashSet<T>.

In both cas­es, it’s invoked through the IEqualityComparer<T> type we talked ear­li­er, and in both cas­es the com­par­er is also ini­tial­ized through EqualityComparer<T>.Default and the Cre­ate­Com­par­er method.

GetH­ash­Code is invoked in many places with­in Dictionary<TKey, TVal­ue> — on Add, Con­tainsKey, Remove, etc.

For this test let’s find out the effects of:

  • imple­ment­ing the IEquatable<T> inter­face in terms of box­ing
  • over­rid­ing GetH­ash­Code (assum­ing the default imple­men­ta­tion requires the use of reflec­tion)

but first, let’s cre­ate V5 of our Point2D struct, this time with a over­rid­den GetH­ash­Code imple­men­ta­tion (albeit a bad one, which is OK for this since we only want to see the per­for­mance impli­ca­tion of hav­ing one).

In this test, we have:

  • V3 = no GetH­ash­Code over­ride, not imple­ment IEquatable<T>
  • V4 = no GetH­ash­Code over­ride, imple­ments IEquatable<T>
  • V5 = has GetH­ash­Code over­ride, imple­ments IEquatable<T>

I used a much small­er sam­ple size here (10K instead of 10M) because the amount of time it took to add even 10K items to a dic­tio­nary was suf­fi­cient to illus­trate the dif­fer­ence here. Even for this small sam­ple size, the dif­fer­ence is very notice­able, cou­ple of things to note:

  • since V3 doesn’t imple­ment IEquatable<T> it incurs box­ing, and a lot of it because Equals is also called through the IEqualityComparer<T>
  • V4 elim­i­nates the need for box­ing but is still pret­ty slow due to the default GetH­ash­Code imple­men­ta­tion
  • V5 address­es both of these prob­lems!

side­bar : with GetH­ash­Code there are also con­sid­er­a­tions around what makes a good hash code, e.g. low chance of col­li­sion, even­ly dis­trib­uted, etc. but that’s anoth­er dis­cus­sion for anoth­er day. Most times I just let tools like Resharp­er work out the imple­men­ta­tion based on the fields my val­ue type has.

 

Conclusions

As we have seen, there are a num­ber of places where implic­it box­ing can hap­pen and how much of a dif­fer­ence these might have on your per­for­mance. So, to reit­er­ate what was already said in the pre­vi­ous post, here are some best prac­tices for using val­ue types:

  • make them immutable
  • over­ride Equals (the one that takes an object as argu­ment);
  • over­load Equals to take anoth­er instance of the same val­ue type (e.g. Equals(Point2D oth­er));
  • over­load oper­a­tors == and !=;
  • over­ride GetH­ash­Code

 

Links