From f73ceeeb18b43671deebd59218179eeb8f4f9908 Mon Sep 17 00:00:00 2001 From: Stephen Toub Date: Fri, 24 Apr 2020 14:12:47 -0400 Subject: [PATCH] Improve Array.Sort(T[]) performance (#35297) * Improve Array.Sort(T[]) performance A variety of tweaks to improve `Array.Sort(T[])` performance and address a regression left over from moving the array sorting implementation from native to managed. The two most impactful are using `Unsafe.*` in `PickPivotAndPartition` to avoid bounds checks and aggressive inlining on `SwapIfGreater`. A few other small improvements to codegen round it out. I only made the unsafe changes in the `Sort(T[])` implementation, and not in the more complicated implementations, such as for `Sort(T[], Comparer)` and `Sort(TKey[], TValue[])`, but I did make some of the smaller changes for consistency across the file. * Address PR feedback, and more tweaks --- .../System.Private.CoreLib/src/System/Array.cs | 53 ++- .../System/Collections/Generic/ArraySortHelper.cs | 519 ++++++++++----------- .../src/System/ThrowHelper.cs | 6 + 3 files changed, 281 insertions(+), 297 deletions(-) diff --git a/src/libraries/System.Private.CoreLib/src/System/Array.cs b/src/libraries/System.Private.CoreLib/src/System/Array.cs index 2411ba2..40d3a06 100644 --- a/src/libraries/System.Private.CoreLib/src/System/Array.cs +++ b/src/libraries/System.Private.CoreLib/src/System/Array.cs @@ -7,6 +7,7 @@ using System.Collections.Generic; using System.Collections.ObjectModel; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; +using System.Numerics; using System.Reflection; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; @@ -26,6 +27,11 @@ namespace System internal const int MaxArrayLength = 0X7FEFFFFF; internal const int MaxByteArrayLength = 0x7FFFFFC7; + // This is the threshold where Introspective sort switches to Insertion sort. + // Empirically, 16 seems to speed up most cases without slowing down others, at least for integers. + // Large value types may benefit from a smaller number. + internal const int IntrosortSizeThreshold = 16; + // This ctor exists solely to prevent C# from generating a protected .ctor that violates the surface area. private protected Array() { } @@ -1916,11 +1922,11 @@ namespace System try { - IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(length)); + IntroSort(left, length + left - 1, 2 * (BitOperations.Log2((uint)length) + 1)); } catch (IndexOutOfRangeException) { - IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + ThrowHelper.ThrowArgumentException_BadComparer(comparer); } catch (Exception e) { @@ -1930,20 +1936,22 @@ namespace System private void IntroSort(int lo, int hi, int depthLimit) { + Debug.Assert(hi > lo); + Debug.Assert(depthLimit >= 0); + while (hi > lo) { int partitionSize = hi - lo + 1; - if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) + if (partitionSize <= IntrosortSizeThreshold) { - if (partitionSize == 1) - { - return; - } + Debug.Assert(partitionSize >= 2); + if (partitionSize == 2) { SwapIfGreater(lo, hi); return; } + if (partitionSize == 3) { SwapIfGreater(lo, hi - 1); @@ -1971,8 +1979,11 @@ namespace System private int PickPivotAndPartition(int lo, int hi) { + Debug.Assert(hi - lo >= IntrosortSizeThreshold); + // Compute median-of-three. But also partition them, since we've done the comparison. int mid = lo + (hi - lo) / 2; + // Sort lo, mid and hi appropriately, then pick mid as the pivot. SwapIfGreater(lo, mid); SwapIfGreater(lo, hi); @@ -1994,7 +2005,10 @@ namespace System } // Put pivot in the right location. - Swap(left, hi - 1); + if (left != hi - 1) + { + Swap(left, hi - 1); + } return left; } @@ -2122,11 +2136,11 @@ namespace System try { - IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(length)); + IntroSort(left, length + left - 1, 2 * (BitOperations.Log2((uint)length) + 1)); } catch (IndexOutOfRangeException) { - IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + ThrowHelper.ThrowArgumentException_BadComparer(comparer); } catch (Exception e) { @@ -2136,20 +2150,22 @@ namespace System private void IntroSort(int lo, int hi, int depthLimit) { + Debug.Assert(hi > lo); + Debug.Assert(depthLimit >= 0); + while (hi > lo) { int partitionSize = hi - lo + 1; - if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) + if (partitionSize <= IntrosortSizeThreshold) { - if (partitionSize == 1) - { - return; - } + Debug.Assert(partitionSize >= 2); + if (partitionSize == 2) { SwapIfGreater(lo, hi); return; } + if (partitionSize == 3) { SwapIfGreater(lo, hi - 1); @@ -2177,6 +2193,8 @@ namespace System private int PickPivotAndPartition(int lo, int hi) { + Debug.Assert(hi - lo >= IntrosortSizeThreshold); + // Compute median-of-three. But also partition them, since we've done the comparison. int mid = lo + (hi - lo) / 2; @@ -2200,7 +2218,10 @@ namespace System } // Put pivot in the right location. - Swap(left, hi - 1); + if (left != hi - 1) + { + Swap(left, hi - 1); + } return left; } diff --git a/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/ArraySortHelper.cs b/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/ArraySortHelper.cs index 0ebaafc..c0da643 100644 --- a/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/ArraySortHelper.cs +++ b/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/ArraySortHelper.cs @@ -2,50 +2,23 @@ // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. -/*============================================================ -** -** -** -** -** -** Purpose: class to sort arrays -** -** -===========================================================*/ - using System.Diagnostics; -using System.Diagnostics.CodeAnalysis; +using System.Numerics; using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; +using Internal.Runtime.CompilerServices; + +#pragma warning disable SA1121 // explicitly using type aliases instead of built-in types +#if TARGET_64BIT +using nint = System.Int64; +#else +using nint = System.Int32; +#endif namespace System.Collections.Generic { #region ArraySortHelper for single arrays - internal static class IntrospectiveSortUtilities - { - // This is the threshold where Introspective sort switches to Insertion sort. - // Empirically, 16 seems to speed up most cases without slowing down others, at least for integers. - // Large value types may benefit from a smaller number. - internal const int IntrosortSizeThreshold = 16; - - internal static int FloorLog2PlusOne(int n) - { - int result = 0; - while (n >= 1) - { - result++; - n /= 2; - } - return result; - } - - [DoesNotReturn] - internal static void ThrowOrIgnoreBadComparer(object? comparer) - { - throw new ArgumentException(SR.Format(SR.Arg_BogusIComparer, comparer)); - } - } - internal partial class ArraySortHelper { #region IArraySortHelper Members @@ -61,11 +34,11 @@ namespace System.Collections.Generic } catch (IndexOutOfRangeException) { - IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + ThrowHelper.ThrowArgumentException_BadComparer(comparer); } catch (Exception e) { - throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e); } } @@ -78,7 +51,8 @@ namespace System.Collections.Generic } catch (Exception e) { - throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e); + return 0; } } @@ -95,11 +69,11 @@ namespace System.Collections.Generic } catch (IndexOutOfRangeException) { - IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + ThrowHelper.ThrowArgumentException_BadComparer(comparer); } catch (Exception e) { - throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e); } } @@ -131,26 +105,24 @@ namespace System.Collections.Generic private static void SwapIfGreater(Span keys, Comparison comparer, int i, int j) { - if (i != j) + Debug.Assert(i != j); + + if (comparer(keys[i], keys[j]) > 0) { - if (comparer(keys[i], keys[j]) > 0) - { - T key = keys[i]; - keys[i] = keys[j]; - keys[j] = key; - } + T key = keys[i]; + keys[i] = keys[j]; + keys[j] = key; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static void Swap(Span a, int i, int j) { - if (i != j) - { - T t = a[i]; - a[i] = a[j]; - a[j] = t; - } + Debug.Assert(i != j); + + T t = a[i]; + a[i] = a[j]; + a[j] = t; } internal static void IntrospectiveSort(Span keys, Comparison comparer) @@ -159,53 +131,51 @@ namespace System.Collections.Generic if (keys.Length > 1) { - IntroSort(keys, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(keys.Length), comparer); + IntroSort(keys, 2 * (BitOperations.Log2((uint)keys.Length) + 1), comparer); } } private static void IntroSort(Span keys, int depthLimit, Comparison comparer) { - int lo = 0; - int hi = keys.Length - 1; - + Debug.Assert(!keys.IsEmpty); + Debug.Assert(depthLimit >= 0); Debug.Assert(comparer != null); - while (hi > lo) + int hi = keys.Length - 1; + while (hi > 0) { - int partitionSize = hi - lo + 1; - if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) + int partitionSize = hi + 1; + + if (partitionSize <= Array.IntrosortSizeThreshold) { - if (partitionSize == 1) - { - return; - } + Debug.Assert(partitionSize >= 2); if (partitionSize == 2) { - SwapIfGreater(keys, comparer, lo, hi); + SwapIfGreater(keys, comparer, 0, hi); return; } if (partitionSize == 3) { - SwapIfGreater(keys, comparer, lo, hi - 1); - SwapIfGreater(keys, comparer, lo, hi); + SwapIfGreater(keys, comparer, 0, hi - 1); + SwapIfGreater(keys, comparer, 0, hi); SwapIfGreater(keys, comparer, hi - 1, hi); return; } - InsertionSort(keys[lo..(hi+1)], comparer); + InsertionSort(keys.Slice(0, hi+1), comparer); return; } if (depthLimit == 0) { - HeapSort(keys[lo..(hi+1)], comparer); + HeapSort(keys.Slice(0, hi+1), comparer); return; } depthLimit--; - int p = PickPivotAndPartition(keys[lo..(hi+1)], comparer); + int p = PickPivotAndPartition(keys.Slice(0, hi+1), comparer); // Note we've already partitioned around the pivot and do not have to move the pivot again. IntroSort(keys[(p+1)..(hi+1)], depthLimit, comparer); @@ -215,23 +185,22 @@ namespace System.Collections.Generic private static int PickPivotAndPartition(Span keys, Comparison comparer) { + Debug.Assert(keys.Length >= Array.IntrosortSizeThreshold); Debug.Assert(comparer != null); - Debug.Assert(!keys.IsEmpty); - int lo = 0; int hi = keys.Length - 1; // Compute median-of-three. But also partition them, since we've done the comparison. - int middle = lo + ((hi - lo) / 2); + int middle = hi >> 1; // Sort lo, mid and hi appropriately, then pick mid as the pivot. - SwapIfGreater(keys, comparer, lo, middle); // swap the low with the mid point - SwapIfGreater(keys, comparer, lo, hi); // swap the low with the high + SwapIfGreater(keys, comparer, 0, middle); // swap the low with the mid point + SwapIfGreater(keys, comparer, 0, hi); // swap the low with the high SwapIfGreater(keys, comparer, middle, hi); // swap the middle with the high T pivot = keys[middle]; Swap(keys, middle, hi - 1); - int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. + int left = 0, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. while (left < right) { @@ -245,7 +214,10 @@ namespace System.Collections.Generic } // Put pivot in the right location. - Swap(keys, left, hi - 1); + if (left != hi - 1) + { + Swap(keys, left, hi - 1); + } return left; } @@ -254,20 +226,16 @@ namespace System.Collections.Generic Debug.Assert(comparer != null); Debug.Assert(!keys.IsEmpty); - int lo = 0; - int hi = keys.Length - 1; - - int n = hi - lo + 1; - - for (int i = n / 2; i >= 1; i--) + int n = keys.Length; + for (int i = n >> 1; i >= 1; i--) { - DownHeap(keys, i, n, lo, comparer); + DownHeap(keys, i, n, 0, comparer); } for (int i = n; i > 1; i--) { - Swap(keys, lo, lo + i - 1); - DownHeap(keys, 1, i - 1, lo, comparer); + Swap(keys, 0, i - 1); + DownHeap(keys, 1, i - 1, 0, comparer); } } @@ -278,7 +246,7 @@ namespace System.Collections.Generic Debug.Assert(lo < keys.Length); T d = keys[lo + i - 1]; - while (i <= n / 2) + while (i <= n >> 1) { int child = 2 * i; if (child < n && comparer(keys[lo + child - 1], keys[lo + child]) < 0) @@ -327,7 +295,10 @@ namespace System.Collections.Generic { if (comparer == null || comparer == Comparer.Default) { - IntrospectiveSort(keys); + if (keys.Length > 1) + { + IntroSort(keys, 2 * (BitOperations.Log2((uint)keys.Length) + 1)); + } } else { @@ -336,11 +307,11 @@ namespace System.Collections.Generic } catch (IndexOutOfRangeException) { - IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + ThrowHelper.ThrowArgumentException_BadComparer(comparer); } catch (Exception e) { - throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e); } } @@ -362,7 +333,8 @@ namespace System.Collections.Generic } catch (Exception e) { - throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e); + return 0; } } @@ -406,147 +378,140 @@ namespace System.Collections.Generic return ~lo; } - private static void SwapIfGreater(Span keys, int i, int j) + /// Swaps the values in the two references if the first is greater than the second. + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static void SwapIfGreater(ref T i, ref T j) { - Debug.Assert(0 <= i && i < keys.Length); - Debug.Assert(0 <= j && j < keys.Length); - - if (i != j) + if (i != null && i.CompareTo(j) > 0) { - if (keys[i] != null && keys[i].CompareTo(keys[j]) > 0) - { - T key = keys[i]; - keys[i] = keys[j]; - keys[j] = key; - } + Swap(ref i, ref j); } } + /// Swaps the values in the two references, regardless of whether the two references are the same. [MethodImpl(MethodImplOptions.AggressiveInlining)] - private static void Swap(Span a, int i, int j) + private static void Swap(ref T i, ref T j) { - if (i != j) - { - T t = a[i]; - a[i] = a[j]; - a[j] = t; - } - } + Debug.Assert(!Unsafe.AreSame(ref i, ref j)); - internal static void IntrospectiveSort(Span keys) - { - if (keys.Length > 1) - { - IntroSort(keys, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(keys.Length)); - } + T t = i; + i = j; + j = t; } private static void IntroSort(Span keys, int depthLimit) { - int lo = 0; - int hi = keys.Length - 1; + Debug.Assert(!keys.IsEmpty); + Debug.Assert(depthLimit >= 0); - while (hi > lo) + int hi = keys.Length - 1; + while (hi > 0) { - int partitionSize = hi - lo + 1; - if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) + int partitionSize = hi + 1; + + if (partitionSize <= Array.IntrosortSizeThreshold) { - if (partitionSize == 1) - { - return; - } + Debug.Assert(partitionSize >= 2); + if (partitionSize == 2) { - SwapIfGreater(keys, lo, hi); + SwapIfGreater(ref keys[0], ref keys[1]); return; } + if (partitionSize == 3) { - SwapIfGreater(keys, lo, hi - 1); - SwapIfGreater(keys, lo, hi); - SwapIfGreater(keys, hi - 1, hi); + ref T hiRef = ref keys[2]; + ref T him1Ref = ref keys[1]; + ref T loRef = ref keys[0]; + + SwapIfGreater(ref loRef, ref him1Ref); + SwapIfGreater(ref loRef, ref hiRef); + SwapIfGreater(ref him1Ref, ref hiRef); return; } - InsertionSort(keys[lo..(hi+1)]); + InsertionSort(keys.Slice(0, partitionSize)); return; } if (depthLimit == 0) { - HeapSort(keys[lo..(hi+1)]); + HeapSort(keys.Slice(0, partitionSize)); return; } depthLimit--; - int p = PickPivotAndPartition(keys[lo..(hi+1)]); + int p = PickPivotAndPartition(keys.Slice(0, partitionSize)); // Note we've already partitioned around the pivot and do not have to move the pivot again. - IntroSort(keys[(p+1)..(hi+1)], depthLimit); + IntroSort(keys[(p+1)..partitionSize], depthLimit); hi = p - 1; } } private static int PickPivotAndPartition(Span keys) { - Debug.Assert(!keys.IsEmpty); - - int lo = 0; - int hi = keys.Length - 1; - - // Compute median-of-three. But also partition them, since we've done the comparison. - int middle = lo + ((hi - lo) / 2); + Debug.Assert(keys.Length >= Array.IntrosortSizeThreshold); - // Sort lo, mid and hi appropriately, then pick mid as the pivot. - SwapIfGreater(keys, lo, middle); // swap the low with the mid point - SwapIfGreater(keys, lo, hi); // swap the low with the high - SwapIfGreater(keys, middle, hi); // swap the middle with the high + // Use median-of-three to select a pivot. Grab a reference to the 0th, Length-1th, and Length/2th elements, and sort them. + ref T zeroRef = ref MemoryMarshal.GetReference(keys); + ref T lastRef = ref Unsafe.Add(ref zeroRef, keys.Length - 1); + ref T middleRef = ref Unsafe.Add(ref zeroRef, (keys.Length - 1) >> 1); + SwapIfGreater(ref zeroRef, ref middleRef); + SwapIfGreater(ref zeroRef, ref lastRef); + SwapIfGreater(ref middleRef, ref lastRef); - T pivot = keys[middle]; - Swap(keys, middle, hi - 1); - int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. + // Select the middle value as the pivot, and move it to be just before the last element. + ref T nextToLastRef = ref Unsafe.Add(ref zeroRef, keys.Length - 2); + T pivot = middleRef; + Swap(ref middleRef, ref nextToLastRef); - while (left < right) + // Walk the left and right pointers, swapping elements as necessary, until they cross. + ref T leftRef = ref zeroRef, rightRef = ref nextToLastRef; + while (Unsafe.IsAddressLessThan(ref leftRef, ref rightRef)) { if (pivot == null) { - while (left < (hi - 1) && keys[++left] == null) ; - while (right > lo && keys[--right] != null) ; + while (Unsafe.IsAddressLessThan(ref leftRef, ref nextToLastRef) && (leftRef = ref Unsafe.Add(ref leftRef, 1)) == null) ; + while (Unsafe.IsAddressGreaterThan(ref rightRef, ref zeroRef) && (rightRef = ref Unsafe.Add(ref rightRef, -1)) == null) ; } else { - while (pivot.CompareTo(keys[++left]) > 0) ; - while (pivot.CompareTo(keys[--right]) < 0) ; + while (Unsafe.IsAddressLessThan(ref leftRef, ref nextToLastRef) && pivot.CompareTo(leftRef = ref Unsafe.Add(ref leftRef, 1)) > 0) ; + while (Unsafe.IsAddressGreaterThan(ref rightRef, ref zeroRef) && pivot.CompareTo(rightRef = ref Unsafe.Add(ref rightRef, -1)) < 0) ; } - if (left >= right) + if (!Unsafe.IsAddressLessThan(ref leftRef, ref rightRef)) + { break; + } - Swap(keys, left, right); + Swap(ref leftRef, ref rightRef); } - // Put pivot in the right location. - Swap(keys, left, hi - 1); - return left; + // Put the pivot in the correct location. + if (!Unsafe.AreSame(ref leftRef, ref nextToLastRef)) + { + Swap(ref leftRef, ref nextToLastRef); + } + return (int)((nint)Unsafe.ByteOffset(ref zeroRef, ref leftRef) / Unsafe.SizeOf()); } private static void HeapSort(Span keys) { Debug.Assert(!keys.IsEmpty); - int lo = 0; - int hi = keys.Length - 1; - - int n = hi - lo + 1; - for (int i = n / 2; i >= 1; i--) + int n = keys.Length; + for (int i = n >> 1; i >= 1; i--) { - DownHeap(keys, i, n, lo); + DownHeap(keys, i, n, 0); } for (int i = n; i > 1; i--) { - Swap(keys, lo, lo + i - 1); - DownHeap(keys, 1, i - 1, lo); + Swap(ref keys[0], ref keys[i - 1]); + DownHeap(keys, 1, i - 1, 0); } } @@ -556,7 +521,7 @@ namespace System.Collections.Generic Debug.Assert(lo < keys.Length); T d = keys[lo + i - 1]; - while (i <= n / 2) + while (i <= n >> 1) { int child = 2 * i; if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0)) @@ -578,16 +543,16 @@ namespace System.Collections.Generic { for (int i = 0; i < keys.Length - 1; i++) { - T t = keys[i + 1]; + T t = Unsafe.Add(ref MemoryMarshal.GetReference(keys), i + 1); int j = i; - while (j >= 0 && (t == null || t.CompareTo(keys[j]) < 0)) + while (j >= 0 && (t == null || t.CompareTo(Unsafe.Add(ref MemoryMarshal.GetReference(keys), j)) < 0)) { - keys[j + 1] = keys[j]; + Unsafe.Add(ref MemoryMarshal.GetReference(keys), j + 1) = Unsafe.Add(ref MemoryMarshal.GetReference(keys), j); j--; } - keys[j + 1] = t; + Unsafe.Add(ref MemoryMarshal.GetReference(keys), j + 1) = t; } } } @@ -608,11 +573,11 @@ namespace System.Collections.Generic } catch (IndexOutOfRangeException) { - IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + ThrowHelper.ThrowArgumentException_BadComparer(comparer); } catch (Exception e) { - throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e); } } @@ -621,35 +586,32 @@ namespace System.Collections.Generic Debug.Assert(comparer != null); Debug.Assert(0 <= i && i < keys.Length && i < values.Length); Debug.Assert(0 <= j && j < keys.Length && j < values.Length); + Debug.Assert(i != j); - if (i != j) + if (comparer.Compare(keys[i], keys[j]) > 0) { - if (comparer.Compare(keys[i], keys[j]) > 0) - { - TKey key = keys[i]; - keys[i] = keys[j]; - keys[j] = key; + TKey key = keys[i]; + keys[i] = keys[j]; + keys[j] = key; - TValue value = values[i]; - values[i] = values[j]; - values[j] = value; - } + TValue value = values[i]; + values[i] = values[j]; + values[j] = value; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static void Swap(Span keys, Span values, int i, int j) { - if (i != j) - { - TKey k = keys[i]; - keys[i] = keys[j]; - keys[j] = k; + Debug.Assert(i != j); - TValue v = values[i]; - values[i] = values[j]; - values[j] = v; - } + TKey k = keys[i]; + keys[i] = keys[j]; + keys[j] = k; + + TValue v = values[i]; + values[i] = values[j]; + values[j] = v; } internal static void IntrospectiveSort(Span keys, Span values, IComparer comparer) @@ -659,79 +621,77 @@ namespace System.Collections.Generic if (keys.Length > 1) { - IntroSort(keys, values, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(keys.Length), comparer); + IntroSort(keys, values, 2 * (BitOperations.Log2((uint)keys.Length) + 1), comparer); } } private static void IntroSort(Span keys, Span values, int depthLimit, IComparer comparer) { + Debug.Assert(!keys.IsEmpty); + Debug.Assert(values.Length == keys.Length); + Debug.Assert(depthLimit >= 0); Debug.Assert(comparer != null); - int lo = 0; int hi = keys.Length - 1; - - while (hi > lo) + while (hi > 0) { - int partitionSize = hi - lo + 1; - if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) + int partitionSize = hi + 1; + + if (partitionSize <= Array.IntrosortSizeThreshold) { - if (partitionSize == 1) - { - return; - } + Debug.Assert(partitionSize >= 2); if (partitionSize == 2) { - SwapIfGreaterWithValues(keys, values, comparer, lo, hi); + SwapIfGreaterWithValues(keys, values, comparer, 0, hi); return; } if (partitionSize == 3) { - SwapIfGreaterWithValues(keys, values, comparer, lo, hi - 1); - SwapIfGreaterWithValues(keys, values, comparer, lo, hi); + SwapIfGreaterWithValues(keys, values, comparer, 0, hi - 1); + SwapIfGreaterWithValues(keys, values, comparer, 0, hi); SwapIfGreaterWithValues(keys, values, comparer, hi - 1, hi); return; } - InsertionSort(keys[lo..(hi+1)], values[lo..(hi+1)], comparer); + InsertionSort(keys.Slice(0, partitionSize), values.Slice(0, partitionSize), comparer); return; } if (depthLimit == 0) { - HeapSort(keys[lo..(hi+1)], values[lo..(hi+1)], comparer); + HeapSort(keys.Slice(0, partitionSize), values.Slice(0, partitionSize), comparer); return; } depthLimit--; - int p = PickPivotAndPartition(keys[lo..(hi+1)], values[lo..(hi+1)], comparer); + int p = PickPivotAndPartition(keys.Slice(0, partitionSize), values.Slice(0, partitionSize), comparer); // Note we've already partitioned around the pivot and do not have to move the pivot again. - IntroSort(keys[(p+1)..(hi+1)], values[(p+1)..(hi+1)], depthLimit, comparer); + IntroSort(keys[(p+1)..partitionSize], values[(p+1)..partitionSize], depthLimit, comparer); hi = p - 1; } } private static int PickPivotAndPartition(Span keys, Span values, IComparer comparer) { + Debug.Assert(keys.Length >= Array.IntrosortSizeThreshold); Debug.Assert(comparer != null); - Debug.Assert(!keys.IsEmpty); - int lo = 0; int hi = keys.Length - 1; // Compute median-of-three. But also partition them, since we've done the comparison. - int middle = lo + ((hi - lo) / 2); + int middle = hi >> 1; // Sort lo, mid and hi appropriately, then pick mid as the pivot. - SwapIfGreaterWithValues(keys, values, comparer, lo, middle); // swap the low with the mid point - SwapIfGreaterWithValues(keys, values, comparer, lo, hi); // swap the low with the high + SwapIfGreaterWithValues(keys, values, comparer, 0, middle); // swap the low with the mid point + SwapIfGreaterWithValues(keys, values, comparer, 0, hi); // swap the low with the high SwapIfGreaterWithValues(keys, values, comparer, middle, hi); // swap the middle with the high TKey pivot = keys[middle]; Swap(keys, values, middle, hi - 1); - int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. + int left = 0, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. while (left < right) { @@ -745,7 +705,10 @@ namespace System.Collections.Generic } // Put pivot in the right location. - Swap(keys, values, left, hi - 1); + if (left != hi - 1) + { + Swap(keys, values, left, hi - 1); + } return left; } @@ -754,19 +717,16 @@ namespace System.Collections.Generic Debug.Assert(comparer != null); Debug.Assert(!keys.IsEmpty); - int lo = 0; - int hi = keys.Length - 1; - - int n = hi - lo + 1; - for (int i = n / 2; i >= 1; i--) + int n = keys.Length; + for (int i = n >> 1; i >= 1; i--) { - DownHeap(keys, values, i, n, lo, comparer); + DownHeap(keys, values, i, n, 0, comparer); } for (int i = n; i > 1; i--) { - Swap(keys, values, lo, lo + i - 1); - DownHeap(keys, values, 1, i - 1, lo, comparer); + Swap(keys, values, 0, i - 1); + DownHeap(keys, values, 1, i - 1, 0, comparer); } } @@ -779,7 +739,7 @@ namespace System.Collections.Generic TKey d = keys[lo + i - 1]; TValue dValue = values[lo + i - 1]; - while (i <= n / 2) + while (i <= n >> 1) { int child = 2 * i; if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0) @@ -842,44 +802,42 @@ namespace System.Collections.Generic } catch (IndexOutOfRangeException) { - IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + ThrowHelper.ThrowArgumentException_BadComparer(comparer); } catch (Exception e) { - throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e); } } private static void SwapIfGreaterWithValues(Span keys, Span values, int i, int j) { - if (i != j) + Debug.Assert(i != j); + + if (keys[i] != null && keys[i].CompareTo(keys[j]) > 0) { - if (keys[i] != null && keys[i].CompareTo(keys[j]) > 0) - { - TKey key = keys[i]; - keys[i] = keys[j]; - keys[j] = key; + TKey key = keys[i]; + keys[i] = keys[j]; + keys[j] = key; - TValue value = values[i]; - values[i] = values[j]; - values[j] = value; - } + TValue value = values[i]; + values[i] = values[j]; + values[j] = value; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static void Swap(Span keys, Span values, int i, int j) { - if (i != j) - { - TKey k = keys[i]; - keys[i] = keys[j]; - keys[j] = k; + Debug.Assert(i != j); - TValue v = values[i]; - values[i] = values[j]; - values[j] = v; - } + TKey k = keys[i]; + keys[i] = keys[j]; + keys[j] = k; + + TValue v = values[i]; + values[i] = values[j]; + values[j] = v; } internal static void IntrospectiveSort(Span keys, Span values) @@ -888,83 +846,82 @@ namespace System.Collections.Generic if (keys.Length > 1) { - IntroSort(keys, values, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(keys.Length)); + IntroSort(keys, values, 2 * (BitOperations.Log2((uint)keys.Length) + 1)); } } private static void IntroSort(Span keys, Span values, int depthLimit) { - int lo = 0; - int hi = keys.Length - 1; + Debug.Assert(!keys.IsEmpty); + Debug.Assert(values.Length == keys.Length); + Debug.Assert(depthLimit >= 0); - while (hi > lo) + int hi = keys.Length - 1; + while (hi > 0) { - int partitionSize = hi - lo + 1; - if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) + int partitionSize = hi + 1; + + if (partitionSize <= Array.IntrosortSizeThreshold) { - if (partitionSize == 1) - { - return; - } + Debug.Assert(partitionSize >= 2); if (partitionSize == 2) { - SwapIfGreaterWithValues(keys, values, lo, hi); + SwapIfGreaterWithValues(keys, values, 0, hi); return; } if (partitionSize == 3) { - SwapIfGreaterWithValues(keys, values, lo, hi - 1); - SwapIfGreaterWithValues(keys, values, lo, hi); + SwapIfGreaterWithValues(keys, values, 0, hi - 1); + SwapIfGreaterWithValues(keys, values, 0, hi); SwapIfGreaterWithValues(keys, values, hi - 1, hi); return; } - InsertionSort(keys[lo..(hi+1)], values[lo..(hi+1)]); + InsertionSort(keys.Slice(0, partitionSize), values.Slice(0, partitionSize)); return; } if (depthLimit == 0) { - HeapSort(keys[lo..(hi+1)], values[lo..(hi+1)]); + HeapSort(keys.Slice(0, partitionSize), values.Slice(0, partitionSize)); return; } depthLimit--; - int p = PickPivotAndPartition(keys[lo..(hi+1)], values[lo..(hi+1)]); + int p = PickPivotAndPartition(keys.Slice(0, partitionSize), values.Slice(0, partitionSize)); // Note we've already partitioned around the pivot and do not have to move the pivot again. - IntroSort(keys[(p+1)..(hi+1)], values[(p+1)..(hi+1)], depthLimit); + IntroSort(keys[(p+1)..partitionSize], values[(p+1)..partitionSize], depthLimit); hi = p - 1; } } private static int PickPivotAndPartition(Span keys, Span values) { - Debug.Assert(!keys.IsEmpty); + Debug.Assert(keys.Length >= Array.IntrosortSizeThreshold); - int lo = 0; int hi = keys.Length - 1; // Compute median-of-three. But also partition them, since we've done the comparison. - int middle = lo + ((hi - lo) / 2); + int middle = hi >> 1; // Sort lo, mid and hi appropriately, then pick mid as the pivot. - SwapIfGreaterWithValues(keys, values, lo, middle); // swap the low with the mid point - SwapIfGreaterWithValues(keys, values, lo, hi); // swap the low with the high + SwapIfGreaterWithValues(keys, values, 0, middle); // swap the low with the mid point + SwapIfGreaterWithValues(keys, values, 0, hi); // swap the low with the high SwapIfGreaterWithValues(keys, values, middle, hi); // swap the middle with the high TKey pivot = keys[middle]; Swap(keys, values, middle, hi - 1); - int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. + int left = 0, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. while (left < right) { if (pivot == null) { while (left < (hi - 1) && keys[++left] == null) ; - while (right > lo && keys[--right] != null) ; + while (right > 0 && keys[--right] != null) ; } else { @@ -979,7 +936,10 @@ namespace System.Collections.Generic } // Put pivot in the right location. - Swap(keys, values, left, hi - 1); + if (left != hi - 1) + { + Swap(keys, values, left, hi - 1); + } return left; } @@ -987,19 +947,16 @@ namespace System.Collections.Generic { Debug.Assert(!keys.IsEmpty); - int lo = 0; - int hi = keys.Length - 1; - - int n = hi - lo + 1; - for (int i = n / 2; i >= 1; i--) + int n = keys.Length; + for (int i = n >> 1; i >= 1; i--) { - DownHeap(keys, values, i, n, lo); + DownHeap(keys, values, i, n, 0); } for (int i = n; i > 1; i--) { - Swap(keys, values, lo, lo + i - 1); - DownHeap(keys, values, 1, i - 1, lo); + Swap(keys, values, 0, i - 1); + DownHeap(keys, values, 1, i - 1, 0); } } @@ -1011,7 +968,7 @@ namespace System.Collections.Generic TKey d = keys[lo + i - 1]; TValue dValue = values[lo + i - 1]; - while (i <= n / 2) + while (i <= n >> 1) { int child = 2 * i; if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0)) diff --git a/src/libraries/System.Private.CoreLib/src/System/ThrowHelper.cs b/src/libraries/System.Private.CoreLib/src/System/ThrowHelper.cs index 8ddc596..cf01b03 100644 --- a/src/libraries/System.Private.CoreLib/src/System/ThrowHelper.cs +++ b/src/libraries/System.Private.CoreLib/src/System/ThrowHelper.cs @@ -97,6 +97,12 @@ namespace System } [DoesNotReturn] + internal static void ThrowArgumentException_BadComparer(object? comparer) + { + throw new ArgumentException(SR.Format(SR.Arg_BogusIComparer, comparer)); + } + + [DoesNotReturn] internal static void ThrowIndexArgumentOutOfRange_NeedNonNegNumException() { throw GetArgumentOutOfRangeException(ExceptionArgument.index, -- 2.7.4