De/Interleave array rápido en C#

Question

Estoy buscando la forma más rápida de de/interleave un buffer. Para ser más específicos, estoy tratando con datos de audio, así que estoy tratando de optimizar el tiempo que dedico a dividir/combinar canales y búferes FFT.

Actualmente estoy usando un bucle for con 2 variables de índice para cada matriz, por lo que solo se usan más operaciones, pero todas las comprobaciones de la matriz administrada no se pueden comparar con un método de puntero C.

Me gustan los métodos Buffer.BlockCopy y Array.Copy, que cortan mucho tiempo cuando proceso canales, pero no hay forma de que una matriz tenga un indexador personalizado.

Estaba tratando de encontrar una forma de hacer una máscara de matriz, donde sería una matriz falsa con un indexador personalizado, pero que resulta ser dos veces más lenta cuando la utilizo en mi operación de FFT. Supongo que hay muchos trucos de optimización que el compilador puede obtener al acceder a una matriz directamente, pero no se puede optimizar el acceso a través de un indexador de clases.

No quiero una solución insegura, aunque por lo que parece, esa podría ser la única forma de optimizar este tipo de operación.

Gracias.

Aquí es el tipo de cosa que estoy haciendo ahora:

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 corrieron algunas pruebas y aquí es el código Probé:

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

y resultados: (tamaño de buffer = 2^17, iteraciones número temporizados por prueba = 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 obtuve resultados similares en cada prueba. Obviamente, el código inseguro es el más rápido, pero me sorprendió ver que el CLS no podía darse cuenta de que podía soltar las comprobaciones de índice cuando se trataba de una matriz dentada. Tal vez alguien pueda pensar en más formas de optimizar mis pruebas.

Edit: He intentado desenrollar el bucle con el código inseguro y no tuvo ningún efecto. También probé la optimización del método de desenrollado del bucle:

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

Los resultados son también un éxito-miss comparación prueba # 4 con 1% de diferencia. La prueba n. ° 4 es mi mejor opción, hasta ahora.

Como me dijeron que jerryjvl, el problema es conseguir el CLS a no índice de comprobar la memoria intermedia de entrada, ya que la adición de un segundo control (& & desplazamiento < inout.Length) va a reducir la velocidad ...

Edición 2 : me encontré con las pruebas antes en el IDE, así que aquí están los resultados exterior:

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 

Parece que el desenrollado del bucle no es favorable. Mi código optimizado sigue siendo mi mejor opción y con solo un 10% de diferencia en comparación con el código inseguro. Si solo pudiera decirle al compilador que (i < buf.Length) implica que (offset < inout.Length), dejará caer el cheque (en [offset]) y básicamente obtendré el rendimiento inseguro.

Answer 2

Como no hay ninguna función integrada de hacerlo, utilizando los índices de matriz es la operación más rápida que usted podría pensar. Los indexadores y soluciones de este tipo solo empeorarán las cosas al introducir llamadas a métodos y evitar que el optimizador JIT pueda optimizar las comprobaciones encuadernadas.

De todos modos, creo que su método actual es la solución más rápida que no sea unsafe que podría estar utilizando. Si el rendimiento realmente le importa (lo que generalmente ocurre en las aplicaciones de procesamiento de señales), puede hacerlo todo en unsafe C# (que es lo suficientemente rápido, probablemente comparable con C) y envolverlo en un método que llamaría desde su caja fuerte métodos.

Answer 3

Creo que muchos lectores se preguntan por qué no quieres una solución insegura para algo así como el procesamiento de audio. Es el tipo de cosas que piden optimización de sangre caliente y yo sería peronalmente infeliz sabiendo que se está forzando a través de un vm.

Answer 4

No le proporcionará un gran impulso en el rendimiento (medí aproximadamente el 20% en mi máquina), pero podría considerar la posibilidad de que algún bucle se desenrolle para casos comunes. Si la mayoría de las veces tienen un número relativamente limitado de canales:

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

Como siempre y cuando salga la variante de repliegue general de allí se va a manejar cualquier número de canales, pero obtendrá un aumento de velocidad si es una de las variantes desenrolladas.

Answer 5

Tal vez algunos desenrollado en su propio mejor respuesta:

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

Esto podría ser un poco más rendimiento todavía.