Create and fill an array with an enumeration from 1 to n in the fastest method possible

Question

I've the following code:

int n = 150000;
int[] myArray = Enumerable.Range(1, n).ToArray();

So I want myArray contains an enumeration like 1,2,3,4,etc...
Of course the size of the array should be variable.

The thing is this is called millions of times inside a Parallel.For so I'm looking for a way to improve it as fast as it possible. Every iteration, n is different.

I just nugged the CommunityToolkit.HighPerformance in order to use some advantages from there, I'm wonder if I can use Span<T> to replace the above code, since I read this code:

var array = new byte[100];
var span = new Span<byte>(array);

span.Fill(255);

So I tried to do this:

var myArray = new int[n];
var span = new Span<int>(myArray );
span.Fill(/*nothing works here */);

So how can I populate that array with a serie of 1 to n?
I will accept another way instead using Fill or even Span<T>. The objective is made faster the whole process.

Answer 1

Here is a vectorized implementation of a FillIncremental method. The Vector<T> is a small container of values that a single CPU core can process in parallel. In my PC the Vector.IsHardwareAccelerated is true and the Vector<int>.Count is 8. Initially a Vector<int> is filled with the values from 1 to 8. Then in each step all these values are incremented by 8 with a single += operation, and the incremented vector is copied to the next section of the target array. Finally the last few slots in the array that have not been filled by the vector (because the array Length might not be divisible by 8), are filled with a simple for loop:

/// <summary>
/// Fills an array of integers with incremented values, starting from the 'startValue'.
/// </summary>
public static void FillIncremental(int[] array, int startValue = 0)
{
    ArgumentNullException.ThrowIfNull(array);
    if (array.Length > 0 && startValue > (Int32.MaxValue - array.Length) + 1)
        throw new ArgumentOutOfRangeException(nameof(startValue));

    static void FillSimple(int[] array, int index, int length, int valueOffset)
    {
        int endIndex =  index + length;
        for (int i = index, j = index + valueOffset; i < endIndex; i++, j++)
            array[i] = j;
    }

    if (!Vector.IsHardwareAccelerated || array.Length < Vector<int>.Count)
    {
        FillSimple(array, 0, array.Length, startValue);
        return;
    }
    FillSimple(array, 0, Vector<int>.Count, startValue);
    Vector<int> vector = new(array);
    Vector<int> step = new(Vector<int>.Count);
    int endIndex = array.Length - Vector<int>.Count + 1;
    int i;
    for (i = Vector<int>.Count; i < endIndex; i += Vector<int>.Count)
    {
        vector += step;
        vector.CopyTo(array, i);
    }
    FillSimple(array, i, array.Length - i, startValue);
}

Usage example:

int n = 150_000;
int[] myArray = new int[n];
FillIncremental(myArray, 1);

In my PC the FillIncremental method is about 4 times faster than filling the array with a simple for loop (online benchmark).

I am not overly familiar with vectors, so it might be possible to optimize further the above approach.

---

Update: Enigmativity mentioned in the comments that the simple int[] myArray = Enumerable.Range(1, n).ToArray() is actually faster than the above vectorized implementation. My own benchmark confirms this observation. Currently I have no idea why the Enumerable.Range is so fast. According to the source code is should perform similarly to the FillSimple above, so it should be around 3 times slower (taking into account the constant time of instantiating the array). It's around 15% faster instead (on .NET 7, .NET 6 and .NET 5).

Answer 2

There are two possible situations here:

1. The created array is actually needed (i.e. you can't just use for loop with some counter), then if you know maximum n and it is constrained enough - then the fastest approach I could think of is to preallocate the array and use Array.Copy:

   static int[] preallocated = Enumerable.Range(1, 500_000).ToArray();
   
   int[] array = new int[150_000];
   Array.Copy(preallocated, array, array.Length)
   

   this approach also can be modified to handle the arrays out of bounds also, i.e. first copying the preallocated memory and then using great @Theodor Zoulias's approach to fill the rest (though it can become a bit cumbersome).

   Updated benchmark from another answer

2. You don't actually need the array - if your goal is to split numbers from 1 to n into 2 arrays I would add simple for loop to comparison. Or just using Enumerable.Range and iterating it (another option is using preallocated array with readonly view via ReadOnlySpan/ReadOnlyMemory, but if you really don't need an array - I think there is no point to waste the memory).

P.S.

1. Allocating arrays and then GCing them can be costly (especially large one - see The large object heap (LOH)), consider using ArrayPool. Note that if you are renting more than there are items in corresponding bucket, pooling approach will result in allocation (see maxArraysPerBucket of ArrayPool.Create). Consider creating a separate pool for such arrays and set clearArray to false when calling Return. And do not forget that Array.Rent can return array bigger then requested (you can switch to Span/Memory for subsequent processing)
2. If array pooling is no go and array creation is still required, then consider using GC.AllocateUninitializedArray<T> which can have positive performance difference in case of big number of allocations due to skip zeroing of the memory (we know that we will manually fill it right away).
3. Do proper (micro)benchmarking using proper tools and techniques. For example BenchmarkDotNet.