how to quickly flip an array?
Dear readers, in this article I want to talk about small tests for obtaining a reverse array and present my conclusions. Tests are made on .net 7.
Tested using BenchmarkDotNet so everyone can check the results and draw their own conclusions.
I note right away that the attribute is used for tests [GlobalSetup]which allows you not to worry about the starting data, since they will be “Executed once per each N value” and this is what we need.
For a complete picture of what is happening, the main tests are carried out on arrays with the number of elements 1000, 10_000, 100_000, 1_000_000, 100_000_000, and the last one with the addition of up to 1_000_000_000 numbers.
The first tests are related to processing the original array without getting a new one, which is not always the right choice, but almost always does not require memory (tests will show strangeness on a large sample).
To start, the usual While is used, presented in a more convenient notation than analogues in the vastness of the network:
[Benchmark]
public int[] While()
{
if (array.Length == 0)
{
return Array.Empty<int>();
}
int i = -1;
int j = array.Length;
while (i++ < j--)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}The most common answer to this question is:
[Benchmark]
public int[] Array_Reverse()
{
Array.Reverse(array);
return array;
}I won’t say that everything is bad here, because under the hood there is a lot of work with unsafe and various “magic” to speed up:
public unsafe static void Reverse<[Nullable(2)] T>(T[] array)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (array.Length > 1)
{
SpanHelpers.Reverse(ref MemoryMarshal.GetArrayDataReference(array), (UIntPtr)(void*)array.Length);
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Reverse<T>(ref T elements, UIntPtr length)
{
if (!RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
if (Unsafe.SizeOf<T>() == 1)
{
Reverse(ref Unsafe.As<T, byte>(ref elements), length);
return;
}
if (Unsafe.SizeOf<T>() == 2)
{
Reverse(ref Unsafe.As<T, char>(ref elements), length);
return;
}
if (Unsafe.SizeOf<T>() == 4)
{
Reverse(ref Unsafe.As<T, int>(ref elements), length);
return;
}
if (Unsafe.SizeOf<T>() == 8)
{
Reverse(ref Unsafe.As<T, long>(ref elements), length);
return;
}
}
ReverseInner(ref elements, length);
}
public unsafe static void Reverse(ref long buf, UIntPtr length)
{
if (Avx2.IsSupported && (ulong)(UIntPtr)(void*)((long)Vector256<long>.Count * 2L) <= (ulong)length)
{
UIntPtr uIntPtr = (UIntPtr)(void*)Vector256<long>.Count;
UIntPtr uIntPtr2 = (UIntPtr)(void*)((ulong)(UIntPtr)(void*)((ulong)length / (ulong)uIntPtr) / 2uL);
for (UIntPtr uIntPtr3 = (UIntPtr)(void*)null; (ulong)uIntPtr3 < (ulong)uIntPtr2; uIntPtr3 = (UIntPtr)(void*)((ulong)(long)(ulong)uIntPtr3 + 1uL))
{
UIntPtr elementOffset = (UIntPtr)(void*)((ulong)(long)(ulong)uIntPtr3 * (ulong)(long)(ulong)uIntPtr);
UIntPtr elementOffset2 = (UIntPtr)(void*)((ulong)(long)(ulong)length - (ulong)(long)(IntPtr)(void*)((long)(IntPtr)(void*)(1L + (long)(ulong)uIntPtr3) * (long)(ulong)uIntPtr));
Vector256<long> value = Vector256.LoadUnsafe(ref buf, elementOffset);
Vector256<long> value2 = Vector256.LoadUnsafe(ref buf, elementOffset2);
value = Avx2.Permute4x64(value, 27);
value2 = Avx2.Permute4x64(value2, 27);
value2.StoreUnsafe(ref buf, elementOffset);
value.StoreUnsafe(ref buf, elementOffset2);
}
buf = ref Unsafe.Add(ref buf, (UIntPtr)(void*)((ulong)(long)(ulong)uIntPtr2 * (ulong)(long)(ulong)uIntPtr));
length = (UIntPtr)(void*)((ulong)(long)(ulong)length - (ulong)(long)(IntPtr)(void*)((long)(IntPtr)(void*)((long)(ulong)uIntPtr2 * (long)(ulong)uIntPtr) * 2L));
}
else if (Vector128.IsHardwareAccelerated && (ulong)(UIntPtr)(void*)((long)Vector128<long>.Count * 2L) <= (ulong)length)
{
UIntPtr uIntPtr4 = (UIntPtr)(void*)Vector128<long>.Count;
UIntPtr uIntPtr5 = (UIntPtr)(void*)((ulong)(UIntPtr)(void*)((ulong)length / (ulong)uIntPtr4) / 2uL);
for (UIntPtr uIntPtr6 = (UIntPtr)(void*)null; (ulong)uIntPtr6 < (ulong)uIntPtr5; uIntPtr6 = (UIntPtr)(void*)((ulong)(long)(ulong)uIntPtr6 + 1uL))
{
UIntPtr elementOffset3 = (UIntPtr)(void*)((ulong)(long)(ulong)uIntPtr6 * (ulong)(long)(ulong)uIntPtr4);
UIntPtr elementOffset4 = (UIntPtr)(void*)((ulong)(long)(ulong)length - (ulong)(long)(IntPtr)(void*)((long)(IntPtr)(void*)(1L + (long)(ulong)uIntPtr6) * (long)(ulong)uIntPtr4));
Vector128<long> vector = Vector128.LoadUnsafe(ref buf, elementOffset3);
Vector128<long> vector2 = Vector128.LoadUnsafe(ref buf, elementOffset4);
vector = Vector128.Shuffle(vector, Vector128.Create(1L, 0L));
vector2 = Vector128.Shuffle(vector2, Vector128.Create(1L, 0L));
vector2.StoreUnsafe(ref buf, elementOffset3);
vector.StoreUnsafe(ref buf, elementOffset4);
}
buf = ref Unsafe.Add(ref buf, (UIntPtr)(void*)((ulong)(long)(ulong)uIntPtr5 * (ulong)(long)(ulong)uIntPtr4));
length = (UIntPtr)(void*)((ulong)(long)(ulong)length - (ulong)(long)(IntPtr)(void*)((long)(IntPtr)(void*)((long)(ulong)uIntPtr5 * (long)Vector128<long>.Count) * 2L));
}
ReverseInner(ref buf, length);
}For a change, check the sorting:
[Benchmark]
public int[] Array_Sort()
{
Array.Sort(array, 0, array.Length, _comparer);
return array;
}public static void Sort<[Nullable(2)] T>(T[] array, int index, int length, [Nullable(new byte[] { 2, 1 })] IComparer<T> comparer)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (index < 0)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (length < 0)
{
ThrowHelper.ThrowLengthArgumentOutOfRange_ArgumentOutOfRange_NeedNonNegNum();
}
if (array.Length - index < length)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
}
if (length > 1)
{
Span<T> keys = new Span<T>(ref Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(array), index), length);
ArraySortHelper<T>.Default.Sort(keys, comparer);
}
}What follows are several variants of the for loop, each of which is not quite familiar:
[Benchmark]
public int[] For()
{
for (int i = 0, length = array.Length - 1; i < length / 2; i++)
{
int item = array[i];
array[i] = array[length - i];
array[length - i] = item;
}
return array;
}
[Benchmark]
public int[] For_Size()
{
for (int i = 0, length = array.Length - 1, size = length / 2; i < size; i++)
{
int item = array[i];
array[i] = array[length - i];
array[length - i] = item;
}
return array;
}For example, I will give 2 options, but further in the full code you can see all available solutions. I note that such seemingly simple improvements help to speed up a little, but here everyone chooses how it is more convenient to do it.
Website https://sharplab.io shows the following on For():
using System;
using System.Diagnostics;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security;
using System.Security.Permissions;
[assembly: CompilationRelaxations(8)]
[assembly: RuntimeCompatibility(WrapNonExceptionThrows = true)]
[assembly: Debuggable(DebuggableAttribute.DebuggingModes.IgnoreSymbolStoreSequencePoints)]
[assembly: SecurityPermission(SecurityAction.RequestMinimum, SkipVerification = true)]
[assembly: AssemblyVersion("0.0.0.0")]
[module: UnverifiableCode]
public class C
{
private static int[] array;
public void M()
{
int i = 0;
for (int num = array.Length - 1; i < num / 2; i++)
{
int num2 = array[i];
array[i] = array[num - i];
array[num - i] = num2;
}
}
static C()
{
int[] obj = new int[15];
RuntimeHelpers.InitializeArray(obj, (RuntimeFieldHandle)/*OpCode not supported: LdMemberToken*/);
array = obj;
}
}
[CompilerGenerated]
internal sealed class <PrivateImplementationDetails>
{
[StructLayout(LayoutKind.Explicit, Pack = 1, Size = 60)]
private struct __StaticArrayInitTypeSize=60
{
}
internal static readonly __StaticArrayInitTypeSize=60 5A8B4F50AC386D79A3A5947122333429A35EBC81F89E807236ED66A4BB8FE498/* Not supported: data(01 00 00 00 02 00 00 00 03 00 00 00 04 00 00 00 05 00 00 00 06 00 00 00 07 00 00 00 08 00 00 00 09 00 00 00 0A 00 00 00 0B 00 00 00 0C 00 00 00 0D 00 00 00 0E 00 00 00 0F 00 00 00) */;
}
At the same time for For_Size():
using System;
using System.Diagnostics;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security;
using System.Security.Permissions;
[assembly: CompilationRelaxations(8)]
[assembly: RuntimeCompatibility(WrapNonExceptionThrows = true)]
[assembly: Debuggable(DebuggableAttribute.DebuggingModes.IgnoreSymbolStoreSequencePoints)]
[assembly: SecurityPermission(SecurityAction.RequestMinimum, SkipVerification = true)]
[assembly: AssemblyVersion("0.0.0.0")]
[module: UnverifiableCode]
public class C
{
private static int[] array;
public void M()
{
int i = 0;
int num = array.Length - 1;
for (int num2 = num / 2; i < num2; i++)
{
int num3 = array[i];
array[i] = array[num - i];
array[num - i] = num3;
}
}
static C()
{
int[] obj = new int[15];
RuntimeHelpers.InitializeArray(obj, (RuntimeFieldHandle)/*OpCode not supported: LdMemberToken*/);
array = obj;
}
}
[CompilerGenerated]
internal sealed class <PrivateImplementationDetails>
{
[StructLayout(LayoutKind.Explicit, Pack = 1, Size = 60)]
private struct __StaticArrayInitTypeSize=60
{
}
internal static readonly __StaticArrayInitTypeSize=60 5A8B4F50AC386D79A3A5947122333429A35EBC81F89E807236ED66A4BB8FE498/* Not supported: data(01 00 00 00 02 00 00 00 03 00 00 00 04 00 00 00 05 00 00 00 06 00 00 00 07 00 00 00 08 00 00 00 09 00 00 00 0A 00 00 00 0B 00 00 00 0C 00 00 00 0D 00 00 00 0E 00 00 00 0F 00 00 00) */;
}
And for reference, For_Unsafe_SameArray:
using System;
using System.Diagnostics;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security;
using System.Security.Permissions;
[assembly: CompilationRelaxations(8)]
[assembly: RuntimeCompatibility(WrapNonExceptionThrows = true)]
[assembly: Debuggable(DebuggableAttribute.DebuggingModes.IgnoreSymbolStoreSequencePoints)]
[assembly: SecurityPermission(SecurityAction.RequestMinimum, SkipVerification = true)]
[assembly: AssemblyVersion("0.0.0.0")]
[module: UnverifiableCode]
public class C
{
private static int[] array;
public void M()
{
For_Unsafe_SameArray();
}
public unsafe int[] For_Unsafe_SameArray()
{
fixed (int* ptr = array)
{
int i = 0;
for (int num = array.Length - 1; i < num / 2; i++)
{
int num2 = ptr[i];
ptr[i] = ptr[num - i];
ptr[num - i] = num2;
}
}
return array;
}
static C()
{
int[] obj = new int[15];
RuntimeHelpers.InitializeArray(obj, (RuntimeFieldHandle)/*OpCode not supported: LdMemberToken*/);
array = obj;
}
}
[CompilerGenerated]
internal sealed class <PrivateImplementationDetails>
{
[StructLayout(LayoutKind.Explicit, Pack = 1, Size = 60)]
private struct __StaticArrayInitTypeSize=60
{
}
internal static readonly __StaticArrayInitTypeSize=60 5A8B4F50AC386D79A3A5947122333429A35EBC81F89E807236ED66A4BB8FE498/* Not supported: data(01 00 00 00 02 00 00 00 03 00 00 00 04 00 00 00 05 00 00 00 06 00 00 00 07 00 00 00 08 00 00 00 09 00 00 00 0A 00 00 00 0B 00 00 00 0C 00 00 00 0D 00 00 00 0E 00 00 00 0F 00 00 00) */;
}Additionally, the final listing shows how to work with unsafe and range in different variations.
hidden text
using BenchmarkDotNet.Attributes;
namespace Benchmarks.Benchmarks.Arrays;
[MemoryDiagnoser]
public class ArrayReverseSameArray
{
private static readonly Comparer<int> _comparer = Comparer<int>.Create((x, y) => y.CompareTo(x));
[Params(1000, 10_000, 100_000, 1_000_000, 100_000_000)]
public int NumberCount;
private int[] array;
[GlobalSetup]
public void GlobalSetup()
{
array = Enumerable.Range(1, NumberCount).ToArray();
}
[Benchmark]
public int[] While()
{
if (array.Length == 0)
{
return Array.Empty<int>();
}
int i = -1;
int j = array.Length;
while (i++ < j--)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
[Benchmark]
public int[] Array_Reverse()
{
Array.Reverse(array);
return array;
}
[Benchmark]
public int[] Array_Sort()
{
Array.Sort(array, 0, array.Length, _comparer);
return array;
}
[Benchmark]
public int[] For()
{
for (int i = 0, length = array.Length - 1; i < length / 2; i++)
{
int item = array[i];
array[i] = array[length - i];
array[length - i] = item;
}
return array;
}
[Benchmark]
public int[] For_Size()
{
for (int i = 0, length = array.Length - 1, size = length / 2; i < size; i++)
{
int item = array[i];
array[i] = array[length - i];
array[length - i] = item;
}
return array;
}
[Benchmark]
public unsafe int[] For_Unsafe()
{
fixed (int* arrayItem = array)
{
for (int i = 0, length = array.Length - 1; i < length / 2; i++)
{
int item = arrayItem[i];
arrayItem[i] = arrayItem[length - i];
arrayItem[length - i] = item;
}
}
return array;
}
[Benchmark]
public unsafe int[] For_Unsafe_Size()
{
fixed (int* arrayItem = array)
{
for (int i = 0, length = array.Length - 1, size = length / 2; i < size; i++)
{
int item = arrayItem[i];
arrayItem[i] = arrayItem[length - i];
arrayItem[length - i] = item;
}
}
return array;
}
[Benchmark]
public int[] For_Range()
{
for (int i = 0, length = array.Length - 1; i < length / 2; i++)
{
(array[^(i + 1)], array[i]) = (array[i], array[^(i + 1)]);
}
return array;
}
[Benchmark]
public int[] For_Range_Size()
{
for (int i = 0, length = array.Length - 1, size = length / 2; i < size; i++)
{
(array[^(i + 1)], array[i]) = (array[i], array[^(i + 1)]);
}
return array;
}
[Benchmark]
public int[] For_Range_v2()
{
for (int i = 0, length = array.Length - 1; i < length / 2; i++)
{
(array[i], array[length - i]) = (array[length - i], array[i]);
}
return array;
}
[Benchmark]
public int[] For_Range_v2_Size()
{
for (int i = 0, length = array.Length - 1, size = length / 2; i < size; i++)
{
(array[i], array[length - i]) = (array[length - i], array[i]);
}
return array;
}
[Benchmark]
public unsafe int[] For_Range_v2_Unsafe()
{
fixed (int* arrayItem = array)
{
for (int i = 0, length = array.Length - 1; i < length / 2; i++)
{
(arrayItem[i], arrayItem[length - i]) = (arrayItem[length - i], arrayItem[i]);
}
}
return array;
}
[Benchmark]
public unsafe int[] For_Range_v2_Unsafe_Size()
{
fixed (int* arrayItem = array)
{
for (int i = 0, length = array.Length - 1, size = length / 2; i < size; i++)
{
(arrayItem[i], arrayItem[length - i]) = (arrayItem[length - i], arrayItem[i]);
}
}
return array;
}
}
It is noteworthy that at the limit values everywhere there will be, albeit insignificant, but memory consumption.
It’s time to try options that are more practical. It’s about returning a new array without changing the input.
hidden text
using BenchmarkDotNet.Attributes;
namespace Benchmarks.Benchmarks.Arrays;
[MemoryDiagnoser]
public class ArrayReverseNewArray
{
private static readonly Comparer<int> _comparer = Comparer<int>.Create((x, y) => y.CompareTo(x));
[Params(1000, 10_000, 100_000, 1_000_000, 100_000_000)]
public int NumberCount;
private int[] array;
[GlobalSetup]
public void GlobalSetup()
{
array = Enumerable.Range(1, NumberCount).ToArray();
}
[Benchmark]
public int[] Array_Reverse_ToArray()
{
int[] items = array.ToArray();
Array.Reverse(items);
return items;
}
[Benchmark]
public int[] Array_Reverse_CopyTo()
{
int[] results = new int[array.Length];
array.CopyTo(results, 0);
Array.Reverse(results);
return results;
}
[Benchmark]
public int[] For()
{
int[] items = new int[array.Length];
int j = 0;
for (int i = array.Length - 1; i > -1; i--)
{
items[j++] = array[i];
}
return items;
}
[Benchmark]
public int[] Enumerable_ToArray()
{
return array.Reverse().ToArray();
}
[Benchmark]
public int[] Stack_ToArray()
{
Stack<int> stack = new(array);
return stack.ToArray();
}
[Benchmark]
public int[] Stack_CopyTo()
{
Stack<int> stack = new(array);
int[] results = new int[stack.Count];
stack.CopyTo(results, 0);
return results;
}
[Benchmark]
public int[] OrderByDescending_ToArray()
{
return array.OrderByDescending(x => x).ToArray();
}
[Benchmark]
public int[] QueryOperators_OrderByDescending_ToArray()
{
return (from x in array orderby x descending select x).ToArray();
}
[Benchmark]
public int[] List_ToArray()
{
List<int> items = new(array);
items.Reverse();
return items.ToArray();
}
[Benchmark]
public int[] List_CopyTo()
{
List<int> items = new(array);
items.Reverse();
int[] results = new int[items.Count];
items.CopyTo(results, 0);
return results;
}
[Benchmark]
public int[] List_Sort()
{
List<int> items = new(array);
items.Sort(_comparer);
return items.ToArray();
}
[Benchmark]
public int[] List_Sort_CopyTo()
{
List<int> items = new(array);
items.Sort(_comparer);
int[] results = new int[items.Count];
items.CopyTo(results, 0);
return results;
}
[Benchmark]
public int[] Span_ToArray()
{
Span<int> items = new(array);
items.Reverse();
return items.ToArray();
}
[Benchmark]
public int[] Span_Sort_ToArray()
{
Span<int> items = new(array);
items.Sort(_comparer);
return items.ToArray();
}
[Benchmark]
public int[] SortedSet_ToArray()
{
SortedSet<int> items = new(array, _comparer);
return items.ToArray();
}
[Benchmark]
public int[] SortedSet_CopyTo()
{
SortedSet<int> items = new(array, _comparer);
int[] results = new int[items.Count];
items.CopyTo(results, 0);
return results;
}
}The result of 80 tests is as follows:
For the general result, although the conclusions are already obvious, I propose to test some of the best options from different approaches:
hidden text
using BenchmarkDotNet.Attributes;
namespace Benchmarks.Benchmarks.Arrays;
[MemoryDiagnoser]
public class ArrayReverseFaster
{
[Params(1000, 10_000, 100_000, 1_000_000, 100_000_000, 1_000_000_000)]
public int NumberCount;
private int[] array;
[GlobalSetup]
public void GlobalSetup()
{
array = Enumerable.Range(1, NumberCount).ToArray();
}
[Benchmark]
public int[] Array_Reverse_SameArray()
{
Array.Reverse(array);
return array;
}
[Benchmark]
public unsafe int[] For_Unsafe_SameArray()
{
fixed (int* arrayItem = array)
{
for (int i = 0, length = array.Length - 1; i < length / 2; i++)
{
int item = arrayItem[i];
arrayItem[i] = arrayItem[length - i];
arrayItem[length - i] = item;
}
}
return array;
}
[Benchmark]
public unsafe int[] For_Unsafe_SameArray_Length()
{
int length = array.Length - 1;
fixed (int* arrayItem = array)
{
for (int i = 0; i < length / 2; i++)
{
int item = arrayItem[i];
arrayItem[i] = arrayItem[length - i];
arrayItem[length - i] = item;
}
}
return array;
}
[Benchmark]
public unsafe int[] For_Unsafe_SameArray_Size()
{
int length = array.Length - 1;
int size = length / 2;
fixed (int* arrayItem = array)
{
for (int i = 0; i < size; i++)
{
int item = arrayItem[i];
arrayItem[i] = arrayItem[length - i];
arrayItem[length - i] = item;
}
}
return array;
}
[Benchmark]
public int[] Array_Reverse_ToArray()
{
int[] items = array.ToArray();
Array.Reverse(items);
return items;
}
[Benchmark]
public int[] Array_Reverse_CopyTo()
{
int[] results = new int[array.Length];
array.CopyTo(results, 0);
Array.Reverse(results);
return results;
}
[Benchmark]
public int[] Enumerable_ToArray()
{
return array.Reverse().ToArray();
}
[Benchmark]
public int[] Span_ToArray()
{
Span<int> items = new(array);
items.Reverse();
return items.ToArray();
}
}The result speaks for itself:
And for a snack, some code with https://referencesource.microsoft.comwhich sometimes pleases and surprises at the same time.
stack.ToArray() (namespace System.Collections):
// Copies the Stack to an array, in the same order Pop would return the items.
public virtual Object[] ToArray()
{
Contract.Ensures(Contract.Result<Object[]>() != null);
Object[] objArray = new Object[_size];
int i = 0;
while (i < _size)
{
objArray[i] = _array[_size - i - 1];
i++;
}
return objArray;
}List.ToArray() (namespace System.Collections.Generic):
// ToArray returns a new Object array containing the contents of the List.
// This requires copying the List, which is an O(n) operation.
public T[] ToArray()
{
Contract.Ensures(Contract.Result<T[]>() != null);
Contract.Ensures(Contract.Result<T[]>().Length == Count);
T[] array = new T[_size];
Array.Copy(_items, 0, array, 0, _size);
return array;
}Good luck to everyone and see you soon!
PS: almost all tests are extremely long (20 – 90+ minutes for 1 test) and if you repeat, it is better to reduce the sample.
