De / Interleave array fast in C#

Question

Hi guys,

I am looking for the fastest way to de/interleave a buffer. To be more specific, I am dealing with audio data, so I am trying to optimize the time I spend on splitting/combining channels and FFT buffers.

Currently I am using a for loop with 2 index variables for each array, so only plus operations, but all the managed array checks will not compare to a C pointer method.

I like the Buffer.BlockCopy and Array.Copy methods, which cut a lot of time when I process channels, but there is no way for an array to have a custom indexer.

I was trying to find a way to make an array mask, where it would be a fake array with a custom indexer, but that proves to be two times slower when using it in my FFT operation. I guess there are a lot of optimization tricks the compiler can pull when accessing an array directly, but accessing through a class indexer cannot be optimized.

I do not want an unsafe solution, although from the looks of it, that might be the only way to optimize this type of operation.

Thanks.

Here is the type of thing I'm doing right now:

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

As there's no built in function to do that, using array indexes is the fastest operation you could think of. Indexers and solutions like that only make things worse by introducing method calls and preventing the JIT optimizer to be able to optimize bound checks.

Anyway, I think your current method is the fastest non-unsafe solution you could be using. If performance really matter to you (which usually does in signal processing applications), you can do the whole thing in unsafe C# (which is fast enough, probably comparable with C) and wrap it in a method that you'd call from your safe methods.

Answer 2

I think a lot of readers would question why you don't want an unsafe solution for something like audio processing. It's the type of thing that begs for hot-blooded optimization and I would peronally be unhappy knowing it's being forced through a vm.

Answer 3

It's not going to get you a major performance boost (I roughly measured 20% on my machine), but you could consider some loop unrolling for common cases. If most of the time you have a relatively limited number of channels:

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

As long as you leave the general fallback variant there it'll handle any number of channels, but you'll get a speed boost if it is one of the unrolled variants.

Answer 4

I ran some tests and here is the code I tested:

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

and results: (buffer size = 2^17, number iterations timed 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 got similar results every test. Obviously the unsafe code is the fastest, but I was surprised to see that the CLS couldn't figure out that that it can drop the index checks when dealing with jagged array. Maybe someone can think of more ways to optimize my tests.

Edit: I tried loop unrolling with the unsafe code and it didn't have an effect. I also tried optimizing the loop unrolling method:

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

The results are also a hit-miss compared test#4 with 1% difference. Test #4 is my best way to go, so far.

As I told jerryjvl, the problem is getting the CLS to not index check the input buffer, since adding a second check (&& offset < inout.Length) will slow it down...

Edit 2: I ran the tests before in the IDE, so here are the results outside:

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.001234 seconds +/- 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

Looks like loop unrolling is not favorable. My optimized code is still my best way to go and with only 10% difference compared to the unsafe code. If only I could tell the compiler that (i < buf.Length) implies that (offset < inout.Length), it will drop the check (inout[offset]) and I will basically get the unsafe performance.

Answer 5

Maybe some unrolling in your own best answer:

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

This might get a little more performance still.