modo più veloce per operare su singoli byte in un int

Question

ho scoperto che la mia domanda spende il 25% del suo tempo a fare questo in un ciclo:

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

Come posso migliorare le prestazioni di questo metodo? Le mie idee finora:

1. Più ovviamente, questo trarrebbe vantaggio da SIMD, ma supponiamo che io non voglia andare lì perché è un po 'una seccatura.
2. Lo stesso vale per le cose di livello inferiore (chiamando una libreria C, eseguendo su GPGPU)
3. Multithreading: lo userò.

Edit: Per comodità, un po 'di codice di prova che riflette l'ambiente reale e dei casi d'uso. (In realtà ancora più dati sono coinvolti, ei dati non sono confrontati in singoli blocchi di grandi dimensioni, ma in molti pezzi di diversi KB ciascuno.)

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

che produce per me (in esecuzione come x64 di uscita su un 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

maggior parte, ovviamente, questo sarebbe beneficiare di SIMD, ma supponiamo che non voglio andare lì perché è un po 'di fastidio.

Evitatelo se volete, ma in realtà è abbastanza ben supportato direttamente da C#. A corto di offloading alla GPU, mi aspetto che questo sia di gran lunga il più grande vincitore di prestazioni se l'algoritmo più grande si presta all'elaborazione SIMD.

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

Multithreading

Certo, utilizzare un thread per core CPU. Puoi anche utilizzare costrutti come Parallel.For e consentire a .NET di specificare quanti thread utilizzare. È abbastanza buono, ma dato che sai che questo è sicuramente legato alla CPU, potresti ottenere (o meno) un risultato più ottimale gestendo i thread tu stesso.

Per quanto riguarda l'accelerazione del blocco di codice effettivo, potrebbe essere più rapido utilizzare bit masking e bit shifting per far funzionare i singoli valori anziché utilizzare i puntatori. Questo ha l'ulteriore vantaggio di non aver bisogno di un blocco di codice non sicuro, ad es.

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

Answer 2

Oltre alle opzioni SIMD già citati e l'esecuzione di più operazioni in parallelo, hai provato a riferimento alcune possibili varianti di implementazione sul tema? Come alcune delle opzioni di seguito.

ho quasi dimenticato di citare un'ottimizzazione molto importante:

• Aggiungi un using System.Runtime.CompilerServices;
• aggiungere l'attributo [MethodImpl(MethodImplOptions.AggressiveInlining)] al vostro metodo.

Ti piace questa:

[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

ho cercato di ridurre il numero di istruzioni IL (sembra che sia unica opzione per thread singolo, il codice no-SIMD). Questo codice funziona il 35% più velocemente rispetto alla descrizione sulla mia macchina. Inoltre stavo pensando che potreste provare a generare da solo l'istruzione di IL tramite la classe statica di Emit. Può darti più precisione.

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