Buffer concatenation method

Question

Is there any way to improve or optimize the speed of this? I can't think of any ways to do it in one pass.

static byte[] ConcatenateBuffers(params byte[][] list)
{
    int totalLen = 0;
    for (int i = 0; i < list.Length; ++i)
        totalLen += list[i].Length;
    byte[] ret = new byte[totalLen];
    int offset = 0;
    for (int i = 0; i < list.Length; ++i)
    {
        Array.ConstrainedCopy(list[i], 0, ret, offset, list[i].Length);
        offset += list[i].Length;
    }
    return ret;
}

Answer 1

If you're optimizing for performance it does not get much better than that. In particular it is a valuable optimization to compute the exact result array length.

I'm not sure why you used ConstrainedCopy which is a very esoteric feature. Copy is faster. ConstrainedCopy is, I believe, used for code that must not be interrupted by a ThreadAbortException. The concept is called a constrained execution region and it's useless in practice because programming in the presence of thread aborts is essentially impossible. The consensus is to never abort a thread except your own (ASP.NET violates that rule which must be very unsafe).

The code is of good quality as well. I'd use foreach to traverse the list. It compiles to the same code that you wrote but is nicer.

Answers have been proposed that use List<byte> or LINQ. These will be far slower (e.g. 10-100x). This is because Array.Copy is a facade over memmove (which is similar to memcpy but it handles overlapping regions as well). The difference becomes noticeable even with common network speeds (10MB/s) and certainly with disk speeds (100MB/s and up).

If you don't care about performance or the amount of data processed is small than you can use slower approaches. Some people find such code better and I'd certainly understand why. The LINQ approach using Concat is extremely concise and self-documenting.

Answer 2

I think it's possible to do it all in one line using linq:

static byte[] ConcatenateBuffers(params byte[][] list)
{
  return list.SelectMany(x => x).ToArray();
}

Answer 3

If you are optimising for performance, then you need to measure what you are optimising.

This is a quick mini-benchmark that will give you an idea of what the trade-offs are, you can adjust for the size of data you're expected and it may change the results.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace CodeReview184845
{
    delegate byte[] ConcatDelegate(params byte[][] inputs);


    public static class Program
    {
        static byte[] ConcatenateBuffers(params byte[][] list)
        {
            int totalLen = 0;
            for (int i = 0; i < list.Length; ++i)
                totalLen += list[i].Length;
            byte[] ret = new byte[totalLen];
            int offset = 0;
            foreach (var item in list)
            {
                Array.ConstrainedCopy(item, 0, ret, offset, item.Length);
                offset += item.Length;
            }
            return ret;
        }
        static byte[] ArrayCopyConcat(params byte[][] list)
        {
            int totalLen = 0;
            for (int i = 0; i < list.Length; ++i)
                totalLen += list[i].Length;
            byte[] ret = new byte[totalLen];
            int offset = 0;
            foreach (var item in list)
            {
                Array.Copy(item, 0, ret, offset, item.Length);
                offset += item.Length;
            }
            return ret;
        }

        static byte[] LinqConcat(params byte[][] list)
        {
            return list.SelectMany(x => x).ToArray();
        }


        static byte[] BufferConcat(params byte[][] list)
        {
            var ret = new byte[list.Sum(t => t.Length)];
            var offset = 0;
            foreach (var item in list)
            {
                var length = item.Length;
                Buffer.BlockCopy(item, 0, ret, offset, length);
                offset += length;
            }
            return ret;
        }

        static byte[] ConcatWithList(byte[][] list)
        {
            var data = new List<byte>();
            for (var i = 0; i < list.Length; ++i)
            {
                for (var j = 0; j < list[i].Length; j++)
                {
                    data.Add(list[i][j]);   // the list automatically resizes
                }
            }

            return data.ToArray();
        }

        static Tuple<string, ConcatDelegate> Test(string name, ConcatDelegate d)
        {
            return new Tuple<string, ConcatDelegate>(name, d);
        }

        static void Main(string[] args)
        {
            var inputs = CreateInputs();

            var tests = new[]
            {
                Test("original", ConcatenateBuffers),
                Test("list", ConcatWithList),
                Test("Array.Copy", ArrayCopyConcat),
                Test("Linq", LinqConcat),
                Test("Buffer", BufferConcat)
            };

            var elapsed = tests.ToDictionary(test => test.Item1, test => new List<long>());

            while (true)
                foreach (var test in tests)
                {
                    Console.Write($"test {test.Item1}\t");
                    Console.Out.Flush();
                    byte[] output = {};

                    var stopwatch = Stopwatch.StartNew();

                    for (var run = 0; run < 1000; ++run)
                    output = test.Item2(inputs);

                    var total = Sum(output);

                    stopwatch.Stop();
                    elapsed[test.Item1].Add(stopwatch.ElapsedMilliseconds);
                    Console.WriteLine($"elapsed {stopwatch.ElapsedMilliseconds} ms (total: {total}) (mean: {Mean(elapsed[test.Item1])} ms) ");
                    Console.Out.Flush();
                }
        }

        private static long Sum(byte[] output)
        {
            var result = 0L;

            foreach (var value in output)
                result += value;

            return result;
        }

        private static long Mean(List<long> times)
        {
            return times.Sum()/ times.Count;
        }

        private static byte[][] CreateInputs()
        {
            var inputs = new byte[100][];

            for (var i = 0; i < inputs.Length; ++i)
            {
                inputs[i] = new byte[500 + 200 * i];
                for (var j = 0; j < inputs[i].Length; ++j)
                    inputs[i][j] = (byte)j;
            }

            return inputs;
        }
    }
}

