How to optimize copying chunks of an array in C#?

Question

I am writing a live-video imaging application and need to speed up this method. It's currently taking about 10ms to execute and I'd like to get it down to 2-3ms.

I've tried both Array.Copy and Buffer.BlockCopy and they both take ~30ms which is 3x longer than the manual copy.

One thought was to somehow copy 4 bytes as an integer and then paste them as an integer, thereby reducing 4 lines of code to one line of code. However, I'm not sure how to do that.

Another thought was to somehow use pointers and unsafe code to do this, but I'm not sure how to do that either.

All help is much appreciated. Thank you!

EDIT: Array sizes are: inputBuffer[327680], lookupTable[16384], outputBuffer[1310720]

public byte[] ApplyLookupTableToBuffer(byte[] lookupTable, ushort[] inputBuffer)
{
    System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
    sw.Start();

    // Precalculate and initialize the variables
    int lookupTableLength = lookupTable.Length;
    int bufferLength = inputBuffer.Length;
    byte[] outputBuffer = new byte[bufferLength * 4];
    int outIndex = 0;
    int curPixelValue = 0;

    // For each pixel in the input buffer...
    for (int curPixel = 0; curPixel < bufferLength; curPixel++)
    {
        outIndex = curPixel * 4;                    // Calculate the corresponding index in the output buffer
        curPixelValue = inputBuffer[curPixel] * 4;  // Retrieve the pixel value and multiply by 4 since the lookup table has 4 values (blue/green/red/alpha) for each pixel value

        // If the multiplied pixel value falls within the lookup table...
        if ((curPixelValue + 3) < lookupTableLength)
        {
            // Copy the lookup table value associated with the value of the current input buffer location to the output buffer
            outputBuffer[outIndex + 0] = lookupTable[curPixelValue + 0];
            outputBuffer[outIndex + 1] = lookupTable[curPixelValue + 1];
            outputBuffer[outIndex + 2] = lookupTable[curPixelValue + 2];
            outputBuffer[outIndex + 3] = lookupTable[curPixelValue + 3];

            //System.Buffer.BlockCopy(lookupTable, curPixelValue, outputBuffer, outIndex, 4);   // Takes 2-10x longer than just copying the values manually
            //Array.Copy(lookupTable, curPixelValue, outputBuffer, outIndex, 4);                // Takes 2-10x longer than just copying the values manually
        }
    }

    Debug.WriteLine("ApplyLookupTableToBuffer(ms): " + sw.Elapsed.TotalMilliseconds.ToString("N2"));
    return outputBuffer;
}

EDIT: I've updated the method keeping the same variable names so others can see how the code would translate based on HABJAN's solution below.

    public byte[] ApplyLookupTableToBufferV2(byte[] lookupTable, ushort[] inputBuffer)
    {
        System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
        sw.Start();

        // Precalculate and initialize the variables
        int lookupTableLength = lookupTable.Length;
        int bufferLength = inputBuffer.Length;
        byte[] outputBuffer = new byte[bufferLength * 4];
        //int outIndex = 0;
        int curPixelValue = 0;

        unsafe
        {
            fixed (byte* pointerToOutputBuffer = &outputBuffer[0])
            fixed (byte* pointerToLookupTable = &lookupTable[0])
            {
                // Cast to integer pointers since groups of 4 bytes get copied at once
                uint* lookupTablePointer = (uint*)pointerToLookupTable;
                uint* outputBufferPointer = (uint*)pointerToOutputBuffer;

                // For each pixel in the input buffer...
                for (int curPixel = 0; curPixel < bufferLength; curPixel++)
                {
                    // No need to multiply by 4 on the following 2 lines since the pointers are for integers, not bytes
                    // outIndex = curPixel;  // This line is commented since we can use curPixel instead of outIndex
                    curPixelValue = inputBuffer[curPixel];  // Retrieve the pixel value 

                    if ((curPixelValue + 3) < lookupTableLength)
                    {
                        outputBufferPointer[curPixel] = lookupTablePointer[curPixelValue];
                    }
                }
            }
        }

        Debug.WriteLine("2 ApplyLookupTableToBuffer(ms): " + sw.Elapsed.TotalMilliseconds.ToString("N2"));
        return outputBuffer;
    }

