Уважаемые читатели, в этой статье я хочу рассказать о небольших тестах получения обратного массива и представить свои выводы. Тесты сделаны на .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 тест) и если повторять, лучше уменьшить выборку.
