Monday, August 18, 2008

Generics Fast

You are trying to come up to speed in C# fast. Then all of a sudden, you come across the C# Generic Type and wonder how do I master that.

Well, I've got some good news for you. You are in good company. You thought I was going to say I'll help you master generics. No, that's beyond a simple blog like mine. But, maybe I can help you become proficient. We just have to get the main learning hurdles out of the way.

Hurdle #1 - Rationale
Generic Types were added to C# in version 2.0. Now, I am not going to go into any detail on the history of C# or generics. I just mention this because the C# team decided they had a serious enough short coming in 1.1 to add this major feature. That is, many, many programmers were opting to ditch type-safety and decent performance in order to write more versatile data structures. How's that? Well, folks (MS included) were writing things like List and Queue and Stack to take "objects". Then their particular data structure could work on anything, and that would maximize code reuse (and likewise productivity).

The problem is, though re-use is greatly increased, productivity may be closer to a "wash" than a gain. That's because in implementing a "generic" structure that takes only "object" types, type-safety is lost. With lost type-safety, there's an increase in coding errors and run-time bugs and thus more time is spent testing and fixing the code. Okay, reusability is a win, productivity is a tie maybe, and performance is a what? Well performance is a loser. To use such a data structure with integers will require the compiler to "box" the type to make it an object. For reference types, the compiler spends extra time with cast operations. One article states the performance of the object data structure is about 200% slower than if it had been implemented as a specific value type.

Generic types solve the performance issue while giving the programmer back the type safety. And, clearly generic types provide for substantial code reuse.

Hurdle #2 - How to Use a Generic Type
Alright. It's good to know why, but it's better to know how. Let's start by using a generic type defined by the framework. Let's start with the List.

// instantiate a List of Strings
List strList = new List();
foreach(string s in strList)

Rather than cut and paste this code into your IDE, go ahead and type it out. Intellisense will help you. In declaring your "strList" as a "List", everything about the list is now "string" oriented. The constructor, the Add(), the enumeration, etc. It's as if a wholesale find and replace has be done on the type place holder. Maybe you saw <T> in the intellisense, T is the place holder. More precisely, T is the "generic parameter" to the List<> type. And though, a macro like replacement is done, it's very different from the C++ Template where the compiler does the replacement. In C#, generics are implemented in the CLR, so its the JIT that is doing the final replacement. It will be good to keep this in mind when you "type-cast" your way around compiler errors only to have your code throw an exception at run-time on a bad conversion.

Hurdle #3 - How to Write a Generic Type
Which brings us to writing our own generic types. This next bit of example code makes use of several applications of the generic type syntax.

public class GenericClass
private T genProp; // a generic field
public T GenProp { // a generic property
get { return genProp; }
set { genProp = value; }
public GenericClass() // a generic constructor
public T GenMethod() // a generic method
return genProp;
public string GenMethodT(T val) // you get the picture
return val.ToString();
// and so on...
// ...
GenericClass gc = new GenericClass();

You can see that the generic parameter T is all over the place and each occurance, if you can imagine, will be filled in with whatever type you end up instantiating this class with. It's behavior will be approriate for whatever "generic argument" you pass.

So, we've got the "generic type", the "generic parameter" and the "generic argument". What are each of these? In the example above, the "generic type" is "GenericClass<T>", the "generic parameter" is "T", and the "generic argument" is "int". There can be multiple generic parameters, and the name of the variable is arbitrary (within naming rule limits, of course). To specify multiple parameters, simply separate them with commas.

Dictionary< int, string> dict = new Dictionary< int, string>();
dict.Add(2,"Two"); // and so on...

public class MyNextGeneric
public T myMethod(U arg)

Hurdle #4 - Using Generic Constraints
You are now well on your way to writing generic classes and methods. It won't take long before you start seeing some interesting compiler errors.

public bool GenMethodCompare(T val1, T val2)
return (val1 == val2) ? true : false;

This bit of code produces the error "Operator '==' cannot be applied to operands of type 'T' and 'T'". You may ask why?! That might be because you are thinking like C++ instead of C#. In C++, maybe you have instantiated the class with "int" which is very easy to compare. The C++ compiler can make the final call. But with C#, the JIT will make the final call, and though the compiler knows what generic arguments you are passing, it does not know what might be passed by an external assembly. The C# team could probably have figured something out, but with deadlines looming, who knows. Regardless, it's situations like these for which "Generic Constraints" were invented.

There are three kinds of Generic Constraint, "Derivation Constraints", "Construction Contraints", and "Reference/Value Type Constraints".

In the last example, the compiler "could" compile the generic method if instead of "==", we used object.Compare() and if the compiler could just be assured that any generic argument supplied for T will be an IComparable type object. This would be a "Derivation Constraint". Notice in this next example that I use a generic IComparable interface as the constraint. Any class or interface can be used as a constraint, even other generic parameters.

public MyClass where T : IComparable
public bool GenMethodCompare(T val1, T val2)
return (val1.Equals(val2)) ? true : false;

All the generic constraints use the syntax "where T : constraint, constraint" at the end of the type declaration (after any base class and/or interfaces) and before the open curly brace. If there are multiple generic parameters that each need constraints, the syntax would be

public class GClass : SomeBaseClass, ISomeInterface
where T : IComparable
where U : IEnumerable
{ ... }

"Construction Constraints" are used when your generic class must constuct objects of type T. You may get the error "Cannot create an instance of the variable type 'T' because it does not have the new() constraint". This is very self explanatory message in terms of what you've got to do. But, it occurs because your code is trying to instantiate an object of type "T". Many types are implemented which do not have default (i.e., parameter-less) constructors. Without the "new()" constraint, the compiler will not allow code that instantiates a generic parameter to compile. You can combine new() with other constraints by separating with a comma and placing it after the others.

public class GClass where T : IComparable, new()
public T factory() { return new T(); }

"Reference/Value Type Constraints" tell the compiler that only reference types or only value types are allowed as the generic argument. "class" indicates a reference type constraint, while "struct" indicates a value type constraint. Notice that it doesn't make any sense to combine the "struct" generic constraint with the "Derivation Constaints", they are incompatible. It doesn't make sense to combine the "class" generic constraint either, it is redundant.

public class RTypeClass where T : class { ... }
public class VTypeClass where T : struct { ... }

Finish Line
That's about all I can cover in an evening. You should have everything you need to start using and creating your own generic types. My article "Thread Synchronized Queing" is reasonable working example of a generic Queue class if you think that would be of any value to you. Just don't try writing anything too complex right away, I wouldn't want you to hurt yourself.

Useful Resources
An Introduction to C# Generics
Generics (C#)
Using C# Generics on Static Classes - Wes' Puzzling Blog
C# Frequently Asked Quetions - How do C# generics compare to C++ templates?

No comments: