6
\$\begingroup\$

I was writing an answer in another thread and came across this challenge. I'm trying to have a generic class so that I can delegate the routine (and tiring) Equals and GetHashCode implementation to it (which should handle all that). With the code things will be clearer.

Please note that I have no problem with performance as of now. But when writing a generic library for future use, I'm contemplating better designs. I'll include the bare minimum code required to drive the idea.

Approach 1

public class Equater<T> : IEqualityComparer<T>
{
    public IEnumerable<Func<T, object>> Keys { get; private set; }

    public Equater(params Func<T, object>[] keys)
    {
        Keys = keys;
    }

    public bool Equals(T x, T y)
    {
        ----
    }

    public int GetHashCode(T obj)
    {
       .....
    }
}

//an example usage
public class Dao : IEquatable<Dao>
{
    static Equater<Dao> equater = new Equater<Dao>(x => x.Id, x => x.Table);

    public bool Equals(Dao other)
    {
        return equater.Equals(this, other);
    }

    public override int GetHashCode()
    {
        return equater.GetHashCode(this);
    }
}

This is great considering it works for any number of properties. But performance sucks, boxing I believe is the culprit. Runs in around 260 ms for about 100000 calls to GetHashCode.

Approach 2

public static class Equater<T>
{
    public static Func<T, T, bool> equals;
    public static Func<T, int> getHashCode;

    public static void Set<TKey1, TKey2>(Func<T, TKey1> key1Selector, 
                                         Func<T, TKey2> key2Selector)
    {
        equals = (x, y) =>
        {
            ----
        };
        getHashCode = t => { .... };
    }

    //other overloads of Set with varying type arguments
}

//an example usage
public class Dao : IEquatable<Dao>
{
    static Dao()
    {
        Equater<Dao>.Set(x => x.Id, x => x.Table);
    }

    public bool Equals(Dao other)
    {
        return Equater<Dao>.equals(this, other);
    }

    public override int GetHashCode()
    {
        return Equater<Dao>.getHashCode(this);
    }
}

Runs in around 100 - 110 ms this time.

Approach 3

public abstract class Equater<T> : IEqualityComparer<T>
{
    public static Equater<T> Create<TKey>(Func<T, TKey> keySelector)
    {
        return new Impl<TKey>(keySelector);
    }

    public static Equater<T> Create<TKey1, Tkey2>(Func<T, TKey1> key1Selector, 
                                                  Func<T, Tkey2> key2Selector)
    {
        return new Impl<TKey1, Tkey2>(key1Selector, key2Selector);
    }

    //etc. other overloads of Create with varying type arguments

    public abstract bool Equals(T x, T y);

    public abstract int GetHashCode(T obj);



    class Impl<TKey> : Equater<T>
    {
        readonly Func<T, TKey> keySelector;

        public Impl(Func<T, TKey> keySelector)
        {
            this.keySelector = keySelector;
        }

        public override bool Equals(T x, T y)
        {
            ----
        }

        public override int GetHashCode(T obj)
        {
            ....
        }
    }

    class Impl<TKey1, TKey2> : Equater<T>
    {
        readonly Func<T, TKey1> key1Selector;
        readonly Func<T, TKey2> key2Selector;

        public Impl(Func<T, TKey1> key1Selector, Func<T, TKey2> key2Selector)
        {
            this.key1Selector = key1Selector;
            this.key2Selector = key2Selector;
        }


        public override bool Equals(T x, T y)
        {
            ----
        }

        public override int GetHashCode(T obj)
        {
            ....
        }
    }
}

//an example usage
public class Dao : IEquatable<Dao>
{
    static Equater<Dao> equater = Equater<Dao>.Create(x => x.Id, x => x.Table);

    public bool Equals(Dao other)
    {
        return equater.Equals(this, other);
    }

    public override int GetHashCode()
    {
        return equater.GetHashCode(this);
    }
}

Approaches 80 - 90 ms. This is a lot verbose since I have to write a class for every additional type argument, but is the fastest.

Can I implement it better?

