Friday 18 July 2014

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!
Share this article on LinkedIn.

No comments:

Post a Comment