From 30bf66a0ef5342ea229a52e2d5b377f3102948a4 Mon Sep 17 00:00:00 2001
From: Gregory Bell <65985703+grbell-ms@users.noreply.github.com>
Date: Mon, 20 Jun 2022 19:27:34 -0700
Subject: [PATCH] Remove allocation in ImmutableArray Builder Sort (#70850)

* Remove allocation in ImmutableArray Builder Sort

`ImmutableArray<T>.Builder.Sort(Comparison<T> comparison)` allocates a new instance of `Comparer<T>` using `comparison`. Then `ArraySort` allocates a new delegate from `comparer.Compare`. Both allocations can be eliminated by calling `Array.Sort<T>(T[] array, Comparison<T> comparison)` directly.

* Sort only valid range of array

* Use MemoryExtensions.Sort where available.

* Update src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.Builder.cs

Fix spelling mistake.

Co-authored-by: Eirik Tsarpalis <eirik.tsarpalis@gmail.com>

Co-authored-by: Eirik Tsarpalis <eirik.tsarpalis@gmail.com>
---
 .../src/System.Collections.Immutable.csproj                         | 3 ++-
 .../src/System/Collections/Immutable/ImmutableArray_1.Builder.cs    | 6 ++++++
 2 files changed, 8 insertions(+), 1 deletion(-)

diff --git a/src/libraries/System.Collections.Immutable/src/System.Collections.Immutable.csproj b/src/libraries/System.Collections.Immutable/src/System.Collections.Immutable.csproj
index 76202d0..7fb8320 100644
--- a/src/libraries/System.Collections.Immutable/src/System.Collections.Immutable.csproj
+++ b/src/libraries/System.Collections.Immutable/src/System.Collections.Immutable.csproj
@@ -1,4 +1,4 @@
-<Project Sdk="Microsoft.NET.Sdk">
+<Project Sdk="Microsoft.NET.Sdk">
   <PropertyGroup>
     <TargetFrameworks>$(NetCoreAppCurrent);$(NetCoreAppMinimum);netstandard2.0;$(NetFrameworkMinimum)</TargetFrameworks>
     <IsPackable>true</IsPackable>
@@ -109,6 +109,7 @@ System.Collections.Immutable.ImmutableStack&lt;T&gt;</PackageDescription>
   <ItemGroup Condition="'$(TargetFramework)' == '$(NetCoreAppCurrent)'">
     <Reference Include="System.Collections" />
     <Reference Include="System.Linq" />
+    <Reference Include="System.Memory" />
     <Reference Include="System.Runtime" />
     <Reference Include="System.Runtime.InteropServices" />
     <Reference Include="System.Threading" />
diff --git a/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.Builder.cs b/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.Builder.cs
index 4ab4c16..0fd2dec 100644
--- a/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.Builder.cs
+++ b/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.Builder.cs
@@ -933,11 +933,17 @@ namespace System.Collections.Immutable
 
                 if (Count > 1)
                 {
+#if NET6_0_OR_GREATER
+                    // MemoryExtensions.Sort is not available in .NET Framework / Standard 2.0.
+                    // But the overload with a Comparison argument doesn't allocate.
+                    _elements.AsSpan(0, _count).Sort(comparison);
+#else
                     // Array.Sort does not have an overload that takes both bounds and a Comparison.
                     // We could special case _count == _elements.Length in order to try to avoid
                     // the IComparer allocation, but the Array.Sort overload that takes a Comparison
                     // allocates such an IComparer internally, anyway.
                     Array.Sort(_elements, 0, _count, Comparer<T>.Create(comparison));
+#endif
                 }
             }
 
-- 
2.7.4