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);
}