De/Interleave array fast in C#

Question

Szukam najszybszego sposobu de/przeplot bufora. Mówiąc dokładniej, mam do czynienia z danymi dźwiękowymi, więc staram się zoptymalizować czas poświęcony na dzielenie/łączenie kanałów i buforów FFT.

Obecnie używam pętli for z 2 zmiennymi indeksowymi dla każdej tablicy, więc tylko operacje plus, ale wszystkie sprawdzenia tablicy zarządzanej nie będą porównywać z metodą wskaźnika C.

Podobają mi się metody Buffer.BlockCopy i Array.Copy, które skracają dużo czasu podczas przetwarzania kanałów, ale nie ma możliwości, aby tablica miała niestandardowy indeks.

Próbowałem znaleźć sposób utworzenia maski tablicowej, gdzie byłaby to fałszywa tablica z niestandardowym indeksem, ale okazuje się to dwa razy wolniejsze, gdy używam jej w mojej operacji FFT. Sądzę, że istnieje wiele sztuczek optymalizacyjnych, które kompilator może ciągnąć podczas bezpośredniego dostępu do tablicy, ale nie można zoptymalizować dostępu za pośrednictwem indeksu klasy.

Nie chcę żadnego niebezpiecznego rozwiązania, chociaż z jego wyglądu może to być jedyny sposób na zoptymalizowanie tego typu operacji.

Dzięki.

Oto typu rzeczy robię teraz:

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

uruchomiony kilka testów i tu jest to kod badane:

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

i wyniki (rozmiar bufora = 2^17 iteracji numer czasowe na 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 uzyskałem podobne wyniki w każdym teście. Oczywiście kod niebezpieczny jest najszybszy, ale zdziwiłem się, widząc, że CLS nie mógł wykombinować, że może zrzucić kontrole indeksu, gdy ma do czynienia z poszarpaną tablicą. Może ktoś może wymyślić więcej sposobów na zoptymalizowanie moich testów.

Edytuj: Próbowałem rozwijania pętli z niebezpiecznym kodem i nie ma efektu. że próbował również optymalizacji pętli sposób odwijania:

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

Wyniki są również HIT-chybienie porównaniu Test 4 różnicą 1%. Test nr 4 to moja najlepsza droga do tej pory.

Jak powiedziałem jerryjvl, problem jest coraz CLS sprawdzić nie wskaźnik bufora wejściowego, ponieważ dodanie drugiego czek (& & przesunięcie < inout.Length) będzie zwalniać ...

Edycja 2 : Pobiegłem testów zanim w IDE, więc oto wyniki zewnątrz:

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 

Wygląda odwijanie pętli nie jest korzystna. Mój zoptymalizowany kod jest nadal moim najlepszym sposobem, z 10% różnicą w porównaniu do niebezpiecznego kodu. Gdybym tylko mógł powiedzieć kompilatorowi, że (i < buf.Length) implikuje to (przesunięcie < inout.Length), usunie to zaznaczenie (inout [offset]), a ja dostanę zasadniczo niebezpieczną wydajność.

Answer 2

Ponieważ nie ma wbudowaną funkcję, aby to zrobić, używając indeksów tablicy jest najszybsza operacja może myśleć. Takie wskaźniki i rozwiązania tylko pogarszają sytuację, wprowadzając wywołania metod i uniemożliwiając optymalizatorowi JIT zoptymalizowanie powiązanych sprawdzeń.

W każdym razie, sądzę, że twoja obecna metoda jest najszybszym rozwiązaniem, które nie może być używane przez użytkownika innego niż unsafe. Jeśli wydajność naprawdę ma dla ciebie znaczenie (co zwykle ma miejsce w aplikacjach do przetwarzania sygnałów), możesz wykonać całą pracę w C# unsafe (która jest wystarczająco szybka, prawdopodobnie porównywalna z C) i zawrzeć ją w metodzie, którą możesz wywołać ze swojego sejfu metody.

Answer 3

Myślę, że wielu czytelników zakwestionuje, dlaczego nie chcesz, aby niebezpieczne rozwiązanie dla czegoś takiego jak przetwarzanie dźwięku. To rodzaj rzeczy, która błaga o gorącą optymalizację i byłbym nieszczęśliwy wiedząc, że jest zmuszony przez vm.

Answer 4

Nie spowoduje to znacznego zwiększenia wydajności (około 20% zmierzyłem na moim komputerze), ale można rozważyć pewne rozwijanie pętli w typowych przypadkach. Jeśli większość czasu masz stosunkowo ograniczonej liczby kanałów:

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

Dopóki opuścić ogólny wariant zastępczy nie będzie ona obsługiwać dowolną liczbę kanałów, ale dostaniesz zastrzyk prędkości Jeśli to jest jednym z rozwiniętych wariantów.

Answer 5

Może jakiś rozwijanie w swoim własnym najlepszą odpowiedź:

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

To może trochę lepsze osiągi nadal.