Самый быстрый способ для работы на отдельных байтов в Int

Question

я обнаружил, что мое приложение тратит 25% своего времени, делая это в цикле:

private static int Diff (int c0, int c1) 
{ 
    unsafe { 
     byte* pc0 = (byte*) &c0; 
     byte* pc1 = (byte*) &c1; 
     int d0 = pc0[0] - pc1[0]; 
     int d1 = pc0[1] - pc1[1]; 
     int d2 = pc0[2] - pc1[2]; 
     int d3 = pc0[3] - pc1[3]; 
     d0 *= d0; 
     d1 *= d1; 
     d2 *= d2; 
     d3 *= d3; 
     return d0 + d1 + d2 + d3; 
    } 
} 

Как я могу улучшить производительность этого метода? Мои идеи до сих пор:

1. Очевидно, что это выиграет от SIMD, но предположим, что я не хочу туда ехать, потому что это немного хлопот.
2. То же самое относится к материалам нижнего уровня (вызов библиотеки C, выполняющейся на GPGPU)
3. Многопоточность - я буду использовать это.

Edit: Для вашего удобства, некоторые тестовый код, который отражает реальную среду и случай использования. (На самом деле даже больше данных участвуют, и данные не сравниваются в отдельных крупных блоках, но и во многих кусках нескольких кБ каждого.)

public static class ByteCompare 
{ 
    private static void Main() 
    { 
     const int n = 1024 * 1024 * 20; 
     const int repeat = 20; 
     var rnd = new Random (0); 

     Console.Write ("Generating test data... "); 
     var t0 = Enumerable.Range (1, n) 
      .Select (x => rnd.Next (int.MinValue, int.MaxValue)) 
      .ToArray(); 
     var t1 = Enumerable.Range (1, n) 
      .Select (x => rnd.Next (int.MinValue, int.MaxValue)) 
      .ToArray(); 
     Console.WriteLine ("complete."); 
     GC.Collect (2, GCCollectionMode.Forced); 
     Console.WriteLine ("GCs: " + GC.CollectionCount (0)); 

     { 
      var sw = Stopwatch.StartNew(); 
      long res = 0; 
      for (int reps = 0; reps < repeat; reps++) { 
       for (int i = 0; i < n; i++) { 
        int c0 = t0[i]; 
        int c1 = t1[i]; 
        res += ByteDiff_REGULAR (c0, c1); 
       } 
      } 
      sw.Stop(); 
      Console.WriteLine ("res=" + res + ", t=" + sw.Elapsed.TotalSeconds.ToString ("0.00") + "s - ByteDiff_REGULAR"); 
     } 
     { 
      var sw = Stopwatch.StartNew(); 
      long res = 0; 
      for (int reps = 0; reps < repeat; reps++) { 
       for (int i = 0; i < n; i++) { 
        int c0 = t0[i]; 
        int c1 = t1[i]; 
        res += ByteDiff_UNSAFE (c0, c1); 
       } 
      } 
      sw.Stop(); 
      Console.WriteLine ("res=" + res + ", t=" + sw.Elapsed.TotalSeconds.ToString ("0.00") + "s - ByteDiff_UNSAFE_PTR"); 
     } 

     Console.WriteLine ("GCs: " + GC.CollectionCount (0)); 
     Console.WriteLine ("Test complete."); 
     Console.ReadKey (true); 
    } 

    public static int ByteDiff_REGULAR (int c0, int c1) 
    { 
     var c00 = (byte) (c0 >> (8 * 0)); 
     var c01 = (byte) (c0 >> (8 * 1)); 
     var c02 = (byte) (c0 >> (8 * 2)); 
     var c03 = (byte) (c0 >> (8 * 3)); 
     var c10 = (byte) (c1 >> (8 * 0)); 
     var c11 = (byte) (c1 >> (8 * 1)); 
     var c12 = (byte) (c1 >> (8 * 2)); 
     var c13 = (byte) (c1 >> (8 * 3)); 
     var d0 = (c00 - c10); 
     var d1 = (c01 - c11); 
     var d2 = (c02 - c12); 
     var d3 = (c03 - c13); 
     d0 *= d0; 
     d1 *= d1; 
     d2 *= d2; 
     d3 *= d3; 
     return d0 + d1 + d2 + d3; 
    } 

    private static int ByteDiff_UNSAFE (int c0, int c1) 
    { 
     unsafe { 
      byte* pc0 = (byte*) &c0; 
      byte* pc1 = (byte*) &c1; 
      int d0 = pc0[0] - pc1[0]; 
      int d1 = pc0[1] - pc1[1]; 
      int d2 = pc0[2] - pc1[2]; 
      int d3 = pc0[3] - pc1[3]; 
      d0 *= d0; 
      d1 *= d1; 
      d2 *= d2; 
      d3 *= d3; 
      return d0 + d1 + d2 + d3; 
     } 
    } 
} 

, который дает мне (работают как x64 версия на i5):

Generating test data... complete. 
GCs: 8 
res=18324555528140, t=1.46s - ByteDiff_REGULAR 
res=18324555528140, t=1.15s - ByteDiff_UNSAFE 
res=18324555528140, t=1.73s - Diff_Alex1 
res=18324555528140, t=1.63s - Diff_Alex2 
res=18324555528140, t=3.59s - Diff_Alex3 
res=18325828513740, t=3.90s - Diff_Alex4 
GCs: 8 
Test complete. 

