5

我正在研究一个IEqualityComparer应该非常快速地比较原始类型数组的方法。我的计划是获取指向数组和memcmp它们的指针。像这样：

    public unsafe override bool Equals(T[] x, T[] y)
    {
        if (ReferenceEquals(x, y)) return true;
        if (x == null || y == null) return false;
        if (x.Length != y.Length) return false;

        var xArray = (Array)x;
        var yArray = (Array)y;
        fixed (void* xPtr = xArray) //compiler error 1
        fixed (T* yPtr = y) //compiler error 2
        {
            return memcmp(xPtr, yPtr, x.Length * this.elementSize);
        }
    }

固定语句不允许我固定Array或T[]。

有错误信息是：

1. Cannot implicitly convert type 'System.Array' to 'void*'
2. Cannot take the address of, get the size of, or declare a pointer to a managed type ('T')

现在，我实际上并不关心我是如何完成这项工作的（我并不致力于这种确切的方法）。我怎么能知道那是原始/ blittable 类型的memcmp两个？T[]T

我真的很想避免打开类型并为每个有趣的类型创建一个专门的（和重复的）代码版本。由于性能限制，任何类型的反射解决方案都不可行（是的，我真的需要这里的性能 - 没有过早的优化警告适用，因为它在 Stack Overflow 上是惯例）。

4

3 回答 3

5

我知道 T 是原始/blittable 类型

你知道的，编译器不知道。CLR 要求垃圾收集器不能再移动固定对象中的所有内容。对于一个数组，它包括它的数组元素。唯一符合条件的 T 是一种简单的值类型，即blittable。泛型没有给您一种将 T 限制为 blittable 类型的方法。

您通常会将 memcmp() 的参数声明为 byte[]。然后 pinvoke 编组器已经做了正确的事情，并将在调用 memcmp() 之前固定 byte[] 数组。但是，这也不起作用，因为您也无法轻松地将 T[] 转换为 byte[] 。您必须使用 GCHandle 固定自己。相应地将 memcmp() 参数声明为 IntPtr 而不是 byte[]。

实际上，可以工作的类型子集足够小，可以考虑简单地编写方法重载而不是泛​​型方法。现在，它使 pinvoke 编组器能够处理固定，相应地重载 memcmp() 函数声明。

于 2013-02-12T13:48:09.550 回答
2

您可以为要比较的每种数组编写单独的 P/Invoke 前端。我知道您并不是真的想专攻 T，但我认为开销并不算太大。

这有点小技巧，因为我为同一个 API 函数定义了多个具有不同签名的 P/Invoke 方法，但是通过这样做，我可以利用 P/Invoke 编组支持。

（请注意，只有当源数据确实是一个字节数组时，memcmp 的返回值的符号才有意义。如果给它一个整数数组，则应该只将返回值与零进行比较而忽略它的符号。它所暗示的顺序对整数没有意义。）

例如，以下代码为我打印以下内容（RELEASE 构建，而不是调试构建）：

MemCmp with ints took 00:00:08.0768666
ManagedMemCmp with ints took 00:00:10.3750453
MemCmp with bytes took 00:00:01.8740001
ManagedMemCmp with bytes took 00:00:09.2885763

请注意，byte[] 测试使用字节，因此比较的字节数是 int[] 测试使用的四分之一。托管代码进行相同数量的比较，因此相对要慢很多。

比较整数数组的时间之间并没有太大的差异，但是比较字节数组的时间差异很大。这向我表明，可能有一个托管优化，它使用fixed从字节数组中获取指向整数的指针，以便一次比较 4 个字节（对最后可能不适合的额外字节进行一些摆弄成一个整数）。

我还认为您可以编写一个多线程托管版本（使用“int *”优化来比较字节数组），这将比非托管 memcmp() 快得多，后者当然不是多线程的（据我所知）。

无论如何，这是我的测试代码。请记住，发布构建，而不是调试！

using System;
using System.Diagnostics;
using System.Runtime.InteropServices;


