De/Interleave array veloce in C#

Question

Sto cercando il modo più veloce per de/interleave un buffer. Per essere più specifici, mi occupo di dati audio, quindi sto cercando di ottimizzare il tempo che spendo per suddividere/combinare canali e buffer FFT.

Attualmente sto usando un ciclo for con 2 variabili di indice per ogni array, quindi solo le operazioni più, ma tutti i controlli di array gestiti non verranno confrontati con un metodo di puntatore C.

Mi piacciono i metodi Buffer.BlockCopy e Array.Copy, che tagliano molto tempo quando elaboro i canali, ma non c'è modo per un array di avere un indicizzatore personalizzato.

Stavo cercando di trovare un modo per creare una maschera di array, dove sarebbe un array falso con un indicizzatore personalizzato, ma che si rivela essere due volte più lento quando lo si utilizza nella mia operazione FFT. Immagino che ci siano molti trucchi di ottimizzazione che il compilatore può eseguire quando accede direttamente a un array, ma l'accesso tramite un indicizzatore di classe non può essere ottimizzato.

Non voglio una soluzione non sicura, anche se dall'aspetto, questo potrebbe essere l'unico modo per ottimizzare questo tipo di operazione.

Grazie.

Qui è il tipo di cosa che sto facendo in questo momento:

private float[][] DeInterleave(float[] buffer, int channels) 
{ 
    float[][] tempbuf = new float[channels][]; 
    int length = buffer.Length/channels; 
    for (int c = 0; c < channels; c++) 
    { 
     tempbuf[c] = new float[length]; 
     for (int i = 0, offset = c; i < tempbuf[c].Length; i++, offset += channels) 
      tempbuf[c][i] = buffer[offset]; 
    } 
    return tempbuf; 
} 

Answer 1

I corse alcuni test e qui è il codice che ho provato:

delegate(float[] inout) 
{ // My Original Code 
    float[][] tempbuf = new float[2][]; 
    int length = inout.Length/2; 
    for (int c = 0; c < 2; c++) 
    { 
     tempbuf[c] = new float[length]; 
     for (int i = 0, offset = c; i < tempbuf[c].Length; i++, offset += 2) 
      tempbuf[c][i] = inout[offset]; 
    } 
} 
delegate(float[] inout) 
{ // jerryjvl's recommendation: loop unrolling 
    float[][] tempbuf = new float[2][]; 
    int length = inout.Length/2; 
    for (int c = 0; c < 2; c++) 
     tempbuf[c] = new float[length]; 
    for (int ix = 0, i = 0; ix < length; ix++) 
    { 
     tempbuf[0][ix] = inout[i++]; 
     tempbuf[1][ix] = inout[i++]; 
    } 

} 
delegate(float[] inout) 
{ // Unsafe Code 
    unsafe 
    { 
     float[][] tempbuf = new float[2][]; 
     int length = inout.Length/2; 
     fixed (float* buffer = inout) 
      for (int c = 0; c < 2; c++) 
      { 
       tempbuf[c] = new float[length]; 
       float* offset = buffer + c; 
       fixed (float* buffer2 = tempbuf[c]) 
       { 
        float* p = buffer2; 
        for (int i = 0; i < length; i++, offset += 2) 
         *p++ = *offset; 
       } 
      } 
    } 
} 
delegate(float[] inout) 
{ // Modifying my original code to see if the compiler is not as smart as i think it is. 
    float[][] tempbuf = new float[2][]; 
    int length = inout.Length/2; 
    for (int c = 0; c < 2; c++) 
    { 
     float[] buf = tempbuf[c] = new float[length]; 
     for (int i = 0, offset = c; i < buf.Length; i++, offset += 2) 
      buf[i] = inout[offset]; 
    } 
} 

e risultati: (dimensione del buffer = 2^17, iterazioni numero temporizzate per test = 200)

Average for test #1:  0.001286 seconds +/- 0.000026 
Average for test #2:  0.001193 seconds +/- 0.000025 
Average for test #3:  0.000686 seconds +/- 0.000009 
Average for test #4:  0.000847 seconds +/- 0.000008 

Average for test #1:  0.001210 seconds +/- 0.000012 
Average for test #2:  0.001048 seconds +/- 0.000012 
Average for test #3:  0.000690 seconds +/- 0.000009 
Average for test #4:  0.000883 seconds +/- 0.000011 

Average for test #1:  0.001209 seconds +/- 0.000015 
Average for test #2:  0.001060 seconds +/- 0.000013 
Average for test #3:  0.000695 seconds +/- 0.000010 
Average for test #4:  0.000861 seconds +/- 0.000009 

I ha ottenuto risultati simili ogni test. Ovviamente il codice non sicuro è il più veloce, ma sono stato sorpreso di vedere che il CLS non riusciva a capire che poteva eliminare i controlli dell'indice quando si trattava di array frastagliato. Forse qualcuno può pensare a più modi per ottimizzare i miei test.

Modifica: Ho provato il ciclo di srotolamento con il codice non sicuro e non ha avuto alcun effetto. Ho anche provato ottimizzare il metodo di svolgimento ciclo:

delegate(float[] inout) 
{ 
    float[][] tempbuf = new float[2][]; 
    int length = inout.Length/2; 
    float[] tempbuf0 = tempbuf[0] = new float[length]; 
    float[] tempbuf1 = tempbuf[1] = new float[length]; 

    for (int ix = 0, i = 0; ix < length; ix++) 
    { 
     tempbuf0[ix] = inout[i++]; 
     tempbuf1[ix] = inout[i++]; 
    } 
} 

I risultati sono anche un colpo-miss prova rispetto # 4 con la differenza di 1%. Il test n. 4 è il mio miglior modo per andare, finora.

