Avoiding Boxing in Classes Implementing Generic Interfaces through Reflection [Dave Fetterman]

Avoiding Boxing in Classes Implementing Generic Interfaces through Reflection [Dave Fetterman]

  • Comments 6

Krzysztof Cwalina showed me this cool trick to avoid boxing value types when working with generics and interfaces.
This may be a bit dense but the trick is rarely seen and illustrative. 

Note before proceeding: This technique is only available in VS.NET Whidbey. 

For the sake of illustration, suppose in .NET there were a notion of combining objects, much like comparing objects.
Thus, we would have interfaces ICombinable and ICombinable<T>, and classes Combiner for objects and an abstract Combiner<T> class,
all similar to those types surrounding the currently available Comparer type.

The generic types could realistically take either values or reference types as arguments.
For instance, one could imagine combining a instances of a value type like MyBitVectorClass by logically ORing them:

public class MyBitVectorClass : ICombine<MyBitVectorClass>
{
  public MyBitVectorClass Combine(MyBitVectorClass arg1, MyBitVectorClass arg2)
  {
    return new MyBitVectorClass(arg1.internalInt | arg2.internalInt);
  }
}

One could also imagine combining instances of ArrayList (a reference type) by concatenating them in some way:

public ArrayList Combine(ArrayList arg1, ArrayList arg2)
{
  ArrayList result = arg1.Clone();
  IEnumerator e = arg2.GetEnumerator();

  while (e.MoveNext())
  {
    Object o = (Object)e.Current;
    result.Add(o);
  }
  return result;
}

In the world of comparison, sometimes we want to use the default on the abstract Comparer class, dictated by our Thread.CurrentCulture.
That is, we can say:

if (0 == Comparer<int>.Default.Compare(intA, intB)) ...
or
if (0 == Comparer<string>.Default.Compare(stringA, stringB)) ...

And just like ICompare's associated abstract Comparer class, there would exist a Combiner, used thus

MyBitVector bv = Combiner<MyBitVector>.Default.Combine(bv1, bv2);
ArrayList al = Combiner<ArrayList>.Default.Combine(al1, al2);

Let's say we wanted to create a static default Combiner for any type.

public abstract class Combiner<T> : ICombiner<T>, ICombiner

  static Combiner<T> defaultCombiner; 
  public static Combiner<T> Default
  {
    get
    {
      Combiner<T> combiner = defaultCombiner;
      if (combiner != null)
      {
        return combiner;
      }
      return CreateCombiner();
    }
  }

  private static Combiner<T> CreateCombiner()
  {
    // create our combiner 
  }

  public abstract T Combine(T x, T y); 

  object ICombiner.Combine(object x, object y)
  {
    if (x == null)
    {
       return y;
    } 
    if (y == null)
    {
       return x;
    } 
    if (x is T && y is T)
    {
      return Combine((T) x, (T) y);
    }
    throw new InvalidOperationException("Bad types etc. ...");
    return null;
  }
}

We want to be able to combine
A. Reference types implementing ICombine
B. Reference types not implementing ICombine
C. Value types implementing ICombine
D. Value types not implementing ICombine

How do we implement the missing code in CreateCombiner with the least boxing possible? 
Cases A and B are already reference types, so no problem there.
Arguments like Case D are going to be boxed and shipped to Combiner.Default.Combine(x,y), so we have no choice.
What about Case C?  Can we generically avoid boxing and shipping off to the object Combiner?

Yes.  The answer is to use reflection. 
Remember, this reflection is a one-time cost when lazily creating the default Combiner over, say, MyBitVector.

The ONLY difference between value types in cases C and D are the interfaces they fulfill. 
Types in case C are assignable to ICombinable, so we use this single piece of information to save us potentially lots of boxing.
We need to create two internal classes to separate the two cases.
In case C, we choose the GenericCombiner over the ObjectCombiner below to guarantee that we're not boxing ICombinable value types.

internal class GenericCombiner<T>: Combiner<T> where T: ICombinable<T>
{
  public override T Combine(T x, T y)
  {
    // assuming ICombinable has a CombineWith method similar to IComparable.
    return (x == null) ? (y == null ? null : y) : x.CombineWith(y);
  }
}

internal class ObjectCombiner<T>: Combiner<T>
{
  public override T Compare(T x, T y)
  {
    return Combiner.Default.Combine(x,y);
  }
}

