From b3116a8f20d7ce04af90963cef537f0d0988b173 Mon Sep 17 00:00:00 2001 From: Mike Danes Date: Wed, 7 Dec 2016 19:38:02 +0200 Subject: [PATCH] Change ArraySortHelper to use Comparison The Array/List.Sort overloads that take a Comparison have worse performance than the ones that take a IComparer. That's because sorting is implemented around IComparer and a Comparison needs to be wrapped in a comparer object to be used. At the same time, interface calls are slower than delegate calls so the existing implementation doesn't offer the best performance even when the IComparer based overloads are used. By changing the implementation to use Comparison we avoid interface calls in both cases. When IComparer overloads are used a Comparison delegate is created from IComparer.Compare, that's an extra object allocation but sorting is faster and we avoid having two separate sorting implementations. Commit migrated from https://github.com/dotnet/coreclr/commit/1cf86165849ffb0ab909078ef09f124f898f0461 --- src/coreclr/src/mscorlib/src/System/Array.cs | 3 +- .../System/Collections/Generic/ArraySortHelper.cs | 94 ++++++++++++++++------ .../src/System/Collections/Generic/List.cs | 3 +- .../src/System/Diagnostics/Eventing/EventSource.cs | 2 +- 4 files changed, 71 insertions(+), 31 deletions(-) diff --git a/src/coreclr/src/mscorlib/src/System/Array.cs b/src/coreclr/src/mscorlib/src/System/Array.cs index eb08700..586df7a 100644 --- a/src/coreclr/src/mscorlib/src/System/Array.cs +++ b/src/coreclr/src/mscorlib/src/System/Array.cs @@ -1933,8 +1933,7 @@ namespace System { } Contract.EndContractBlock(); - IComparer comparer = Comparer.Create(comparison); - Array.Sort(array, comparer); + ArraySortHelper.Sort(array, 0, array.Length, comparison); } public static bool TrueForAll(T[] array, Predicate match) { diff --git a/src/coreclr/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs b/src/coreclr/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs index 8f5d690..a03aa62 100644 --- a/src/coreclr/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs +++ b/src/coreclr/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs @@ -107,15 +107,15 @@ namespace System.Collections.Generic // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort. - IntrospectiveSort(keys, index, length, comparer); + IntrospectiveSort(keys, index, length, comparer.Compare); #else if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) { - IntrospectiveSort(keys, index, length, comparer); + IntrospectiveSort(keys, index, length, comparer.Compare); } else { - DepthLimitedQuickSort(keys, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold); + DepthLimitedQuickSort(keys, index, length + index - 1, comparer.Compare, IntrospectiveSortUtilities.QuickSortDepthThreshold); } #endif } @@ -148,6 +148,42 @@ namespace System.Collections.Generic #endregion + internal static void Sort(T[] keys, int index, int length, Comparison comparer) + { + Contract.Assert(keys != null, "Check the arguments in the caller!"); + Contract.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); + Contract.Assert(comparer != null, "Check the arguments in the caller!"); + + // Add a try block here to detect bogus comparisons + try + { +#if FEATURE_CORECLR + // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade + // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka + // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort. + + IntrospectiveSort(keys, index, length, comparer); +#else + if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) + { + IntrospectiveSort(keys, index, length, comparer); + } + else + { + DepthLimitedQuickSort(keys, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold); + } +#endif + } + catch (IndexOutOfRangeException) + { + IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + } + catch (Exception e) + { + throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + } + } + internal static int InternalBinarySearch(T[] array, int index, int length, T value, IComparer comparer) { Contract.Requires(array != null, "Check the arguments in the caller!"); @@ -174,11 +210,11 @@ namespace System.Collections.Generic return ~lo; } - private static void SwapIfGreater(T[] keys, IComparer comparer, int a, int b) + private static void SwapIfGreater(T[] keys, Comparison comparer, int a, int b) { if (a != b) { - if (comparer.Compare(keys[a], keys[b]) > 0) + if (comparer(keys[a], keys[b]) > 0) { T key = keys[a]; keys[a] = keys[b]; @@ -189,7 +225,7 @@ namespace System.Collections.Generic private static void Swap(T[] a, int i, int j) { - if(i != j) + if (i != j) { T t = a[i]; a[i] = a[j]; @@ -197,7 +233,8 @@ namespace System.Collections.Generic } } - internal static void DepthLimitedQuickSort(T[] keys, int left, int right, IComparer comparer, int depthLimit) +#if !FEATURE_CORECLR + internal static void DepthLimitedQuickSort(T[] keys, int left, int right, Comparison comparer, int depthLimit) { do { @@ -221,8 +258,8 @@ namespace System.Collections.Generic T x = keys[middle]; do { - while (comparer.Compare(keys[i], x) < 0) i++; - while (comparer.Compare(x, keys[j]) < 0) j--; + while (comparer(keys[i], x) < 0) i++; + while (comparer(x, keys[j]) < 0) j--; Contract.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?"); if (i > j) break; if (i < j) @@ -252,8 +289,9 @@ namespace System.Collections.Generic } } while (left < right); } +#endif - internal static void IntrospectiveSort(T[] keys, int left, int length, IComparer comparer) + internal static void IntrospectiveSort(T[] keys, int left, int length, Comparison comparer) { Contract.Requires(keys != null); Contract.Requires(comparer != null); @@ -268,7 +306,7 @@ namespace System.Collections.Generic IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer); } - private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer comparer) + private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, Comparison comparer) { Contract.Requires(keys != null); Contract.Requires(comparer != null); @@ -315,7 +353,7 @@ namespace System.Collections.Generic } } - private static int PickPivotAndPartition(T[] keys, int lo, int hi, IComparer comparer) + private static int PickPivotAndPartition(T[] keys, int lo, int hi, Comparison comparer) { Contract.Requires(keys != null); Contract.Requires(comparer != null); @@ -338,8 +376,8 @@ namespace System.Collections.Generic while (left < right) { - while (comparer.Compare(keys[++left], pivot) < 0) ; - while (comparer.Compare(pivot, keys[--right]) < 0) ; + while (comparer(keys[++left], pivot) < 0) ; + while (comparer(pivot, keys[--right]) < 0) ; if (left >= right) break; @@ -352,7 +390,7 @@ namespace System.Collections.Generic return left; } - private static void Heapsort(T[] keys, int lo, int hi, IComparer comparer) + private static void Heapsort(T[] keys, int lo, int hi, Comparison comparer) { Contract.Requires(keys != null); Contract.Requires(comparer != null); @@ -372,7 +410,7 @@ namespace System.Collections.Generic } } - private static void DownHeap(T[] keys, int i, int n, int lo, IComparer comparer) + private static void DownHeap(T[] keys, int i, int n, int lo, Comparison comparer) { Contract.Requires(keys != null); Contract.Requires(comparer != null); @@ -384,11 +422,11 @@ namespace System.Collections.Generic while (i <= n / 2) { child = 2 * i; - if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0) + if (child < n && comparer(keys[lo + child - 1], keys[lo + child]) < 0) { child++; } - if (!(comparer.Compare(d, keys[lo + child - 1]) < 0)) + if (!(comparer(d, keys[lo + child - 1]) < 0)) break; keys[lo + i - 1] = keys[lo + child - 1]; i = child; @@ -396,7 +434,7 @@ namespace System.Collections.Generic keys[lo + i - 1] = d; } - private static void InsertionSort(T[] keys, int lo, int hi, IComparer comparer) + private static void InsertionSort(T[] keys, int lo, int hi, Comparison comparer) { Contract.Requires(keys != null); Contract.Requires(lo >= 0); @@ -409,7 +447,7 @@ namespace System.Collections.Generic { j = i; t = keys[i + 1]; - while (j >= lo && comparer.Compare(t, keys[j]) < 0) + while (j >= lo && comparer(t, keys[j]) < 0) { keys[j + 1] = keys[j]; j--; @@ -462,15 +500,15 @@ namespace System.Collections.Generic // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort. - ArraySortHelper.IntrospectiveSort(keys, index, length, comparer); + ArraySortHelper.IntrospectiveSort(keys, index, length, comparer.Compare); #else if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) { - ArraySortHelper.IntrospectiveSort(keys, index, length, comparer); + ArraySortHelper.IntrospectiveSort(keys, index, length, comparer.Compare); } else { - ArraySortHelper.DepthLimitedQuickSort(keys, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold); + ArraySortHelper.DepthLimitedQuickSort(keys, index, length + index - 1, comparer.Compare, IntrospectiveSortUtilities.QuickSortDepthThreshold); } #endif } @@ -574,6 +612,7 @@ namespace System.Collections.Generic } } +#if !FEATURE_CORECLR private static void DepthLimitedQuickSort(T[] keys, int left, int right, int depthLimit) { Contract.Requires(keys != null); @@ -645,6 +684,7 @@ namespace System.Collections.Generic } } while (left < right); } +#endif internal static void IntrospectiveSort(T[] keys, int left, int length) { @@ -815,7 +855,7 @@ namespace System.Collections.Generic } } - #endregion +#endregion #region ArraySortHelper for paired key and value arrays @@ -938,6 +978,7 @@ namespace System.Collections.Generic } } +#if !FEATURE_CORECLR internal static void DepthLimitedQuickSort(TKey[] keys, TValue[] values, int left, int right, IComparer comparer, int depthLimit) { do @@ -999,6 +1040,7 @@ namespace System.Collections.Generic } } while (left < right); } +#endif internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length, IComparer comparer) { @@ -1283,6 +1325,7 @@ namespace System.Collections.Generic } } +#if !FEATURE_CORECLR private static void DepthLimitedQuickSort(TKey[] keys, TValue[] values, int left, int right, int depthLimit) { // The code in this function looks very similar to QuickSort in ArraySortHelper class. @@ -1356,6 +1399,7 @@ namespace System.Collections.Generic } } while (left < right); } +#endif internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length) { @@ -1545,5 +1589,3 @@ namespace System.Collections.Generic #endregion } - - diff --git a/src/coreclr/src/mscorlib/src/System/Collections/Generic/List.cs b/src/coreclr/src/mscorlib/src/System/Collections/Generic/List.cs index 6cdb5f3..9e77906 100644 --- a/src/coreclr/src/mscorlib/src/System/Collections/Generic/List.cs +++ b/src/coreclr/src/mscorlib/src/System/Collections/Generic/List.cs @@ -977,8 +977,7 @@ namespace System.Collections.Generic { Contract.EndContractBlock(); if( _size > 0) { - IComparer comparer = Comparer.Create(comparison); - Array.Sort(_items, 0, _size, comparer); + ArraySortHelper.Sort(_items, 0, _size, comparison); } } diff --git a/src/coreclr/src/mscorlib/src/System/Diagnostics/Eventing/EventSource.cs b/src/coreclr/src/mscorlib/src/System/Diagnostics/Eventing/EventSource.cs index ce61234..b089381 100644 --- a/src/coreclr/src/mscorlib/src/System/Diagnostics/Eventing/EventSource.cs +++ b/src/coreclr/src/mscorlib/src/System/Diagnostics/Eventing/EventSource.cs @@ -6563,7 +6563,7 @@ namespace System.Diagnostics.Tracing // very early in the app domain creation, when _FusionStore is not set up yet, resulting in a failure to run the static constructory // for BinaryCompatibility. This failure is then cached and a TypeInitializationException is thrown every time some code attampts to // access BinaryCompatibility. - ArraySortHelper.IntrospectiveSort(sortedStrings, 0, sortedStrings.Length, Comparer.Default); + ArraySortHelper.IntrospectiveSort(sortedStrings, 0, sortedStrings.Length, string.Compare); #endif foreach (var ci in cultures) { -- 2.7.4