On my machine, after a few runs it settles down to results like:

test original   elapsed  429 ms (total: 132052576) (mean:  430 ms)
test list       elapsed 3451 ms (total: 132052576) (mean: 3419 ms)
test Array.Copy elapsed  437 ms (total: 132052576) (mean:  425 ms)
test Linq       elapsed  448 ms (total: 132052576) (mean:  440 ms)
test Buffer     elapsed  443 ms (total: 132052576) (mean:  429 ms)

The runtime is very good at optimising LINQ. Writing something using a for loop instead of LINQ may give you an extra percent (and in some cases can allow you to perform other optimisations), but very often the difference is lost in the noise.

Answer 4

Thank you for this interesting problem. I think your code is good to go, although it isn't quite how I would do it. First, avoid using array unless you absolutely need to. List<T> is much easier to manage, which compensates for it's nominally larger size in memory. You can then get your data in one pass because a list is resizable.

static List<byte> ConcatenateBuffers(params byte[][] list)

Now you can do:

var data = new List<byte>();
for (var i = 0; i < list.Length; ++i)
{
    for (var j = 0; j < list[i].Length; j++)
    {
        data.Add(list[i][j]);   // the list automatically resizes
    }
}

If performance isn't critical, where you need to squeeze the last nanosecond out of performance, I would also consider using IEnumerable and yielding results. This constructs a state machine that doesn't do the calculations until you actually ask for them. It has the drawback of having some slight overhead for each call, but if you only need to process a few bytes periodically and the performance cost of processing a chunk of bytes is large, it allows you to do just that, rather than processing the whole set at once--you only process what you need when you need it.

for (var i = 0; i < list.Length; ++i)
{
    for (var j = 0; j < list[i].Length; j++)
    {
        yield return list[i][j];
    }
}

Your signature then becomes:

static IEnumerable<byte> ConcatenateBuffers(params byte[][] list)

For what it's worth, if you want/need to use arrays, what you have is good, and likely as optimal as you will get both memory- and performance-wise.

Answer 5

A slightly different take on the answers presented so far: this does nothing apart from rename variables, and also methods - and I've done nothing but refactor without changing any of the functionality - perhaps it reads a little better, and I hope will be more understandable if one looks at in in 6 months with no recollection of it?

    private static byte[] getConcatenatedBuffer(params byte[][] inputBuffer)
    {
        int length = getLengthOfConcatenatedBuffer(inputBuffer);

        byte[] concatenatedBuffer = new byte[length];

        int startingIndex = 0;
        for (int i = 0; i < inputBuffer.Length; ++i)
        {
            int endingIndex = inputBuffer[i].Length;

            Array.ConstrainedCopy(inputBuffer[i], 0, concatenatedBuffer, startingIndex, endingIndex);

            // update index values
            startingIndex += inputBuffer[i].Length;
        }
        return concatenatedBuffer;
    }

    private static int getLengthOfConcatenatedBuffer(byte[][] list)
    {
        int totalLength = 0;
        for (int i = 0; i < list.Length; ++i)
        {
            totalLength += list[i].Length;
        }

        return totalLength;
    }