So, the CreateCombiner() method should split paths based on whether we implement ICombinable<T>, directing to the GenericCombinable
method through some explicit type manipulation:


private static Combiner<T> CreateCombiner()
{
  if (typeof(ICombinable<T>).IsAssignableFrom(typeof(T))
  {
    defaultCombiner = (Combiner<T>)
      Activator.CreateInstance(
        typeof(GenericCombiner<string>).GetGenericTypeDefinition().BindGenericParameters(
          new Type[] { typeof(T) }));
  }
  else
  {
    defaultCombiner = new ObjectCombiner<T>();
  }
  return defaultCombiner;
}

I think this is super cool.  Esoteric?  Perhaps.  Faster?  Definitely.
In an upcoming release, the BCL team may implement a way to make this much easier.

 

  • That's the approach I've used in the past for passing through IFormattible to an inner type without boxing when making ToString calls.

    But that is *NOT* how Comparer<T>.Default is implemented, and I assume that this way is slower.

    Comparer<T>.Default makes a call to an internal method:
    (Comparer<T>)typeof(GenericComparer<string>).TypeHandle.CreateInstanceForAnotherGenericParameter(typeof(T));

    I know that is a *bit* odd, but if it performs significanly better, then I think that this method should be public. Of course, caching the comparer for each type helps, but there *has* to be a reason why Comparer<T> is implemented this way. Or is it because the refelction-based approach was not complete when Comparer<T> was being written?

    Once well-performing method of doing this is established, the C# syntax might be extended to support it.

    I think that there should be an option for runtime check for a constraint, similar to a cast. Something like:

    if(typeof(IComparable<T>).IsAssignableFrom(typeof(T)))
    return new GenericComparer<(IComparable<T>)T>();

    (Or perhaps the "as" version of cast might read better).

    Or perhaps a simple way to remove the compile-time constaint check, so that multiple constraints can be ignored. Something like:

    return new GenericComparer<relax T>();

    Even if this compiles to refleciton-based code, it certainly reads better. Either way, you're just delyaing the constraint check until runtime. (or does the runtime even enforce this?)
  • Matthew,

    You are entirely correct! The CreateInstanceForAnotherGenericParameter method *is* internal-only, and you are right in saying it's likely faster.

    We're actually working now on another way to make this happen in a much easier fashion, so a lot of this becomes moot; making the aforementioned method public might be overlooking an even better, more general solution.
    My example is largely to get the juices flowing; and, to be fair, it's a one-time cost of lazily filling the internal Default member representation.

    But you're right. Thanks for keeping us sharp.
  • Well, to be honest, I'd hate to use a method called "CreateInstanceForAnotherGenericParameter" on a regular basis. While it describes what the method does *very* well, it has a lengthy name (which I realize is moot with intellisense), and it's a non-obvious solution to the problem.

    For example, I assume Comparer<string> is used as the base type when calling this method since Comparer<string> is likely to already be in memory, since string comparison is a very common comparison. For other generic interfaces, I wouldn't know what type to use.

    It also seems that the internal CreateInstanceForAnotherGenericParameter does not work for multiple type parameters. I'm not sure what it would do on a type with two parameters, and since it's an InternalCall I can't take a peek at what it does (well...I'm too lazy to do so).

    I also noticed something about your code that differs from mine:

    typeof(GenericCombiner<string>).GetGenericTypeDefinition().BindGenericParameters(...)

    can be replaced with:

    typeof(GenericCombiner<>).BindGenericParameters(...)

    The confusing part about this is when two or more type parameters are involved. The generic type of Dictionary is Dictionary<,> (which I suppose is C#-speak for Dictionary`2) and not Dictionary<K,V>. This is not immediately obvious from the beta1 documentation, and it took me a while to figure it out. Then again, it doesn't come up very often.

    Perhaps a new method needs to be put on Activator to simplify this process. I propose a new method on Activator called CreateGenericInstance.

    Comparer<T> comparer = Activator.CreateGenericInstance(typeof(GenericComparer<>), typeof(T));

    Overloads for one- and two- type-parameter generic types could avoid the need for a param array in most cases. Even if it used reflection internally, it'd feel more "correct" than hacking around the Type class and then using Activator.
  • Tips
  • Tips
  • Here's the next .NET Framework 2.0 performance guideline for review from Prashant Bansode, Bhavin Raichura,

Page 1 of 1 (6 items)