Separate Comparer and EqualityComparer creation logic into a non-generic class (#9640)

4 files changed, 221 insertions, 142 deletions

diff --git a/src/mscorlib/System.Private.CoreLib.csproj b/src/mscorlib/System.Private.CoreLib.csproj
index af5bb8f62d..816295636b 100644
--- a/src/mscorlib/System.Private.CoreLib.csproj
+++ b/src/mscorlib/System.Private.CoreLib.csproj
@@ -1085,6 +1085,7 @@
   <ItemGroup>
     <MscorlibSources Include="$(BclSourcesRoot)\System\Nullable.cs" />
     <MscorlibSources Include="$(BclSourcesRoot)\System\Collections\Generic\Comparer.cs" />
+    <MscorlibSources Include="$(BclSourcesRoot)\System\Collections\Generic\ComparerHelpers.cs" />
     <MscorlibSources Include="$(BclSourcesRoot)\System\Collections\Generic\Dictionary.cs" />
     <MscorlibSources Include="$(BclSourcesRoot)\System\Collections\Generic\EqualityComparer.cs" />
     <MscorlibSources Include="$(BclSourcesRoot)\System\Collections\Generic\DebugView.cs" />
diff --git a/src/mscorlib/src/System/Collections/Generic/Comparer.cs b/src/mscorlib/src/System/Collections/Generic/Comparer.cs
index 056843a606..714b386e3e 100644
--- a/src/mscorlib/src/System/Collections/Generic/Comparer.cs
+++ b/src/mscorlib/src/System/Collections/Generic/Comparer.cs
@@ -20,14 +20,9 @@ namespace System.Collections.Generic
     [TypeDependencyAttribute("System.Collections.Generic.ObjectComparer`1")] 
     public abstract class Comparer<T> : IComparer, IComparer<T>
     {
-        static readonly Comparer<T> defaultComparer = CreateComparer();
-
-        public static Comparer<T> Default {
-            get {
-                Contract.Ensures(Contract.Result<Comparer<T>>() != null);
-                return defaultComparer;
-            }
-        }
+        // To minimize generic instantiation overhead of creating the comparer per type, we keep the generic portion of the code as small
+        // as possible and define most of the creation logic in a non-generic class.
+        public static Comparer<T> Default { get; } = (Comparer<T>)ComparerHelpers.CreateDefaultComparer(typeof(T));
 
         public static Comparer<T> Create(Comparison<T> comparison)
         {
@@ -39,66 +34,6 @@ namespace System.Collections.Generic
             return new ComparisonComparer<T>(comparison);
         }
 
-        //
-        // Note that logic in this method is replicated in vm\compile.cpp to ensure that NGen
-        // saves the right instantiations
-        //
-        private static Comparer<T> CreateComparer()
-        {
-            object result = null;
-            RuntimeType t = (RuntimeType)typeof(T);
-
-            // If T implements IComparable<T> return a GenericComparer<T>
-            if (typeof(IComparable<T>).IsAssignableFrom(t))
-            {
-                result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericComparer<int>), t);
-            }
-            else if (default(T) == null)
-            {
-                // If T is a Nullable<U> where U implements IComparable<U> return a NullableComparer<U>
-                if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) {
-                    RuntimeType u = (RuntimeType)t.GetGenericArguments()[0];
-                    if (typeof(IComparable<>).MakeGenericType(u).IsAssignableFrom(u)) {
-                        result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableComparer<int>), u);
-                    }
-                }
-            }
-            else if (t.IsEnum)
-            {
-                // Explicitly call Enum.GetUnderlyingType here. Although GetTypeCode
-                // ends up doing this anyway, we end up avoiding an unnecessary P/Invoke
-                // and virtual method call.
-                TypeCode underlyingTypeCode = Type.GetTypeCode(Enum.GetUnderlyingType(t));
-                
-                // Depending on the enum type, we need to special case the comparers so that we avoid boxing
-                // Specialize differently for signed/unsigned types so we avoid problems with large numbers
-                switch (underlyingTypeCode)
-                {
-                    case TypeCode.SByte:
-                    case TypeCode.Int16:
-                    case TypeCode.Int32:
-                        result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(Int32EnumComparer<int>), t);
-                        break;
-                    case TypeCode.Byte:
-                    case TypeCode.UInt16:
-                    case TypeCode.UInt32:
-                        result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(UInt32EnumComparer<uint>), t);
-                        break;
-                    // 64-bit enums: use UnsafeEnumCastLong
-                    case TypeCode.Int64:
-                        result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(Int64EnumComparer<long>), t);
-                        break;
-                    case TypeCode.UInt64:
-                        result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(UInt64EnumComparer<ulong>), t);
-                        break;
-                }
-            }
-            
-            return result != null ?
-                (Comparer<T>)result :
-                new ObjectComparer<T>(); // Fallback to ObjectComparer, which uses boxing
-        }
-
         public abstract int Compare(T x, T y);
 
         int IComparer.Compare(object x, object y) {
@@ -196,7 +131,7 @@ namespace System.Collections.Generic
     {
         public Int32EnumComparer()
         {
-            Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!");
+            Debug.Assert(typeof(T).IsEnum);
         }
         
         // Used by the serialization engine.
@@ -231,7 +166,7 @@ namespace System.Collections.Generic
     {
         public UInt32EnumComparer()
         {
-            Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!");
+            Debug.Assert(typeof(T).IsEnum);
         }
         
         // Used by the serialization engine.
@@ -262,7 +197,7 @@ namespace System.Collections.Generic
     {
         public Int64EnumComparer()
         {
-            Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!");
+            Debug.Assert(typeof(T).IsEnum);
         }
         
         public override int Compare(T x, T y)
@@ -290,7 +225,7 @@ namespace System.Collections.Generic
     {
         public UInt64EnumComparer()
         {
-            Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!");
+            Debug.Assert(typeof(T).IsEnum);
         }
         
         // Used by the serialization engine.
diff --git a/src/mscorlib/src/System/Collections/Generic/ComparerHelpers.cs b/src/mscorlib/src/System/Collections/Generic/ComparerHelpers.cs
new file mode 100644
index 0000000000..3e428413d4
--- /dev/null
+++ b/src/mscorlib/src/System/Collections/Generic/ComparerHelpers.cs
@@ -0,0 +1,210 @@
+// Licensed to the .NET Foundation under one or more agreements.
+// The .NET Foundation licenses this file to you under the MIT license.
+// See the LICENSE file in the project root for more information.
+
+using System.Diagnostics;
+using static System.RuntimeTypeHandle;
+
+namespace System.Collections.Generic
+{
+    /// <summary>
+    /// Helper class for creating the default <see cref="Comparer{T}"/> and <see cref="EqualityComparer{T}"/>.
+    /// </summary>
+    /// <remarks>
+    /// This class is intentionally type-unsafe and non-generic to minimize the generic instantiation overhead of creating
+    /// the default comparer/equality comparer for a new type parameter. Efficiency of the methods in here does not matter too
+    /// much since they will only be run once per type parameter, but generic code involved in creating the comparers needs to be
+    /// kept to a minimum.
+    /// </remarks>
+    internal static class ComparerHelpers
+    {
+        /// <summary>
+        /// Creates the default <see cref="Comparer{T}"/>.
+        /// </summary>
+        /// <param name="type">The type to create the default comparer for.</param>
+        /// <remarks>
+        /// The logic in this method is replicated in vm/compile.cpp to ensure that NGen saves the right instantiations.
+        /// </remarks>
+        internal static object CreateDefaultComparer(Type type)
+        {
+            Debug.Assert(type != null && type is RuntimeType);
+
+            object result = null;
+            var runtimeType = (RuntimeType)type;
+
+            // If T implements IComparable<T> return a GenericComparer<T>
+            if (typeof(IComparable<>).MakeGenericType(type).IsAssignableFrom(type))
+            {
+                result = CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericComparer<int>), runtimeType);
+            }
+            // Nullable does not implement IComparable<T?> directly because that would add an extra interface call per comparison.
+            // Instead, it relies on Comparer<T?>.Default to specialize for nullables and do the lifted comparisons if T implements IComparable.
+            else if (type.IsGenericType)
+            {
+                if (type.GetGenericTypeDefinition() == typeof(Nullable<>))
+                {
+                    result = TryCreateNullableComparer(runtimeType);
+                }
+            }
+            // The comparer for enums is specialized to avoid boxing.
+            else if (type.IsEnum)
+            {
+                result = TryCreateEnumComparer(runtimeType);
+            }
+            
+            return result ?? CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ObjectComparer<object>), runtimeType);
+        }
+
+        /// <summary>
+        /// Creates the default <see cref="Comparer{T}"/> for a nullable type.
+        /// </summary>
+        /// <param name="nullableType">The nullable type to create the default comparer for.</param>
+        private static object TryCreateNullableComparer(RuntimeType nullableType)
+        {
+            Debug.Assert(nullableType != null);
+            Debug.Assert(nullableType.IsGenericType && nullableType.GetGenericTypeDefinition() == typeof(Nullable<>));
+            
+            var embeddedType = (RuntimeType)nullableType.GetGenericArguments()[0];
+
+            if (typeof(IComparable<>).MakeGenericType(embeddedType).IsAssignableFrom(embeddedType))
+            {
+                return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableComparer<int>), embeddedType);
+            }
+
+            return null;
+        }
+
+        /// <summary>
+        /// Creates the default <see cref="Comparer{T}"/> for an enum type.
+        /// </summary>
+        /// <param name="enumType">The enum type to create the default comparer for.</param>
+        private static object TryCreateEnumComparer(RuntimeType enumType)
+        {
+            Debug.Assert(enumType != null);
+            Debug.Assert(enumType.IsEnum);
+
+            // Explicitly call Enum.GetUnderlyingType here. Although GetTypeCode
+            // ends up doing this anyway, we end up avoiding an unnecessary P/Invoke
+            // and virtual method call.
+            TypeCode underlyingTypeCode = Type.GetTypeCode(Enum.GetUnderlyingType(enumType));
+            
+            // Depending on the enum type, we need to special case the comparers so that we avoid boxing.
+            // Specialize differently for signed/unsigned types so we avoid problems with large numbers.
+            switch (underlyingTypeCode)
+            {
+                case TypeCode.SByte:
+                case TypeCode.Int16:
+                case TypeCode.Int32:
+                    return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(Int32EnumComparer<int>), enumType);
+                case TypeCode.Byte:
+                case TypeCode.UInt16:
+                case TypeCode.UInt32:
+                    return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(UInt32EnumComparer<uint>), enumType);
+                // 64-bit enums: Use `UnsafeEnumCastLong`
+                case TypeCode.Int64:
+                    return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(Int64EnumComparer<long>), enumType);
+                case TypeCode.UInt64:
+                    return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(UInt64EnumComparer<ulong>), enumType);
+            }
+            
+            return null;
+        }
+
+        /// <summary>
+        /// Creates the default <see cref="EqualityComparer{T}"/>.
+        /// </summary>
+        /// <param name="type">The type to create the default equality comparer for.</param>
+        /// <remarks>
+        /// The logic in this method is replicated in vm/compile.cpp to ensure that NGen saves the right instantiations.
+        /// </remarks>
+        internal static object CreateDefaultEqualityComparer(Type type)
+        {
+            Debug.Assert(type != null && type is RuntimeType);
+
+            object result = null;
+            var runtimeType = (RuntimeType)type;
+
+            // Specialize for byte so Array.IndexOf is faster.
+            if (type == typeof(byte))
+            {
+                result = new ByteEqualityComparer();
+            }
+            // If T implements IEquatable<T> return a GenericEqualityComparer<T>
+            else if (typeof(IEquatable<>).MakeGenericType(type).IsAssignableFrom(type))
+            {
+                result = CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericEqualityComparer<int>), runtimeType);
+            }
+            // Nullable does not implement IEquatable<T?> directly because that would add an extra interface call per comparison.
+            // Instead, it relies on EqualityComparer<T?>.Default to specialize for nullables and do the lifted comparisons if T implements IEquatable.
+            else if (type.IsGenericType)
+            {
+                if (type.GetGenericTypeDefinition() == typeof(Nullable<>))
+                {
+                    result = TryCreateNullableEqualityComparer(runtimeType);
+                }
+            }
+            // The equality comparer for enums is specialized to avoid boxing.
+            else if (type.IsEnum)
+            {
+                result = TryCreateEnumEqualityComparer(runtimeType);
+            }
+            
+            return result ?? CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ObjectEqualityComparer<object>), runtimeType);
+        }
+
+        /// <summary>
+        /// Creates the default <see cref="EqualityComparer{T}"/> for a nullable type.
+        /// </summary>
+        /// <param name="nullableType">The nullable type to create the default equality comparer for.</param>
+        private static object TryCreateNullableEqualityComparer(RuntimeType nullableType)
+        {
+            Debug.Assert(nullableType != null);
+            Debug.Assert(nullableType.IsGenericType && nullableType.GetGenericTypeDefinition() == typeof(Nullable<>));
+
+            var embeddedType = (RuntimeType)nullableType.GetGenericArguments()[0];
+
+            if (typeof(IEquatable<>).MakeGenericType(embeddedType).IsAssignableFrom(embeddedType))
+            {
+                return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableEqualityComparer<int>), embeddedType);
+            }
+            
+            return null;
+        }
+
+        /// <summary>
+        /// Creates the default <see cref="EqualityComparer{T}"/> for an enum type.
+        /// </summary>
+        /// <param name="enumType">The enum type to create the default equality comparer for.</param>
+        private static object TryCreateEnumEqualityComparer(RuntimeType enumType)
+        {
+            Debug.Assert(enumType != null);
+            Debug.Assert(enumType.IsEnum);
+
+            // See the METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST and METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST_LONG cases in getILIntrinsicImplementation
+            // for how we cast the enum types to integral values in the comparer without boxing.
+
+            TypeCode underlyingTypeCode = Type.GetTypeCode(Enum.GetUnderlyingType(enumType));
+
+            // Depending on the enum type, we need to special case the comparers so that we avoid boxing.
+            // Note: We have different comparers for short and sbyte, since for those types GetHashCode does not simply return the value.
+            // We need to preserve what they would return.
+            switch (underlyingTypeCode)
+            {
+                case TypeCode.Int16:
+                    return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ShortEnumEqualityComparer<short>), enumType);
+                case TypeCode.SByte:
+                    return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(SByteEnumEqualityComparer<sbyte>), enumType);
+                case TypeCode.Int32:
+                case TypeCode.UInt32:
+                case TypeCode.Byte:
+                case TypeCode.UInt16:
+                    return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(EnumEqualityComparer<int>), enumType);
+                case TypeCode.Int64:
+                case TypeCode.UInt64:
+                    return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(LongEnumEqualityComparer<long>), enumType);
+            }
+            
+            return null;
+        }
+    }
+}
diff --git a/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs b/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs
index 0f9259d2f3..7178ddc663 100644
--- a/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs
+++ b/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs
@@ -18,76 +18,9 @@ namespace System.Collections.Generic
     [TypeDependencyAttribute("System.Collections.Generic.ObjectEqualityComparer`1")]
     public abstract class EqualityComparer<T> : IEqualityComparer, IEqualityComparer<T>
     {
-        static readonly EqualityComparer<T> defaultComparer = CreateComparer();
-
-        public static EqualityComparer<T> Default {
-            get {
-                Contract.Ensures(Contract.Result<EqualityComparer<T>>() != null);
-                return defaultComparer;
-            }
-        }
-
-        //
-        // Note that logic in this method is replicated in vm\compile.cpp to ensure that NGen
-        // saves the right instantiations
-        //
-        private static EqualityComparer<T> CreateComparer()
-        {
-            Contract.Ensures(Contract.Result<EqualityComparer<T>>() != null);
-            
-            object result = null;
-            RuntimeType t = (RuntimeType)typeof(T);
-            
-            // Specialize type byte for performance reasons
-            if (t == typeof(byte)) {
-                result = new ByteEqualityComparer();
-            }
-            // If T implements IEquatable<T> return a GenericEqualityComparer<T>
-            else if (typeof(IEquatable<T>).IsAssignableFrom(t))
-            {
-                result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericEqualityComparer<int>), t);
-            }
-            else if (default(T) == null) // Reference type/Nullable
-            {
-                // If T is a Nullable<U> where U implements IEquatable<U> return a NullableEqualityComparer<U>
-                if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) {
-                    RuntimeType u = (RuntimeType)t.GetGenericArguments()[0];
-                    if (typeof(IEquatable<>).MakeGenericType(u).IsAssignableFrom(u)) {
-                        result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableEqualityComparer<int>), u);
-                    }
-                }
-            }
-            // See the METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST and METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST_LONG cases in getILIntrinsicImplementation
-            else if (t.IsEnum) {
-                TypeCode underlyingTypeCode = Type.GetTypeCode(Enum.GetUnderlyingType(t));
-
-                // Depending on the enum type, we need to special case the comparers so that we avoid boxing
-                // Note: We have different comparers for Short and SByte because for those types we need to make sure we call GetHashCode on the actual underlying type as the 
-                // implementation of GetHashCode is more complex than for the other types.
-                switch (underlyingTypeCode) {
-                    case TypeCode.Int16: // short
-                        result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ShortEnumEqualityComparer<short>), t);
-                        break;
-                    case TypeCode.SByte:
-                        result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(SByteEnumEqualityComparer<sbyte>), t);
-                        break;
-                    case TypeCode.Int32:
-                    case TypeCode.UInt32:
-                    case TypeCode.Byte:
-                    case TypeCode.UInt16: //ushort
-                        result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(EnumEqualityComparer<int>), t);
-                        break;
-                    case TypeCode.Int64:
-                    case TypeCode.UInt64:
-                        result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(LongEnumEqualityComparer<long>), t);
-                        break;
-                }
-            }
-            
-            return result != null ?
-                (EqualityComparer<T>)result :
-                new ObjectEqualityComparer<T>(); // Fallback to ObjectEqualityComparer, which uses boxing
-        }
+        // To minimize generic instantiation overhead of creating the comparer per type, we keep the generic portion of the code as small
+        // as possible and define most of the creation logic in a non-generic class.
+        public static EqualityComparer<T> Default { get; } = (EqualityComparer<T>)ComparerHelpers.CreateDefaultEqualityComparer(typeof(T));
 
         [Pure]
         public abstract bool Equals(T x, T y);