Come ho detto jerryjvl, il problema è sempre la CLS di non indice di controllare il buffer di ingresso, dal momento che l'aggiunta di un secondo controllo (& & compensato < inout.Length) sarà rallentarlo ...

Edit 2 : ho eseguito i test prima nell'IDE, ecco i risultati al di fuori:

2^17 items, repeated 200 times 
****************************************** 
Average for test #1:  0.000533 seconds +/- 0.000017 
Average for test #2:  0.000527 seconds +/- 0.000016 
Average for test #3:  0.000407 seconds +/- 0.000008 
Average for test #4:  0.000374 seconds +/- 0.000008 
Average for test #5:  0.000424 seconds +/- 0.000009 

2^17 items, repeated 200 times 
****************************************** 
Average for test #1:  0.000547 seconds +/- 0.000016 
Average for test #2:  0.000732 seconds +/- 0.000020 
Average for test #3:  0.000423 seconds +/- 0.000009 
Average for test #4:  0.000360 seconds +/- 0.000008 
Average for test #5:  0.000406 seconds +/- 0.000008 


2^18 items, repeated 200 times 
****************************************** 
Average for test #1:  0.001295 seconds +/- 0.000036 
Average for test #2:  0.001283 seconds +/- 0.000020 
Average for test #3:  0.001085 seconds +/- 0.000027 
Average for test #4:  0.001035 seconds +/- 0.000025 
Average for test #5:  0.001130 seconds +/- 0.000025 

2^18 items, repeated 200 times 
****************************************** 
Average for test #1:  0.0seconds +/- 0.000026 
Average for test #2:  0.001319 seconds +/- 0.000023 
Average for test #3:  0.001309 seconds +/- 0.000025 
Average for test #4:  0.001191 seconds +/- 0.000026 
Average for test #5:  0.001196 seconds +/- 0.000022 

Test#1 = My Original Code 
Test#2 = Optimized safe loop unrolling 
Test#3 = Unsafe code - loop unrolling 
Test#4 = Unsafe code 
Test#5 = My Optimized Code 

Sembra svolgimento del ciclo non è favorevole. Il mio codice ottimizzato è ancora il mio modo migliore di andare e con solo il 10% di differenza rispetto al codice non sicuro. Se solo potessi dire al compilatore che (i < buf.Length) implica che (offset < inout.Length), lascerà cadere il controllo (inout [offset]) e fondamentalmente otterrò le prestazioni non sicure.

Answer 2

Poiché non c'è costruito in funzione per farlo, utilizzando indici di matrice è l'operazione più veloce si potrebbe pensare. Gli indicizzatori e le soluzioni di questo tipo peggiorano solo le cose introducendo le chiamate ai metodi e impedendo all'ottimizzatore JIT di essere in grado di ottimizzare i controlli associati.

In ogni caso, penso che il tuo metodo attuale sia la soluzione più rapida non- unsafe che potresti utilizzare. Se le prestazioni sono importanti per te (cosa che di solito accade nelle applicazioni di elaborazione dei segnali), puoi fare tutto in unsafe C# (che è abbastanza veloce, probabilmente paragonabile a C) e avvolgerlo in un metodo che chiameresti dalla tua cassaforte metodi.

Answer 3

Penso che molti lettori si chiederanno perché non si desidera una soluzione non sicura per qualcosa come l'elaborazione audio. È il tipo di cosa che implora l'ottimizzazione a sangue caldo e peronalmente sarei infelice sapendo che è stato forzato attraverso un vm.

Answer 4

Non ti darà un grande incremento di prestazioni (ho misurato approssimativamente il 20% sulla mia macchina), ma potresti considerare lo srotolamento del loop per casi comuni. Se la maggior parte del tempo che avete un numero relativamente limitato di canali:

static private float[][] Alternative(float[] buffer, int channels) 
{ 
    float[][] result = new float[channels][]; 
    int length = buffer.Length/channels; 
    for (int c = 0; c < channels; c++) 
     result[c] = new float[length]; 

    int i = 0; 
    if (channels == 8) 
    { 
     for (int ix = 0; ix < length; ix++) 
     { 
      result[0][ix] = buffer[i++]; 
      result[1][ix] = buffer[i++]; 
      result[2][ix] = buffer[i++]; 
      result[3][ix] = buffer[i++]; 
      result[4][ix] = buffer[i++]; 
      result[5][ix] = buffer[i++]; 
      result[6][ix] = buffer[i++]; 
      result[7][ix] = buffer[i++]; 
     } 
    } 
    else 
     for (int ix = 0; ix < length; ix++) 
      for (int ch = 0; ch < channels; ch++) 
       result[ch][ix] = buffer[i++]; 


    return result; 
} 

Finché si lascia la variante generale ripiego lì occuperemo di gestire qualsiasi numero di canali, ma si otterrà un aumento di velocità se è una delle varianti srotolate.

Answer 5

Forse alcuni srotolamento nel proprio migliore risposta:

delegate(float[] inout) 
{ 
    unsafe 
    { 
     float[][] tempbuf = new float[2][]; 
     int length = inout.Length/2; 

     fixed (float* buffer = inout) 
     { 
      float* pbuffer = buffer; 

      tempbuf[0] = new float[length]; 
      tempbuf[1] = new float[length]; 

      fixed (float* buffer0 = tempbuf[0]) 
      fixed (float* buffer1 = tempbuf[1]) 
      { 
       float* pbuffer0 = buffer0; 
       float* pbuffer1 = buffer1; 

       for (int i = 0; i < length; i++) 
       { 
        *pbuffer0++ = *pbuffer++; 
        *pbuffer1++ = *pbuffer++; 
       } 
      } 
     } 
    } 
} 

Questo potrebbe avere un po 'più di prestazioni ancora.