Answer 1

Совершенно очевидно, что это было бы полезно SIMD, но давайте предположим, что я не хочу идти туда, потому что это немного хлопот.

Удалите его, если хотите, но на самом деле он довольно хорошо поддерживается непосредственно с C#. Если не считать разгрузки на GPU, я бы ожидал, что это будет самым большим выигрышем в производительности, если более крупный алгоритм поддается обработке SIMD.

http://www.drdobbs.com/architecture-and-design/simd-enabled-vector-types-with-c/240168888

Многопоточность

Конечно, использовать один поток для каждого ядра процессора. Вы также можете использовать конструкции, подобные Parallel.For, и пусть .NET определяет, сколько потоков используется. Это очень хорошо, но, поскольку вы знаете, что это, безусловно, связано с процессором, вы можете (или не можете) получить более оптимальный результат, управляя потоками самостоятельно.

Что касается ускорения фактического кодового блока, возможно, более быстрое использование битовой маскировки и смещения битов, чтобы заставить отдельные значения работать, а не использовать указатели. Это имеет дополнительное преимущество, что вам не нужен небезопасный блок кода, например.

byte b0_leftmost = (c0 & 0xff000000) >> 24; 

Answer 2

Помимо уже упомянутых опций SIMD и параллельной работы нескольких параллельных операций, вы попытались сравнить некоторые возможные варианты реализации темы? Как некоторые из нижеперечисленных вариантов.

я почти забыл упомянуть очень важную оптимизацию:

• Добавить в корзину Или using System.Runtime.CompilerServices;
• Добавьте атрибут [MethodImpl(MethodImplOptions.AggressiveInlining)] к вашему методу.

Как это:

[MethodImpl(MethodImplOptions.AggressiveInlining)] 
private static int Diff(int c0, int c1) 
{ 
    unsafe 
    { 
     byte* pc0 = (byte*)&c0; 
     byte* pc1 = (byte*)&c1; 
     int sum = 0; 
     int dif = 0; 
     for (var i = 0; i < 4; i++, pc0++, pc1++) 
     { 
      dif = *pc0 - *pc1; 
      sum += (dif * dif); 
     } 
     return sum; 
    } 
} 

[MethodImpl(MethodImplOptions.AggressiveInlining)] 
private static int Diff(int c0, int c1) 
{ 
    unchecked 
    { 
     int sum = 0; 
     int dif = 0; 
     for (var i = 0; i < 4; i++) 
     { 
      dif = (c0 & 0xFF) - (c1 & 0xFF); 
      c0 >>= 8; 
      c1 >>= 8; 
      sum += (dif * dif); 
     } 
     return sum; 
    } 
} 

[MethodImpl(MethodImplOptions.AggressiveInlining)] 
private static int Diff(int c0, int c1) 
{ 
    unsafe 
    { 
     int* difs = stackalloc int[4]; 
     byte* pc0 = (byte*)&c0; 
     byte* pc1 = (byte*)&c1; 
     difs[0] = pc0[0] - pc1[0]; 
     difs[1] = pc0[1] - pc1[1]; 
     difs[2] = pc0[2] - pc1[2]; 
     difs[3] = pc0[3] - pc1[3]; 
     return difs[0] * difs[0] + difs[1] * difs[1] + difs[2] * difs[2] + difs[3] * difs[3]; 
    } 
} 

[MethodImpl(MethodImplOptions.AggressiveInlining)] 
private static int Diff(int c0, int c1) 
{ 
    unsafe 
    { 
     int* difs = stackalloc int[4]; 
     difs[0] = (c0 >> 24) - (c1 >> 24); 
     difs[1] = ((c0 >> 16) & 0xFF) - ((c1 >> 16) & 0xFF); 
     difs[2] = ((c0 >> 8) & 0xFF) - ((c1 >> 8) & 0xFF); 
     difs[3] = (c0 & 0xFF) - (c1 & 0xFF); 
     return difs[0] * difs[0] + difs[1] * difs[1] + difs[2] * difs[2] + difs[3] * difs[3]; 
    } 
} 

Answer 3

Я пытался уменьшить кол инструкции IL (похоже, это единственный вариант для однопоточный, не-SIMD-код). Этот код работает на 35% быстрее, чем в описании на моей машине. Также я думал, что вы можете попытаться генерировать IL-инструкцию самостоятельно через статический класс Emit. Это может дать вам больше точности.

[MethodImpl(MethodImplOptions.AggressiveInlining)] 
private static int ByteDiff_UNSAFE_2 (int c0, int c1) 
{ 
    unsafe { 
     byte* pc0 = (byte*) &c0; 
     byte* pc1 = (byte*) &c1; 
     int d0 = pc0[0] - pc1[0]; 
     d0 *= d0; 
     int d1 = pc0[1] - pc1[1]; 
     d0 += d1 * d1; 
     int d2 = pc0[2] - pc1[2]; 
     d0 += d2 * d2; 
     int d3 = pc0[3] - pc1[3]; 
     return d0 + d3 * d3; 
    } 
}