GUID比较中的性能表现

Question

我阅读了这个问题和另一个问题。在这两个问题中的一个中，我还读到Guid结构由以下四个字段组成：Int32、Int16、Int16和Byte[8]，因此两个Guid之间的比较应该更快。

嗯，我只使用Guid结构来生成UUID，然后我只需要比较那些先前生成的UUID。因此，我想将每个快速生成的UUID转换为可比较的格式。

我使用了以下代码运行了一些测试（我从这个问题中获得了灵感）。

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

以下是翻译的结果：

以下是结果:

• Guid.Equals: 18.911 秒
• Array.Equals(byte): 12.003 秒
• String.Equals: 26.159 秒
• BigInteger.Equals: 22.652 秒
• Two long compare: 6.530 秒 <--- 最快
• Array.Equals(long): 11.930 秒
• Four int compare: 6.795 秒
• FastUuid: 1 分 26.636 秒 <--- 最慢

为什么 FastUuid 比较最慢？ 由于 UUID 应该是一个 Dictionary 的关键字, 是否有办法在实现 UUID 的同时, 使用一个小的 (16 字节) 对象 / 结构来获取两个 long 之间的性能比较?

编辑： 实际上，我执行的测试是衡量两个UUID之间比较性能的，因此它们对于评估访问字典的性能意义不大，因为当我调用ContainsKey方法时，它会计算UUID的哈希值。 我应该评估计算Guid、String、FastUuid等哈希值的性能吗？ ContainsKey方法是如何工作的？

- enzom83

---

给那位给提问者点踩的人，为什么呢？建设性的反馈总是受欢迎的！ - Will

你的测试结果相当值得怀疑。您正在测试出现一十亿个相同 GUID 的极不可能情况。Guid.Equals() 的优化是针对更有可能的情况，即它们将不会相等。 - Hans Passant

我设置了一亿个检查以获得更好的比较。 - enzom83

Answer 1

结构体的默认Equals实现使用反射进行比较，这种方法速度较慢。(更多信息请参见MSDN上的ValueType.Equals。)

你应该重写Equals并提供自己的实现：

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

然而，这并不能完全解决问题。由于这是一个结构体，您还应该实现IEquatable<FastUuid>以避免不得不装箱/拆箱其他项：

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

相等就是这样：

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

- porges

---

使用此解决方案，经过的时间增加：3分52秒。 - enzom83

抱歉，我也应该展示如何避免装箱另一个结构体。我已经更新了示例。 - porges

它应该比Array.Equals版本快，至少应该是。您使用的是64位还是32位？ - porges

对于我提供的第二个版本，在32位上获得了与Array.Equals大约相同的性能。 - porges

请注意，这在 .Net 4.5 中已不再适用：“如果当前实例和 obj 的所有字段都不是引用类型，则 Equals 方法对内存中的两个对象执行逐字节比较。否则，它使用反射来比较 obj 和此实例的相应字段。”- http://msdn.microsoft.com/en-us/library/2dts52z7.aspx - Peter

Answer 2

结构使用运行时反射来确定需要进行比较的内容。覆盖Equals方法并使用自己的比较方法，可以获得更快的结果。

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

更新 - 为结构体重写equals最终会有装箱开销（将结构体转换为对象，然后再转换回结构体），但如果您直接定义一个接受FastUuid结构体的Equals方法，则运行速度会更快：

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

在我的电脑上，这比Guid实现稍微快一点（4.2秒对比5.8秒，但仍然比长整型比较慢1.7秒）。

附注：请务必仅使用发布版本运行测试，因为调试版本会严重影响计时。

- Will

---

很好！在发布模式下，这些时间缩短了：

• 两个长整型比较：2.291秒
• 四个整型比较：2.245秒
• FastUuid：10.018秒

- enzom83