Fastest way to fill an array with a single value

Question

I would like to fill a 2D array with a single value that I have, however, I would like to do it the quickest way possible has the 2D array's length will be a total of 200k+ and over time there will be over 200 of these arrays. I have looked into Buffer.BlockCopy and Array.Copy, however, they both take in arrays as the source/destination, where the only array I have is the destination, with the source being a single value.

What is the fastest way to fill in an array with the source being a single value and not an array?

Solution 1

The fastest method I have found uses Array.Copy with the copy size doubling each time through the loop. The speed is basically the same whether you fill the array with a single value or an array of values.

In my test with 20,000,000 array items, this function is twice as fast as a for loop.

using System;

namespace Extensions
{
    public static class ArrayExtensions
    {
        public static void Fill<T>(this T[] destinationArray, params T[] value)
        {
            if (destinationArray == null)
            {
                throw new ArgumentNullException("destinationArray");
            }

            if (value.Length >= destinationArray.Length)
            {
                throw new ArgumentException("Length of value array must be less than length of destination");
            }

            // set the initial array value
            Array.Copy(value, destinationArray, value.Length);

            int arrayToFillHalfLength = destinationArray.Length / 2;
            int copyLength;

            for(copyLength = value.Length; copyLength < arrayToFillHalfLength; copyLength <<= 1)
            {
                Array.Copy(destinationArray, 0, destinationArray, copyLength, copyLength);
            }

            Array.Copy(destinationArray, 0, destinationArray, copyLength, destinationArray.Length - copyLength);
        }
    }
}

I blogged about this at https://secureapplicationlifestyle.com/2011/11/initialize-array-to-value-in-c-very.html and https://secureapplicationlifestyle.com/2014/04/better-array-fill-function.html

Solution 2

For some related info, see What is the equivalent of memset in C#?.

As mentioned in that question (pretty close to a dupe of this one), a for loop is generally best unless you want to get into unmanaged code.

So this should be pretty fast:

int[] arr = new int[MAX_ELEMENTS];
for (int i = 0; i < arr.Length; ++i)
{
    array[i] = MY_VALUE;
}

As with all things performance-related, get something working, then measure what the bottleneck is. Emphasis on "measure." Trying to guess what the bottleneck is is usually a bad idea (:

Solution 3

Array.Copy is likely to be better optimized than a for loop, so use it.

void FillArray<T>(T[] arr, T fillValue)
{
    int i = 0;
    if (arr.Length > 16) {
    {
        do {
            array[i++] = fillValue;
        } while (i < arr.Length)
        while (i + 16 < arr.Length) {
            Array.Copy(arr, 0, arr, i, 16);
            i = i + 16;
        }
    }
    while (i < arr.Length)
    {
        array[i++] = fillValue;
    }
}

(I'd love to see a performance comparison between this and the naive for loop, for different types and array sizes)

Comments

[debracey]

There are a couple of different ways, this guy has listed out a few of the more common ones -- and he was even kind enough to benchmark it: dotnetperls.com/initialize-array Holding 200K items in memory, even if they are primitives, is going to eat up a huge chunk of memory -- what are you doing that you need all 200K items available with constant time access (per item)?