Уважаемые читатели, в этой статье я хочу рассказать о небольших тестах получения обратного массива и представить свои выводы. Тесты сделаны на .net 7.
Тестировал с использованием BenchmarkDotNet, так что каждый может проверить результаты и сделать свои выводы.
Сразу отмечу, что для тестов используется атрибут [GlobalSetup], что позволяет не переживать о стартовых данных, так как они будут «Executed once per each N value» и это нам и надо.
Для полной картины происходящего основные тесты идут на массивах с количеством элементов 1000, 10_000, 100_000, 1_000_000, 100_000_000, а самый последний с добавлением до 1_000_000_000 чисел.
Первые тесты связаны с обработкой исходного массива без получения нового, что не всегда верный выбор, но памяти почти всегда не требует (тесты покажут странность на крупной выборке).
Для старта используется обычный While, представленный в более удобной записи, чем аналоги на просторах сети:
[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;
}Не скажу, что тут все плохо, ведь под капотом там много работы с unsafe и разной «магии» для ускорения:
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);
}Для разнообразия проверим сортировку:
[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);
}
}Далее следует несколько вариантов цикла for, каждый из которых не совсем привычный:
[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;
}Для примера приведу 2 варианта, но далее в полном коде можно посмотреть все доступные решения. Отмечу, что столь простые с виду улучшения помогают чуть ускориться, но тут каждый сам выбирает как удобней делать.
Сайт https://sharplab.io показывает следующее на 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) */;
}
В то же время для 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) */;
}
И для ознакомления 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) */;
}Дополнительно в итоговом листинге представлена работа с unsafe и range в разных вариациях.
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;
}
}
Примечательно, что на предельных значениях везде будет, пусть и незначительный, но расход памяти.
Пришло время попробовать варианты, которые более практичны. Речь про возврат нового массива без изменения входного.
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;
}
}Итог 80-ти тестов следующий:
Для общего итога, хоть выводы уже очевидны, предлагаю протестировать несколько лучших вариантов из разных подходов:
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();
}
}Итог говорит сам за себя:
И на закуску немного кода с https://referencesource.microsoft.com, который иногда радует и удивляет одновременно.
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;
}Итого победители: Array и Span Reverse.
Всем удачи и до новых встреч!
P.S.: почти все тесты крайне длительные (20 - 90+ минут на 1 тест) и если повторять, лучше уменьшить выборку.