Prepend to a C# Array

Ok guys, let's take a look at the perfomance issue regarding this question. This is not an answer, just a microbenchmark to see which option is more efficient.

So, let's set the scenario:

• A byte array of 1,000,000 items, randomly populated
• We need to prepend item 0x00

We have 3 options:

1. Manually creating and populating the new array
2. Manually creating the new array and using Array.Copy (@Monroe)
3. Creating a list, loading the array, inserting the item and converting the list to an array

Here's the code:

 byte[] byteArray = new byte[1000000]; for (int i = 0; i < byteArray.Length; i++) { byteArray[i] = Convert.ToByte(DateTime.Now.Second); } Stopwatch stopWatch = new Stopwatch(); //#1 Manually creating and populating a new array; stopWatch.Start(); byte[] extendedByteArray1 = new byte[byteArray.Length + 1]; extendedByteArray1[0] = 0x00; for (int i = 0; i < byteArray.Length; i++) { extendedByteArray1[i + 1] = byteArray[i]; } stopWatch.Stop(); Console.WriteLine(string.Format("#1: {0} ms", stopWatch.ElapsedMilliseconds)); stopWatch.Reset(); //#2 Using a new array and Array.Copy stopWatch.Start(); byte[] extendedByteArray2 = new byte[byteArray.Length + 1]; extendedByteArray2[0] = 0x00; Array.Copy(byteArray, 0, extendedByteArray2, 1, byteArray.Length); stopWatch.Stop(); Console.WriteLine(string.Format("#2: {0} ms", stopWatch.ElapsedMilliseconds)); stopWatch.Reset(); //#3 Using a List stopWatch.Start(); List<byte> byteList = new List<byte>(); byteList.AddRange(byteArray); byteList.Insert(0, 0x00); byte[] extendedByteArray3 = byteList.ToArray(); stopWatch.Stop(); Console.WriteLine(string.Format("#3: {0} ms", stopWatch.ElapsedMilliseconds)); stopWatch.Reset(); Console.ReadLine(); 

And the results are:

#1: 9 ms #2: 1 ms #3: 6 ms 

I've run it multiple times and I got different numbers, but the proportion is always the same: #2 is always the most efficient choice.

My conclusion: arrays are more efficient then Lists (although they provide less functionality), and somehow Array.Copy is really optmized (would like to understand that, though).

Any feedback will be appreciated.

Best regards.

PS: this is not a swordfight post, we are at a Q&A site to learn and teach. And learn.

The easiest and cleanest way for .NET 4.7.1 and above is to use the side-effect free Prepend().

Adds a value to the beginning of the sequence.

Example

// Creating an array of numbers var numbers = new[] { 1, 2, 3 }; // Trying to prepend any value of the same type var results = numbers.Prepend(0); // output is 0, 1, 2, 3 Console.WriteLine(string.Join(", ", results )); 

As you surmised, the fastest way to do this is to create new array of length + 1 and copy all the old values over.

If you are going to be doing this many times, then I suggest using a List<byte> instead of byte[], as the cost of reallocating and copying while growing the underlying storage is amortized more effectively; in the usual case, the underlying vector in the List is grown by a factor of two each time an addition or insertion is made to the List that would exceed its current capacity.

... byte[] newValues = new byte[values.Length + 1]; newValues[0] = 0x00; // set the prepended value Array.Copy(values, 0, newValues, 1, values.Length); // copy the old values 

When I need to append data frequently but also want O(1) random access to individual elements, I'll use an array that is over allocated by some amount of padding for quickly adding new values. This means you need to store the actual content length in another variable, as the array.length will indicate the length + the padding. A new value gets appended by using one slot of the padding, no allocation & copy are necessary until you run out of padding. In effect, allocation is amortized over several append operations. There are speed space trade offs, as if you have many of these data structures you could have a fair amount of padding in use at any one time in the program.

This same technique can be used in prepending. Just as with appending, you can introduce an interface or abstraction between the users and the implementation: you can have several slots of padding so that new memory allocation is only necessary occasionally. As some above suggested, you can also implement a prepending interface with an appending data structure that reverses the indexes.

I'd package the data structure as an implementation of some generic collection interface, so that the interface appears fairly normal to the user (such as an array list or something).

(Also, if removal is supported, it's probably useful to clear elements as soon as they are removed to help reduce gc load.)

The main point is to consider the implementation and the interface separately, as decoupling them gives you the flexibility to choose varied implementations or to hide implementation details using a minimal interface.

There are many other data structures you could use depending on the applicability to your domain. Ropes or Gap Buffer; see What is best data structure suitable to implement editor like notepad?; Trie's do some useful things, too.

I know this is a VERY old post but I actually like using lambda. Sure my code may NOT be the most efficient way but its readable and in one line. I use a combination of .Concat and ArraySegment.

 string[] originalStringArray = new string[] { "1", "2", "3", "5", "6" }; int firstElementZero = 0; int insertAtPositionZeroBased = 3; string stringToPrepend = "0"; string stringToInsert = "FOUR"; // Deliberate !!! originalStringArray = new string[] { stringToPrepend } .Concat(originalStringArray).ToArray(); insertAtPositionZeroBased += 1; // BECAUSE we prepended !! originalStringArray = new ArraySegment<string>(originalStringArray, firstElementZero, insertAtPositionZeroBased) .Concat(new string[] { stringToInsert }) .Concat(new ArraySegment<string>(originalStringArray, insertAtPositionZeroBased, originalStringArray.Length - insertAtPositionZeroBased)).ToArray(); 

The best choice depends on what you're going to be doing with this collection later on down the line. If that's the only length-changing edit that will ever be made, then your best bet is to create a new array with one additional slot and use Array.Copy() to do the rest. No need to initialize the first value, since new C# arrays are always zeroed out:

byte[] PrependWithZero(byte[] input) { var newArray = new byte[input.Length + 1]; Array.Copy(input, 0, newArray, 1, input.Length); return newArray; } 

If there are going to be other length-changing edits that might happen, the most performant option might be to use a List<byte> all along, as long as the additions aren't always to the beginning. (If that's the case, even a linked list might not be an option that you can dismiss out of hand.):

var list = new List<byte>(input); list.Insert(0, 0); 

You can let the compiler take the wheel with the optimisations using the new collection expression and spread element:

byte[] newArray = [0x00, ..oldArray]; 

From glancing at my IL on Release build, it seems that it goes the route of creating a new array with the length of the oldArray + 1, and for-looping adding the other array.
So it's not as efficient as the Array.Copy, however, it's a nice one-liner that could be improved over time and by the compiler based on your configuration.

Apparently, the spread element takes the GetEnumerator over an applicable CopyTo. Perhaps I'm missing something!

From docs (where target type is an array):

If the element is a spread element then one of the following is used:

• A member of a well-known interface or type is invoked to copy items from the spread element expression to the initialization instance.
• An applicable GetEnumerator instance or extension method is invoked on the spread element expression and for each item from the enumerator, the initialization instance indexer is invoked to add the item at the current index. If the enumerator implements IDisposable, then Dispose will be called after enumeration, regardless of exceptions.
• An applicable CopyTo instance or extension method is invoked on the spread element expression with the initialization instance and int index as arguments.

I am aware this is over 4-year-old accepted post, but for those who this might be relevant Buffer.BlockCopy would be faster.