namespace Demo
{
    public static class Program
    {
        private static void Main(string[] args)
        {
            int[] a1 = new int[1000000];
            int[] a2 = new int[1000000];

            for (int i = 0; i < a1.Length-1; ++i)
            {
                a1[i] = i;
                a2[i] = i;
            }

            a1[a1.Length-1] = 1;
            a2[a1.Length-1] = 2;

            byte[] b1 = new byte[1000000];
            byte[] b2 = new byte[1000000];

            for (int i = 0; i < b1.Length-1; ++i)
            {
                b1[i] = (byte)i;
                b2[i] = (byte)i;
            }

            b1[a1.Length-1] = 1;
            b2[a1.Length-1] = 2;

            Stopwatch sw = Stopwatch.StartNew();
            testWithMemCmp(a1, a2);
            sw.Stop();
            Console.WriteLine("MemCmp with ints took " + sw.Elapsed);

            sw.Restart();
            testWithManagedMemCmp(a1, a2);
            sw.Stop();
            Console.WriteLine("ManagedMemCmp with ints took " + sw.Elapsed);

            sw.Restart();
            testWithMemCmp(b1, b2);
            sw.Stop();
            Console.WriteLine("MemCmp with bytes took " + sw.Elapsed);

            sw.Restart();
            testWithManagedMemCmp(b1, b2);
            sw.Stop();
            Console.WriteLine("ManagedMemCmp with bytes took " + sw.Elapsed);
        }

        private static void testWithMemCmp(int[] a1, int[] a2)
        {
            for (int j = 0; j < COUNT; ++j)
            {
                MemCmp(a1, a2);
            }
        }

        private static void testWithMemCmp(byte[] a1, byte[] a2)
        {
            for (int j = 0; j < COUNT; ++j)
            {
                MemCmp(a1, a2);
            }
        }

        private static void testWithManagedMemCmp(int[] a1, int[] a2)
        {
            for (int j = 0; j < COUNT; ++j)
            {
                ManagedMemCmp(a1, a2);
            }
        }

        private static void testWithManagedMemCmp(byte[] a1, byte[] a2)
        {
            for (int j = 0; j < COUNT; ++j)
            {
                ManagedMemCmp(a1, a2);
            }
        }

        public static bool ManagedMemCmp(int[] a1, int[] a2)
        {
            if (a1 == null || a2 == null || a1.Length != a2.Length)
            {
                throw new InvalidOperationException("Arrays are null or different lengths.");
            }

            for (int i = 0; i < a1.Length; ++i)
            {
                if (a1[i] != a2[i])
                {
                    return false;
                }
            }

            return true;
        }

        public static bool ManagedMemCmp(byte[] a1, byte[] a2)
        {
            if (a1 == null || a2 == null || a1.Length != a2.Length)
            {
                throw new InvalidOperationException("Arrays are null or different lengths.");
            }

            for (int i = 0; i < a1.Length; ++i)
            {
                if (a1[i] != a2[i])
                {
                    return false;
                }
            }


            return true;
        }

        public static bool MemCmp(byte[] a1, byte[] a2)
        {
            if (a1 == null || a2 == null || a1.Length != a2.Length)
            {
                throw new InvalidOperationException("Arrays are null or different lengths.");
            }

            return memcmp(a1, a2, new UIntPtr((uint)a1.Length)) == 0;
        }

        public static bool MemCmp(int[] a1, int[] a2)
        {
            if (a1 == null || a2 == null || a1.Length != a2.Length)
            {
                throw new InvalidOperationException("Arrays are null or different lengths.");
            }

            return memcmp(a1, a2, new UIntPtr((uint)(a1.Length * sizeof(int)))) == 0;
        }

        [DllImport("msvcrt.dll")]
        private static extern int memcmp(byte[] a1, byte[] a2, UIntPtr count);

        [DllImport("msvcrt.dll")]
        private static extern int memcmp(int[] a1, int[] a2, UIntPtr count);

        private const int COUNT = 10000;
    }
}
于 2013-02-12T14:47:55.273 回答
1

我同意 Daniel A. White 的评论，告诉您它可能不会导致性能提升，但会因为编组到非托管代码等的开销而导致性能下降。

话虽如此，您应该能够使用GCHandle.Alloc：

public unsafe bool Equals(T[] x, T[] y)
{
    if (ReferenceEquals(x, y)) return true;
    if (x == null || y == null) return false;
    if (x.Length != y.Length) return false;

    GCHandle handleOfX = default(GCHandle);
    GCHandle handleOfY = default(GCHandle);
    handleOfX = GCHandle.Alloc(x, GCHandleType.Pinned);
    handleOfY = GCHandle.Alloc(y, GCHandleType.Pinned);
    try
    {
        return memcmp(handleOfX.AddrOfPinnedObject(),
                      handleOfY.AddrOfPinnedObject(),
                      x.Length * this.elementSize);
    }
    finally
    {
        if(handleOfX != default(GCHandle)) handleOfX.Free();
        if(handleOfY != default(GCHandle)) handleOfY.Free();
    }
}
于 2013-02-12T13:19:41.637 回答