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')

今、私は実際にこれをどのように機能させるかは気にしません（私はこの正確なアプローチにコミットしていません）。それがプリミティブ/ブリット可能なタイプであることがわかっている場合、どうすればmemcmp2つできますか？T[]T

タイプをオンにして、興味深いタイプごとに特殊な（そして複製された）コードバージョンを作成することは本当に避けたいです。パフォーマンスの制約のため、どのような種類のリフレクションソリューションも機能しません（もちろん、ここでパフォーマンスが本当に必要です。StackOverflowでは通常のように、時期尚早の最適化警告は適用されません）。

4

3 に答える 3

5

T がプリミティブ/ブリット可能な型であることを知っている場所

あなたはそれを知っています、コンパイラはそれを知りません。CLRは、固定されたオブジェクト内のすべてのものをガベージ コレクターで移動できないようにすることを要求します。配列の場合、その配列要素が含まれます。適格となる T の種類は、 blittableである単純な値の型だけです。ジェネリックでは、T を blittable 型に制約する方法は提供されません。

通常、memcmp() の引数は byte[] として宣言します。pinvoke マーシャラーはすでに正しいことを行っており、memcmp() を呼び出す前に byte[] 配列を固定します。ただし、T[] を byte[] に簡単に変換することもできないため、これも機能しません。GCHandle でピン留めする必要があります。それに応じて、memcmp() 引数を byte[] ではなく IntPtr として宣言します。

機能する型のサブセットは、実際には、ジェネリック メソッドの代わりにメソッド オーバーロードを単純に記述することを検討するのに十分小さいです。これにより、pinvoke マーシャラーがピニングを処理し、それに応じて memcmp() 関数宣言をオーバーロードできるようになりました。

于 2013-02-12T13:48:09.550 に答える
2

比較する配列の種類ごとに個別の P/Invoke フロントエンドを作成できます。T に特化したくないのはわかっていますが、オーバーヘッドはそれほど大きくないと思います。

同じ API 関数に対して異なる署名を持つ複数の P/Invoke メソッドを定義しているため、これは少しハックですが、これを行うことで、P/Invoke マーシャリング サポートを活用できます。

(memcmp からの戻り値の符号は、ソース データが実際にバイトの配列である場合にのみ意味があることに注意してください。int の配列を指定する場合は、戻り値をゼロとのみ比較し、その符号を無視する必要があります。それが意味する順序付けは、int には意味がありません。)

たとえば、次のコードは次のように出力します (デバッグ ビルドではなくリリース ビルド)。

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[] テストが使用するバイト数の 4 分の 1 を比較していることに注意してください。マネージ コードは同じ数の比較を行うため、比較的遅くなります。

int の配列を比較する時間には大きな違いはありませんが、バイトの配列を比較する時間には大きな違いがあります。これは、一度に 4 バイトを比較するために、 fixedを使用してバイト配列から int へのポインターを取得する管理された最適化がある可能性があることを示唆しています (最後に収まらない余分なバイトをいじる必要があります)。 int に)。

また、マルチスレッド マネージド バージョン (「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 に答える