Implementing a fast point structure in C# for large-scale comparison checks and searches

The code below is extracted from Part I of the Pluralsight course "Making .NET Applications faster", discussed and presented below. Implementing a fast structure for 2D points in C# requires using a struct instead of a class, since this is value-based and not reference type, i.e making use of the stack and not the heap and avoiding expensive header fields of objects. In addition, it is necessary to:

• Override the Equals method inherited from System.Object
• Implement a method called Equals that returns true and has one input parameter, another instance of the same struct
• Mark the struct with the generic IEquatable interface, IEquatable<PointV5>
• Implement the operators == and != to make use of the Equals method receiving an instance of the struct
• Implement GetHashCode, using Jon Skeet's advice of creating a weighted sum multiplied by prime numbers and the struct's fields

Implementing this equality regime will reduce overall size in memory about 4x and increase speed 4x to 10x for large scale scenarios. In the example code testing this code, 10 million 2D point structs of type PointV5 was tested. Most modern games will avoid reference types of course and stick to value types, i.e. structs. Since most of us are application developers, make sure if you create a LOT of objects, consider switching from class to struct type(s), if possible. Often, it is not needed to use classes, a struct will be sufficient (and faster and lighter). Check out the course page here: Pluralsight: Making .NET applications faster Pluralsight is a great course and IT resource for IT professionals!

using System;


    struct PointV5 : IEquatable
    {
        public int X;
        public int Y;

        public override bool Equals(object obj)
        {
            if (!(obj is PointV5)) return false;
            PointV5 other = (PointV5)obj;
            return X == other.X && Y == other.Y;
        }

        public bool Equals(PointV5 other)
        {
            return X == other.X && Y == other.Y;
        }

        public static bool operator ==(PointV5 a, PointV5 b)
        {
            return a.Equals(b);
        }

        public static bool operator !=(PointV5 a, PointV5 b)
        {
            return !a.Equals(b);
        }

        public override int GetHashCode()
        {
            // 19 and 29 are primes, and this doesn't assume anything about
            // the distribution of X and Y.
            // Also see http://stackoverflow.com/questions/263400/what-is-the-best-algorithm-for-an-overridden-system-object-gethashcode
            int hash = 19;
            hash = hash * 29 + X;
            hash = hash * 29 + Y;
            return hash;
        }
    }

Actually, a simple class is in fact faster in this scenario, according to the testing I did. Consider this class:

public class PointV0
{

        public int X { get; set; }

        public int Y { get; set; }

}

However, the price on pays here is higher memory overhead, as each point will have to be stored on the heap and have the object header fields and method table pointer fields, i.e. taking up more memory.

Elementary class
        Average time per lookup: 85,70ms
        Garbage collections: 0
Naked struct
        Average time per lookup: 435,10ms
        Garbage collections: 1018
With Equals override
        Average time per lookup: 248,70ms
        Garbage collections: 510
With Equals overload
        Average time per lookup: 239,50ms
        Garbage collections: 510
With IEquatable
        Average time per lookup: 168,60ms
        Garbage collections: 0
All bells and whistles
        Average time per lookup: 170,00ms
        Garbage collections: 0
Press any key to continue ..

I cannot conclude from these results that structs always are faster than classes, but it will always be more memory overhead to resort to classes instead of structs.. It looks though, that in this example, a simple class was the fastest choice!

A generic IEqualityComparer of T written in C#

When working with LINQ, often one has to pass in an IEqualityComparer of the class(es) being used. Implementing IEqualityComparer on classes can sometimes be unwanted to just make the computations work, therefore a generic implementation would be nice to invoke when performing the LINQ expression without either adding IEqualityComparer or worse - having to rewrite it. Sometimes also multiple implementations are desired.. The following class LambdaComparer is a generic implementation of IEqualityComparer of T.

using System;
using System.Collections.Generic;

namespace Hemit.OpPlan.Client.Infrastructure.Utility
{
    /// <summary>
    /// LambdaComparer - avoids the need for writing custom IEqualityComparers
    /// 
    /// Usage:
    /// 
    /// List<MyObject> x = myCollection.Except(otherCollection, new LambdaComparer<MyObject>((x, y) => x.Id == y.Id)).ToList();
    /// 
    /// or
    /// 
    /// IEqualityComparer comparer = new LambdaComparer<MyObject>((x, y) => x.Id == y.Id);
    /// List<MyObject> x = myCollection.Except(otherCollection, comparer).ToList();
    /// 
    /// </summary>
    /// <typeparam name="T">The type to compare</typeparam>
    public class LambdaComparer<T> : IEqualityComparer<T>
    {
        private readonly Func<T, T, bool> _lambdaComparer;
        private readonly Func<T, int> _lambdaHash;

        public LambdaComparer(Func<T, T, bool> lambdaComparer) :
            this(lambdaComparer, o => 0)
        {
        }

        public LambdaComparer(Func<T, T, bool> lambdaComparer, Func<T, int> lambdaHash)
        {
            if (lambdaComparer == null)
            {
                throw new ArgumentNullException("lambdaComparer");
            }

            if (lambdaHash == null)
            {
                throw new ArgumentNullException("lambdaHash");
            }

            _lambdaComparer = lambdaComparer;
            _lambdaHash = lambdaHash;
        }

        public bool Equals(T x, T y)
        {
            return _lambdaComparer(x, y);
        }

        public int GetHashCode(T obj)
        {
            return _lambdaHash(obj);
        }
    }
}

