Performance in GUID comparison

Question

I read this question and another question. In one of these two questions, I also read that Guid Structure consists of following four fields: Int32, Int16, Int16 and Byte[8], so the comparison between two Guid should be faster.

Well, I use the Guid Structure only to generate UUID, and then I have to compare only those previously generated UUID. Therefore, I would like to convert each UUID generated quickly in a format comparable.

I ran some tests using the following code (I took inspiration from this question).

        struct FastUuid
        {
            public long _part1;
            public long _part2;

            public FastUuid(byte[] value)
            {
                _part1 = BitConverter.ToInt64(value, 0);
                _part2 = BitConverter.ToInt64(value, 8);
            }
        }

        static void Main(string[] args)
        {
            TestUuidCompare(1000000000);
            Console.ReadLine();

        }

        public static void TestUuidCompare(uint numberOfChecks)
        {
            Guid uuid1 = Guid.NewGuid();
            Guid uuid2 = new Guid(uuid1.ToByteArray());

            byte[] a1 = uuid1.ToByteArray();
            byte[] a2 = uuid2.ToByteArray();

            string s1 = uuid1.ToString();
            string s2 = uuid2.ToString();

            BigInteger b1 = new BigInteger(uuid1.ToByteArray());
            BigInteger b2 = new BigInteger(uuid2.ToByteArray());

            long l1part1 = BitConverter.ToInt64(uuid1.ToByteArray(), 0); // Parts 1 and 2
            long l1part2 = BitConverter.ToInt64(uuid1.ToByteArray(), 8); // of uuid1.

            long l2part1 = BitConverter.ToInt64(uuid2.ToByteArray(), 0); // Parts 1 and 2
            long l2part2 = BitConverter.ToInt64(uuid2.ToByteArray(), 8); // of uuid2.

            long[] la1 = { l1part1, l1part2 }; // Parts 1 and 2 of uuid1.
            long[] la2 = { l2part1, l2part2 }; // Parts 1 and 2 of uuid2.

            int i1part1 = BitConverter.ToInt32(uuid1.ToByteArray(), 0);  // Parts 1, 2, 3
            int i1part2 = BitConverter.ToInt32(uuid1.ToByteArray(), 4);  // and 4
            int i1part3 = BitConverter.ToInt32(uuid1.ToByteArray(), 8);  // of
            int i1part4 = BitConverter.ToInt32(uuid1.ToByteArray(), 12); // uuid1.

            int i2part1 = BitConverter.ToInt32(uuid2.ToByteArray(), 0);  // Parts 1, 2, 3
            int i2part2 = BitConverter.ToInt32(uuid2.ToByteArray(), 4);  // and 4
            int i2part3 = BitConverter.ToInt32(uuid2.ToByteArray(), 8);  // of
            int i2part4 = BitConverter.ToInt32(uuid2.ToByteArray(), 12); // uuid2

            FastUuid fast1 = new FastUuid(uuid1.ToByteArray());
            FastUuid fast2 = new FastUuid(uuid2.ToByteArray());


            // UUID are equal (worse scenario)

            Stopwatch sw = new Stopwatch();
            bool result;

            sw.Reset(); sw.Start();
            for (int i = 0; i < numberOfChecks; i++)
            {
                result = (uuid1 == uuid2);
            }
            Console.WriteLine("- Guid.Equals: \t{0}", sw.Elapsed);

            sw.Reset(); sw.Start();
            for (int i = 0; i < numberOfChecks; i++)
            {
                result = Array.Equals(a1, a2);
            }
            Console.WriteLine("- Array.Equals(byte): \t{0}", sw.Elapsed);

            sw.Reset(); sw.Start();
            for (int i = 0; i < numberOfChecks; i++)
            {
                result = s1.Equals(s2);
            }
            Console.WriteLine("- String.Equals: \t{0}", sw.Elapsed);

            sw.Reset(); sw.Start();
            for (int i = 0; i < numberOfChecks; i++)
            {
                result = b1.Equals(b2);
            }
            Console.WriteLine("- BigInteger.Equals: \t{0}", sw.Elapsed);

            sw.Reset(); sw.Start();
            for (int i = 0; i < numberOfChecks; i++)
            {
                result = (l1part1 == l2part1 && l1part2 == l2part2);
            }
            Console.WriteLine("- Two long compare: \t{0}", sw.Elapsed);

            sw.Reset(); sw.Start();
            for (int i = 0; i < numberOfChecks; i++)
            {
                result = Array.Equals(la1, la2);
            }
            Console.WriteLine("- Array.Equals(long): \t{0}", sw.Elapsed);

            sw.Reset(); sw.Start();
            for (int i = 0; i < numberOfChecks; i++)
            {
                result = (i1part1 == i2part1 && i1part2 == i2part2 && i1part3 == i2part3 && i1part4 == i2part4);
            }
            Console.WriteLine("- Four int compare: \t{0}", sw.Elapsed);

            sw.Reset(); sw.Start();
            for (int i = 0; i < numberOfChecks; i++)
            {
                result = fast1.Equals(fast2);
            }
            Console.WriteLine("- FastUuid: \t{0}", sw.Elapsed);
        }

With the following results.

• Guid.Equals: 18.911 s
• Array.Equals(byte): 12.003 s
• String.Equals: 26.159 s
• BigInteger.Equals: 22.652 s
• Two long compare: 6.530 s <--- the fastest
• Array.Equals(long): 11.930 s
• Four int compare: 6.795 s
• FastUuid: 1m 26.636 s <--- the slowest

Why the FastUuid comparison is the slowest? Since the UUID should be the key to a Dictionary, is there a way to get the performance comparison between two long, and at the same time, implement the UUID with a small (16 byte) object/struct?

EDIT: Actually, the tests that I performed measure the performance of the comparison between two UUID, so they have little meaning to evaluate the performance of accessing a Dictionary, because when I invoke the ContainsKey method, it calculates the hash value of the UUID. Should I evaluate the performance in calculating the hash value of the Guid, String, FastUuid, etc.? How does the ContainsKey method work?

Answer 1

The default implementation of Equals for structs uses reflection for comparison, which is slower. (See more at ValueType.Equals on MSDN.)

You should override Equals and provide your own implementation:

public override bool Equals(object other)
{
    var fastOther = other as FastUuid?;
    return fastOther.HasValue &&
        fastOther.Value._part1 == _part1 &&
        fastOther.Value._part2 == _part2;
}

This won't fix the problem entirely, however. Since this is a struct you should also implement IEquatable<FastUuid> to avoid having to box/unbox the other item:

public bool Equals(FastUuid other)
{
    return
        other._part1 == _part1 &&
        other._part2 == _part2;
}

Equals is then just:

public override bool Equals(object other)
{
    var fastOther = other as FastUuid?;
    return fastOther.HasValue && Equals(fastOther.Value);
}

Answer 2

Structs use runtime reflection to determine what needs to be compared. Override Equals with your own comparison method to get much faster results.

see http://msdn.microsoft.com/en-us/library/2dts52z7.aspx

Update - Overriding equals for a struct ends up having boxing overheads (converting struct to object and back to struct), but if you define an Equals that takes the FastUuid struct directly, it runs much faster:

        public bool Equals(FastUuid value)
        {
            return this._part1 == value._part1
                && this._part2 == value._part2;
        }

This runs slightly faster than the Guid implementation on my box (4.2sec vs 5.8sec, but still slower than long comparison at 1.7sec).

ps. Pls be careful to run tests with release builds only, as debug builds can seriously affect timing.