Live-video imaging application in pure C# and with byte[] manipulation? No way... sooner or later you will have to go lower so I strongly suggest learning Interop and/or C++/CLI. — Konrad Kokosa
– Konrad Kokosa, Commented Jan 13, 2014 at 17:52
Yup, there might be a need to go 'lower'. Before you do that, you could try to rewrite that using pointer arithmetic in an unsafe block and measure again, there are no simple guarantees about performance here though. — Patryk Ćwiek
– Patryk Ćwiek, Commented Jan 13, 2014 at 17:54
In my experience, a simple conversion to unsafe will yield about a 10 percent improvement in performance. Your mileage may vary. — Robert Harvey
– Robert Harvey, Commented Jan 13, 2014 at 17:56
Could you provide information about your input arrays (size, etc.)? — ken2k
– ken2k, Commented Jan 13, 2014 at 18:15
@PatrykĆwiek: Would you please be so kind as to provide a sample as to how the pointer arithmetic might work? I'd like to give it a try, but am not sure where to start. Thanks. — nb1forxp
– nb1forxp, Commented Jan 13, 2014 at 18:30

Jojodmo · Accepted Answer · 2014-02-06 05:34:37Z

14

I did some tests, and I managed to achieve max speed by turning my code into unsafe along with using the RtlMoveMemory API. I figured out that Buffer.BlockCopy and Array.Copy were much slower than direct RtlMoveMemory usage.

So, at the end you will end up with something like this:

fixed(byte* ptrOutput= &outputBufferBuffer[0])
{
    MoveMemory(ptrOutput, ptrInput, 4);
}

[DllImport("Kernel32.dll", EntryPoint = "RtlMoveMemory", SetLastError = false)]
private static unsafe extern void MoveMemory(void* dest, void* src, int size);

EDIT:

Ok, now once when I figured out your logic and when I did some tests, I managed to speed up your method for almost up to 50%. Since you need to copy a small data blocks (always 4 bytes), yes, you were right, RtlMoveMemory wont help here and it's better to copy data as integer. Here is the final solution I came up with:

public static byte[] ApplyLookupTableToBufferV2(byte[] lookupTable, ushort[] inputBuffer)
{
    int lookupTableLength = lookupTable.Length;
    int bufferLength = inputBuffer.Length;
    byte[] outputBuffer = new byte[bufferLength * 4];
    int outIndex = 0, curPixelValue = 0;

    unsafe
    {
        fixed (byte* ptrOutput = &outputBuffer[0])
        fixed (byte* ptrLookup = &lookupTable[0])
        {
            uint* lkp = (uint*)ptrLookup;
            uint* opt = (uint*)ptrOutput;

            for (int index = 0; index < bufferLength; index++)
            {
                outIndex = index;
                curPixelValue = inputBuffer[index];

                if ((curPixelValue + 3) < lookupTableLength)
                {
                    opt[outIndex] = lkp[curPixelValue];
                }
            }
        }
    }

    return outputBuffer;
}

I renamed your method to ApplyLookupTableToBufferV1.

And here are my test result:

int tc1 = Environment.TickCount;

for (int i = 0; i < 200; i++)
{
    byte[] a = ApplyLookupTableToBufferV1(lt, ib);
}

tc1 = Environment.TickCount - tc1;

Console.WriteLine("V1: " + tc1.ToString() + "ms");

Result - V1: 998 ms

int tc2 = Environment.TickCount;

for (int i = 0; i < 200; i++)
{
    byte[] a = ApplyLookupTableToBufferV2(lt, ib);
}

tc2 = Environment.TickCount - tc2;

Console.WriteLine("V2: " + tc2.ToString() + "ms");

Result - V2: 473 ms

edited Feb 6, 2014 at 5:34

Jojodmo

23.6k13 gold badges69 silver badges112 bronze badges

answered Jan 13, 2014 at 18:06

HABJAN

9,2733 gold badges38 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

nb1forxp Over a year ago

Thanks for the suggestion. I implemented it like this: fixed (byte* ptrOutput = &outputBuffer[outIndex]) { fixed (byte* ptrInput = &lookupTable[curPixelValue]) { MoveMemory(ptrOutput, ptrInput, 4); } }. Unfortunately, it is much slower; it executes in 40-100ms, with the average being about 60ms.

nb1forxp Over a year ago

Fantastic!! That is exactly what I was hoping for. Thank you so much. The time went from ~10ms to an average of 4.3ms. If I remove the lookupTableLength check, it drops to an average of 3.3ms.

Collectives™ on Stack Overflow

How to optimize copying chunks of an array in C#?

1 Answer 1

EDIT:

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

EDIT:

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related