.Net, самое эффективное сравнение

Question

У меня есть 2 массива из N объектов, х и у. Объекты в штучной упаковке. В обоих массивах нет нулевых элементов. 1> = N <50 </p>

Я могу сравнить их со следующим кодом:

for (var i = 0; i < N; i++)
{
    if (!xs[i].Equals(ys[i]))
    {
        return false;
    }
}

return true;

Мой вопрос: используя трюки .Net JIT или CLR или какое-то преобразование, могу ли я оптимизировать этот алгоритм дальше?

Answer 1

Если они не в штучной упаковке, у вас есть еще несколько вариантов, также это в основном только начнет платить с большими массивами.

Также, как упоминалось в комментариях, вы можете использовать параллель. Но plinq и TPL, вероятно, не дадут вам никакой положительной выгоды с такими маленькими массивами, и определенно дадут гораздо больше накладных расходов.

public static unsafe bool UnsafeCompare(int[] ary1, int[] ary2)
{
   fixed (int* pAry1 = ary1, pAry2 = ary2)
   {
      var pLen = pAry1 + ary1.Length;
      for (int* p1 = pAry1, p2 = pAry2; p1 < pLen; p1++, p2++)
         if (*p1 != *p2)
            return false;
   }
   return true;
}

или

[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)]
static extern int memcmp(IntPtr b1, IntPtr b2, IntPtr count);

public static unsafe bool UnsafeCompare2(int[] ary1, int[] ary2)
{
   fixed (int* pAry1 = ary1, pAry2 = ary2)
   {
      return memcmp((IntPtr)pAry1, (IntPtr)pAry2, (IntPtr)(ary2.Length * sizeof(int))) == 0;
   }
}

Во всяком случае, если вы действительно после выступления, узнайте, что работает для вас

Просто интересная заметка, это источник для memcmp (или достаточно близко)

memcmp (const PTR str1, const PTR str2, size_t count)
{
  register const unsigned char *s1 = (const unsigned char*)str1;
  register const unsigned char *s2 = (const unsigned char*)str2;

  while (count-- > 0)
    {
      if (*s1++ != *s2++)
      return s1[-1] < s2[-1] ? -1 : 1;
    }
  return 0;
}

Тесты

Возьмите это с крошкой соли, однако эти тесты были проведены 100 000 раз, чтобы попытаться выявить тонкие различия.

   ----------------------------------------------------------------------------
Mode             : Release (64Bit)
Test Framework   : .NET Framework 4.7.1 (CLR 4.0.30319.42000)
----------------------------------------------------------------------------
Operating System : Microsoft Windows 10 Pro
Version          : 10.0.17134
----------------------------------------------------------------------------
CPU Name         : Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
Description      : Intel64 Family 6 Model 42 Stepping 7
Cores (Threads)  : 4 (8)      : Architecture  : x64
Clock Speed      : 3401 MHz   : Bus Speed     : 100 MHz
L2Cache          : 1 MB       : L3Cache       : 8 MB
----------------------------------------------------------------------------

Результаты

--- Standard input ------------------------------------------------------------
| Value    |    Average |    Fastest |    Cycles | Garbage | Test |      Gain |
--- Scale 5 ---------------------------------------------------- Time 0.475 ---
| Unsafe   |  54.271 ns |   0.000 ns |   1.850 K | 0.000 B | Pass |   16.95 % |
| Original |  65.349 ns |   0.000 ns |   1.820 K | 0.000 B | Base |    0.00 % |
| Memcmp   | 143.527 ns |   0.000 ns |   1.977 K | 0.000 B | Pass | -119.63 % |
--- Scale 50 --------------------------------------------------- Time 0.483 ---
| Unsafe   |  78.542 ns |   0.000 ns |   1.936 K | 0.000 B | Pass |   36.69 % |
| Original | 124.064 ns |   0.000 ns |   2.038 K | 0.000 B | Base |    0.00 % |
| Memcmp   | 181.076 ns |   0.000 ns |   2.066 K | 0.000 B | Pass |  -45.95 % |
--- Scale 500 -------------------------------------------------- Time 0.620 ---
| Memcmp   | 445.434 ns | 300.000 ns |   3.044 K | 0.000 B | Pass |   44.14 % |
| Unsafe   | 501.585 ns | 300.000 ns |   3.341 K | 0.000 B | Pass |   37.10 % |
| Original | 797.435 ns | 300.000 ns |   4.291 K | 0.000 B | Base |    0.00 % |
--- Scale 5,000 ------------------------------------------------ Time 2.172 ---
| Memcmp   |   3.519 µs |   2.701 µs |  13.625 K | 0.000 B | Pass |   46.95 % |
| Unsafe   |   5.110 µs |   4.502 µs |  19.084 K | 0.000 B | Pass |   22.96 % |
| Original |   6.633 µs |   5.703 µs |  24.364 K | 0.000 B | Base |    0.00 % |
--- Scale 50,000 ---------------------------------------------- Time 25.561 ---
| Memcmp   |  52.378 µs |  35.422 µs | 180.681 K | 0.000 B | Pass |   34.55 % |
| Unsafe   |  74.634 µs |  49.832 µs | 257.216 K | 0.000 B | Pass |    6.74 % |
| Original |  80.031 µs |  62.740 µs | 274.704 K | 0.000 B | Base |    0.00 % |
--- Scale 500,000 --------------------------------------------- Time 38.306 ---
| Memcmp   | 505.916 µs | 447.289 µs |   1.726 M | 0.000 B | Pass |   37.20 % |
| Unsafe   | 662.644 µs | 590.781 µs |   2.262 M | 0.000 B | Pass |   17.75 % |
| Original | 805.634 µs | 675.736 µs |   2.748 M | 0.000 B | Base |    0.00 % |
-------------------------------------------------------------------------------