7
\$\begingroup\$

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;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ What do you want to optimize for? Speed? Size? Clarity? \$\endgroup\$ – Philip Kendall Jan 11 '18 at 16:53
  • \$\begingroup\$ Mostly speed, but this is an interactive client application so I don't need to go to a lower level language to get the absolute fastest method. \$\endgroup\$ – user Jan 11 '18 at 18:11
  • \$\begingroup\$ Your length computation can suffer from integer overflow, in which case the array copying will throw an exception. \$\endgroup\$ – CodesInChaos Jan 12 '18 at 12:43
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I had no idea Array.Copy could specify the location. I always used Array.ConstrainedCopy because I thought that it was the version that allowed me to specify the location of the data in the new array. \$\endgroup\$ – user Jan 11 '18 at 17:26
  • \$\begingroup\$ +1: this seems like the most appropriate answer so far. Minor nitpick: the documentation for Array.Copy mentions that it's equivalent to memmove, not memcpy, the difference being that overlap between the source and destination is allowed. \$\endgroup\$ – Pieter Witvoet Jan 11 '18 at 18:37
  • \$\begingroup\$ "Answers have been proposed that use List<byte> or LINQ. These will be far slower" You might think, but the runtime is very good at optimising LINQ. \$\endgroup\$ – Pete Kirkham Jan 12 '18 at 9:03
  • \$\begingroup\$ @PeteKirkham LINQ is not specifically targeted by the JIT for optimizations. This has recently been proposed on GitHub but it's hard. I know from experience that LINQ to object queries execute almost literally on the CPU causing enormous runtime increases (and allocations diminishing overall application scalability due to GC involvement). \$\endgroup\$ – usr Jan 15 '18 at 12:02
  • \$\begingroup\$ @usr Yes, generally I'd assume that LINQ would be slower, but from measuring this case is not significantly slower. It certainly can be slower is some cases, so (as for anything performance related) you must measure and use that evidence before you make any statements about what is fast enough or too slow. I didn't mean to imply that the JIT specifically targeted LINQ itself, only that it was good at optimising the sort of code LINQ generates.I wouldn't expect JIT to optimise inefficient algorithms or reorder complex queries for best execution. \$\endgroup\$ – Pete Kirkham Jan 15 '18 at 13:08
10
\$\begingroup\$

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();
}
\$\endgroup\$
  • \$\begingroup\$ I'm surprised this answer isn't more popular as it seems to me to be the best answer in terms of both clarity and size, and performance wise, looking at Pete's answer, is as near as makes no difference on par with more complicated solutions. \$\endgroup\$ – Ashigore Jan 12 '18 at 11:48
  • \$\begingroup\$ @Ashigore we don't like the machine taking our jobs :) . \$\endgroup\$ – Pete Kirkham Jan 12 '18 at 17:23
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Any performance implications with using List<byte>? I'm using this for building network packets that get encrypted or appending the IV. It looks like the AesManaged class only uses byte[] data types so I think I would have to use ToArray() to use them. \$\endgroup\$ – user Jan 11 '18 at 14:29
  • \$\begingroup\$ It resizes the array every so often, which adds some overhead. Not enough to be noticeable unless you are running real-time data where every nanosecond counts. However, given that you need the array anyway, I'd just leave it the way you have it. Just wanted to throw some ideas out there. \$\endgroup\$ – Hosch250 Jan 11 '18 at 14:31
  • \$\begingroup\$ Cool, thanks. I'll accept the answer in a couple of hours. \$\endgroup\$ – user Jan 11 '18 at 14:33
  • 6
    \$\begingroup\$ Element-by-element copying is slower than copying a memory block (which ConstrainedCopy does internally) once you have to copy arrays with more than ~100 items. Performance will differ by orders of magnitude for really large arrays. So unless OP has a special case, where he knows beforehand that he will only be dealing with very small arrays, I would recommend against above refactoring. \$\endgroup\$ – Nikita B Jan 11 '18 at 15:15
  • 2
    \$\begingroup\$ There is a good answer on SO which goes into more detail on the topic, in case anyone is interested: stackoverflow.com/a/33865267/1386995 \$\endgroup\$ – Nikita B Jan 11 '18 at 15:25
0
\$\begingroup\$

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;
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.