Please note that my question is not about performance as such (for that reason I've not included the critical GetHashCode part as my question is not about that). I'm trying to know if I can implement the above in a cooler and more efficient way. In other words its more about efficiency than performance.

\$\endgroup\$

migrated from stackoverflow.com Apr 16 '13 at 11:18

This question came from our site for professional and enthusiast programmers.

3
\$\begingroup\$

You can reach maximum performance by generating specialized code at runtime using Expression trees. Instead of injecting Funcs, inject Expression<Func<...>> s into your Equater class. Analyze what field they point to and build up the corresponding expressions for hashing and equality.

That way you only have to execute one static field load and one delegate call per call to Equals or GetHashCode.

\$\endgroup\$
  • \$\begingroup\$ Can you give a pointer? Or the bare minimum code to get me going? I did not understand this: Analyze what field they point to and build up the corresponding expressions for hashing and equality. Isn't that my 2nd approach is already doing? \$\endgroup\$ – nawfal Apr 16 '13 at 11:33
  • \$\begingroup\$ Your 2nd approach is combining delegates, not the expressions they were built from. It is really hard to give a short overview about expression trees. I suggest you read a little about them because that will be a more thorough information that I can offer here. Basically, expressions are a way to represent C# expressions at runtime in the form of an AST. That allows you to manipulate them and create new functions at runtime. \$\endgroup\$ – usr Apr 16 '13 at 11:37
  • \$\begingroup\$ Do you have a good starter link to start with? A related question or so? Or some key words for google will do too.. \$\endgroup\$ – nawfal Apr 16 '13 at 11:39
  • 1
    \$\begingroup\$ Googling for "c# expression trees" I find some good stuff: msdn.microsoft.com/en-us/library/bb397951.aspx stackoverflow.com/questions/403088/… stackoverflow.com/questions/683620/… If you have specific questions about them I'll answer them on SO if I happen to see them. \$\endgroup\$ – usr Apr 16 '13 at 11:42
1
\$\begingroup\$

Yes, boxing is likely the culprit. To fix that, you need to type your Funcs as in Example 3. Just make your Equater class better so it's not as verbose. Expression trees won't buy you anything here.

public class Equater<T>
{
    private readonly List<IEquaterFunc<T>> _equaterFuncs = new List<IEquaterFunc<T>>();

    public bool Equals(T x, T y)
    {
        return _equaterFuncs.All(equaterFunc => equaterFunc.Equals(x, y));
    }

    public int GetHashCode(T obj)
    {
        //do something
    }

    public void AddEquaterFunc<TProperty>(Func<T, TProperty> equaterFunc)
    {
        _equaterFuncs.Add(new EquaterFunc<T, TProperty>(equaterFunc));
    }
}

public interface IEquaterFunc<T>
{
    bool Equals(T x, T y);
    int GetHashCode(T obj);
}

public class EquaterFunc<T, TProperty> : IEquaterFunc<T>
{
    private readonly Func<T, TProperty> _func;

    public EquaterFunc(Func<T, TProperty> func)
    {
        _func = func;
    }

    public bool Equals(T x, T y)
    {
        //use EqualityComparer<TProperty>.Default to avoid boxing
        return EqualityComparer<TProperty>.Default.Equals(_func(x), _func(y));
    }

    public int GetHashCode(T obj)
    {
        TProperty value = _func(obj);
        return ReferenceEquals(value, null) ? 0 : value.GetHashCode();
    }
}

//an example usage
public class Dao : IEquatable<Dao>
{
    private static readonly Equater<Dao> Equater;

    static Dao()
    {
        Equater = new Equater<Dao>();
        Equater.AddEquaterFunc(x => x.Id);
        Equater.AddEquaterFunc(x => x.Table);
    }

    public bool Equals(Dao other)
    {
        return Equater.Equals(this, other);
    }

    public override int GetHashCode()
    {
        return Equater.GetHashCode(this);
    }

    public int Id { get; set; }
    public string Table { get; set; }
}
\$\endgroup\$
1
\$\begingroup\$

I created a library a while ago that takes exactly the approach described by usr. Feel free to take a look at it: https://github.com/thedmi/Equ . You can find the expression tree magic in the class EqualityFunctionGenerator.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.