Generic Algorithms

7/7/2004 4:22:52 AM

Generic Algorithms

Generics provide a good solution for building generic collections. However, they leave a lot to be desired for generic algorithms, especially with primitive types, because new interfaces cannot be attached to such types. Interfaces, combined with constraints, is the .NET provision for generic algorithms. This is one of the major differences between constraint-based generics and name-based templates--that and run-time (versus compilation) generation, specialization, and non-type parameters. Generics, unlike templates, doesn't work with operators, even simple equality testing; hence the introduction of the IComparable<T> interface  into Whidbey with two methods, CompareTo(T) and Equals(T).

Perhaps, this would not be a problem if the CLR had allowed extensions of types outside their definition; I believe that Delphi sometime introduced and patented an invention called Class Helpers for this particular purpose. For now, Microsoft developers rely on a pattern for this XXXHelper, as in StringHelper, to include ancillary methods that should be on main class; this is especially useful for enumeration classes, because they are sealed and cannot define members (properties, methods) other than constants . Of course, this is a not really a solution, because such classes lack true integration by not supporting inheritance, not exposing information through reflection (except perhaps through attributes), and not having access to private members (ok, this is questionable feature).

I came up with a way that might help support generic algorithms with primitive types and operators. The idea is to define an interface for use with constraints and a helper struct that an implementations for specific closed generic interfaces.

    public interface IMath<T>
bool IsZero(T value);
bool IsOne(T value);
T Negate(T value);
T Inverse(T value);
T Add(T left, T right);
T Subtract(T left, T right);
T Multiply(T left, T right);
T Divide(T left, T right);
T Mod(T left, T right);

public struct MathTools : IMath<int>, IMath<long>, IMath<double>, IMath<float>, IMath<decimal>
#region IMath<int> Members
public bool IsZero(int value)
return value==0;

public int Negate(int value)
return -value;

public int Add(int left, int right)
return left + right;
#region IMath<double> Members
// ....

Then when defining a generic method we call it with two type parameters, one for the primitive type and one for the helper struct. Here is a declaration and usage example:

        public T Sum<T, M>(T[] array) where M : IMath<T>
M m default(M);
T result = T);
foreach (T t in array)
result = m.Add(result, t);
return result;

sum = Sum<int, MathHelper>(array);

Using a struct provides advantages over classes. Generics is specifically optimized to avoid boxing and allow direct calls (and potential inlining) for value type implementations of interfaces declared in the constraints. Classes, in contrast, will incur an interface call, which is slower than a virtual call, let alone direct calls.

Note that I used the same struct for multiple interface implementations instead of creating multiple different classes.






Net Undocumented is a blog about the internals of .NET including Xamarin implementations. Other topics include managed and web languages (C#, C++, Javascript), computer science theory, software engineering and software entrepreneurship.

Social Media