The following unit tests uses this implementation of a generic IEqualityComparer of T:

using System;
using System.Collections.Generic;
using System.Linq;
using Hemit.OpPlan.Client.Infrastructure.Utility;
using NUnit.Framework;

namespace Hemit.OpPlan.Client.Infrastructure.Test.Utility
{
    
    [TestFixture]
    public class LambdaComparerTest
    {

        [Test] 
        public void LambdaComparerPerformsExpected()
        {
            var countriesFirst = new List<Tuple<int, string>>{ 
                new Tuple<int, string>(1, "Spain"),
                new Tuple<int, string>(3, "Brazil"),
                new Tuple<int, string>(5, "Argentina"),
                new Tuple<int, string>(6, "Switzerland"),
                new Tuple<int, string>(7, "Uruguay"),
                new Tuple<int, string>(8, "Colombia")
            };
            var countriesSecond = new List<Tuple<int, string>>{
                new Tuple<int, string>(1, "Spain"),
                new Tuple<int, string>(4, "Portugal"),
                new Tuple<int, string>(7, "Uruguay"),
                new Tuple<int, string>(10, "England"),
                new Tuple<int, string>(11, "Belgium"),
                new Tuple<int, string>(12, "Greece")
            };

            var expected = new List<Tuple<int, string>>
            {            
                new Tuple<int, string>(3, "Brazil"),
                new Tuple<int, string>(5, "Argentina"),
                new Tuple<int, string>(6, "Switzerland"),               
                new Tuple<int, string>(8, "Colombia")                
            }; 

            var countriesOnlyInFirst = countriesFirst.Except(countriesSecond, new LambdaComparer<Tuple<int, string>>((x, y) => x.Item1 == y.Item1));

            CollectionAssert.AreEqual(countriesOnlyInFirst, expected); 

        }


    }


}

In the unit test above, two lists containing the topmost FIFA ranking country teams in soccer in the world are being used in a LINQ Except expression, where the generic LambdaComparer class is being used. The class being passed in is Tuple of int and string: Tuple<int,string> - Note that an ordinary class could also be used here. The property Item1 of the Tuple is the "key" that is being used to compare two different objects - if it is the same, the objects are being considered to be the same. This results into a list of items from the first country list that are not being present in the second list. Finally, a list of the expected result is being built up and the NUnit CollectionAssert.AreEqual method is used for checking consistent result. The test passes. Much of .NET requires implementing interfaces such as IEqualityComparer, IComparer and more. Using a generic implementation class that expects Func expressions (the lambda expressions being passed, is a pattern that can give much flexibility.

Generic type conversion in C#

Generic type conversion in C# is possible, but the type conversion must consider many different conversions. The following code below defines a generic method To<T> which is an extension method on object:

namespace Hemit.OpPlan.Common
{
    
    public static class ObjectExtensions
    {

        public static T To<T>(this object value)
        {
            if (value == null)
                return default(T);

            Type t = typeof(T); 

            if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>))
            {
                Type valueType = t.GetGenericArguments()[0];
                if (value == null)
                    return default(T);
                object result = Convert.ChangeType(value, valueType);
                return (T)result;
            }
            else if (typeof(T).IsEnum)
            {
                object result = Enum.Parse(typeof(T), value.ToString());
                return (T)result;
            }
            else
            {
                try
                {
                    object result = Convert.ChangeType(value, typeof(T));
                    return (T)result;
                }
                catch (Exception err)
                {
                    Debug.WriteLine(err.Message);
                    return default(T); 
                }
            }
        }

    }
}

Next is a couple of unit tests written in NUnit for this extension method. All tests passes.

using System;
using System.Reflection;
using Hemit.OpPlan.Common.DataContract;
using NUnit.Framework;  

namespace Hemit.OpPlan.Common.Test.Extensions
{
    
    [TestFixture] 
    public class ObjectExtensionsTest
    {

        [Test]
        [TestCase("4", typeof(int), 4)]
        [TestCase("true", typeof(bool), true)]
        [TestCase(null, typeof(bool), false)]
        [TestCase(null, typeof(Nullable<bool>), null)]
        [TestCase("true", typeof(Nullable<bool>), true)]
        [TestCase("FutureOperation", typeof(OperationStatusDataContract), OperationStatusDataContract.FutureOperation)]
        [TestCase("Postponed", typeof(OperationStatusDataContract), OperationStatusDataContract.Postponed)]
        public void ToReturnsExpected(object input, Type genericTypeArgument, object expected)
        {
            MethodInfo method = typeof(ObjectExtensions).GetMethod("To");
            MethodInfo genericMethod = method.MakeGenericMethod(new Type[] { genericTypeArgument });
            object actual = genericMethod.Invoke(input, new object[]{ input });
            Assert.AreEqual(actual, expected); 
        }

        [Test] 
        public void ToReturnsExpectedWithNullableBoolean()
        {
            int? inputValue = new Nullable<int>(3);
            int actual = ((int?)inputValue).To<int>(); 
            Assert.AreEqual(actual, 3); 
        }

    }

}

The code above shows how one can call a generic method, shown in the unit test. Multiple test cases are passed into this unit test method. As is visible to the reader, the class ObjectExtensions contains the method To, which considers a conversion of an object to a designated type. The conversion itself must of course be valid, in addition one should check that the value implements IConvertible or similar interface. I have kept the code rather short and will eloborate the code if I see thare are conversions that fail, which should work.