Vectorized SequenceCompareTo for Span<char> (dotnet/coreclr#17237)

- This change makes the compare for very short Span strings a bit slower and for longer Span strings many times faster.
- Switch several places where it was a clear benefit to use it.
`String.CompareOrdinal(string,string)` is notable exception that I have left intact for now. It is fine tuned for current string layout, and replacing with a call of vectorized SequenceCompareTo gives mixed results.

Signed-off-by: dotnet-bot <dotnet-bot@microsoft.com>

6 files changed, 226 insertions, 141 deletions

diff --git a/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems b/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems
index f4f8dd32a..4f7e0614e 100644
--- a/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems
+++ b/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems
@@ -492,6 +492,7 @@
     <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.cs" />
     <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.BinarySearch.cs" />
     <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.Byte.cs" />
+    <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.Char.cs" />
     <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.T.cs" />
     <Compile Include="$(MSBuildThisFileDirectory)System\String.cs" />
     <Compile Include="$(MSBuildThisFileDirectory)System\String.Manipulation.cs" />
diff --git a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs
index 4ccd739bc..079b8afbc 100644
--- a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs
+++ b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs
@@ -341,7 +341,7 @@ namespace System.Globalization
             if (_invariantMode)
             {
                 if ((options & CompareOptions.IgnoreCase) != 0)
-                    return CompareOrdinalIgnoreCase(string1, 0, string1.Length, string2, 0, string2.Length);
+                    return CompareOrdinalIgnoreCase(string1, string2);
 
                 return String.CompareOrdinal(string1, string2);
             }
@@ -501,35 +501,23 @@ namespace System.Globalization
                 return (1);
             }
 
+            ReadOnlySpan<char> span1 = string1.AsSpan(offset1, length1);
+            ReadOnlySpan<char> span2 = string2.AsSpan(offset2, length2);
+
             if (options == CompareOptions.Ordinal)
             {
-                return CompareOrdinal(string1, offset1, length1,
-                                      string2, offset2, length2);
+                return string.CompareOrdinal(span1, span2);
             }
 
             if (_invariantMode)
             {
                 if ((options & CompareOptions.IgnoreCase) != 0)
-                    return CompareOrdinalIgnoreCase(string1, offset1, length1, string2, offset2, length2);
+                    return CompareOrdinalIgnoreCase(span1, span2);
 
-                return CompareOrdinal(string1, offset1, length1, string2, offset2, length2);
+                return string.CompareOrdinal(span1, span2);
             }
 
-            return CompareString(
-                string1.AsSpan(offset1, length1),
-                string2.AsSpan(offset2, length2),
-                options);
-        }
-
-        private static int CompareOrdinal(string string1, int offset1, int length1, string string2, int offset2, int length2)
-        {
-            int result = String.CompareOrdinal(string1, offset1, string2, offset2,
-                                                       (length1 < length2 ? length1 : length2));
-            if ((length1 != length2) && result == 0)
-            {
-                return (length1 > length2 ? 1 : -1);
-            }
-            return (result);
+            return CompareString(span1, span2, options);
         }
 
         //
diff --git a/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs b/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs
index 0a06f3584..1a3b33acc 100644
--- a/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs
+++ b/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs
@@ -301,6 +301,13 @@ namespace System
                     ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(other)),
                     other.Length);
 
+            if (typeof(T) == typeof(char))
+                return SpanHelpers.SequenceCompareTo(
+                    ref Unsafe.As<T, char>(ref MemoryMarshal.GetReference(span)),
+                    span.Length,
+                    ref Unsafe.As<T, char>(ref MemoryMarshal.GetReference(other)),
+                    other.Length);
+
             return SpanHelpers.SequenceCompareTo(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(other), other.Length);
         }
 
@@ -659,6 +666,13 @@ namespace System
                     ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(other)),
                     other.Length);
 
+            if (typeof(T) == typeof(char))
+                return SpanHelpers.SequenceCompareTo(
+                    ref Unsafe.As<T, char>(ref MemoryMarshal.GetReference(span)),
+                    span.Length,
+                    ref Unsafe.As<T, char>(ref MemoryMarshal.GetReference(other)),
+                    other.Length);
+
             return SpanHelpers.SequenceCompareTo(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(other), other.Length);
         }
 
diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs
new file mode 100644
index 000000000..2033d8b90
--- /dev/null
+++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs
@@ -0,0 +1,201 @@
+// 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 System.Runtime.CompilerServices;
+
+#if !netstandard
+using Internal.Runtime.CompilerServices;
+#endif
+
+#if !netstandard11
+using System.Numerics;
+#endif
+
+namespace System
+{
+    internal static partial class SpanHelpers
+    {
+        public static unsafe int SequenceCompareTo(ref char first, int firstLength, ref char second, int secondLength)
+        {
+            Debug.Assert(firstLength >= 0);
+            Debug.Assert(secondLength >= 0);
+
+            int lengthDelta = firstLength - secondLength;
+
+            if (Unsafe.AreSame(ref first, ref second))
+                goto Equal;
+
+            IntPtr minLength = (IntPtr)((firstLength < secondLength) ? firstLength : secondLength);
+            IntPtr i = (IntPtr)0; // Use IntPtr for arithmetic to avoid unnecessary 64->32->64 truncations
+
+            if ((byte*)minLength >= (byte*)(sizeof(UIntPtr) / sizeof(char)))
+            {
+#if !netstandard11
+                if (Vector.IsHardwareAccelerated && (byte*)minLength >= (byte*)Vector<ushort>.Count)
+                {
+                    IntPtr nLength = minLength - Vector<ushort>.Count;
+                    do
+                    {
+                        if (Unsafe.ReadUnaligned<Vector<ushort>>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref first, i))) !=
+                            Unsafe.ReadUnaligned<Vector<ushort>>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref second, i))))
+                        {
+                            break;
+                        }
+                        i += Vector<ushort>.Count;
+                    }
+                    while ((byte*)nLength >= (byte*)i);
+                }
+#endif
+
+                while ((byte*)minLength >= (byte*)(i + sizeof(UIntPtr) / sizeof(char)))
+                {
+                    if (Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref first, i))) !=
+                        Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref second, i))))
+                    {
+                        break;
+                    }
+                    i += sizeof(UIntPtr) / sizeof(char);
+                }
+            }
+
+            if (sizeof(UIntPtr) > sizeof(int) && (byte*)minLength >= (byte*)(i + sizeof(int) / sizeof(char)))
+            {
+                if (Unsafe.ReadUnaligned<int>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref first, i))) ==
+                    Unsafe.ReadUnaligned<int>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref second, i))))
+                {
+                    i += sizeof(int) / sizeof(char);
+                }
+            }
+
+            while ((byte*)i < (byte*)minLength)
+            {
+                int result = Unsafe.Add(ref first, i).CompareTo(Unsafe.Add(ref second, i));
+                if (result != 0) return result;
+                i += 1;
+            }
+
+        Equal:
+            return lengthDelta;
+        }
+
+        public static unsafe int IndexOf(ref char searchSpace, char value, int length)
+        {
+            Debug.Assert(length >= 0);
+
+            uint uValue = value; // Use uint for comparisons to avoid unnecessary 8->32 extensions
+            IntPtr index = (IntPtr)0; // Use IntPtr for arithmetic to avoid unnecessary 64->32->64 truncations
+            IntPtr nLength = (IntPtr)length;
+#if !netstandard11
+            if (Vector.IsHardwareAccelerated && length >= Vector<ushort>.Count * 2)
+            {
+                const int elementsPerByte = sizeof(ushort) / sizeof(byte);
+                int unaligned = ((int)Unsafe.AsPointer(ref searchSpace) & (Vector<byte>.Count - 1)) / elementsPerByte;
+                nLength = (IntPtr)((Vector<ushort>.Count - unaligned) & (Vector<ushort>.Count - 1));
+            }
+        SequentialScan:
+#endif
+            while ((byte*)nLength >= (byte*)4)
+            {
+                nLength -= 4;
+
+                if (uValue == Unsafe.Add(ref searchSpace, index))
+                    goto Found;
+                if (uValue == Unsafe.Add(ref searchSpace, index + 1))
+                    goto Found1;
+                if (uValue == Unsafe.Add(ref searchSpace, index + 2))
+                    goto Found2;
+                if (uValue == Unsafe.Add(ref searchSpace, index + 3))
+                    goto Found3;
+
+                index += 4;
+            }
+
+            while ((byte*)nLength > (byte*)0)
+            {
+                nLength -= 1;
+
+                if (uValue == Unsafe.Add(ref searchSpace, index))
+                    goto Found;
+
+                index += 1;
+            }
+#if !netstandard11
+            if (Vector.IsHardwareAccelerated && ((int)(byte*)index < length))
+            {
+                nLength = (IntPtr)((length - (int)(byte*)index) & ~(Vector<ushort>.Count - 1));
+
+                // Get comparison Vector
+                Vector<ushort> vComparison = new Vector<ushort>(value);
+
+                while ((byte*)nLength > (byte*)index)
+                {
+                    var vMatches = Vector.Equals(vComparison, Unsafe.ReadUnaligned<Vector<ushort>>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref searchSpace, index))));
+                    if (Vector<ushort>.Zero.Equals(vMatches))
+                    {
+                        index += Vector<ushort>.Count;
+                        continue;
+                    }
+                    // Find offset of first match
+                    return (int)(byte*)index + LocateFirstFoundChar(vMatches);
+                }
+
+                if ((int)(byte*)index < length)
+                {
+                    nLength = (IntPtr)(length - (int)(byte*)index);
+                    goto SequentialScan;
+                }
+            }
+#endif
+            return -1;
+        Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549
+            return (int)(byte*)index;
+        Found1:
+            return (int)(byte*)(index + 1);
+        Found2:
+            return (int)(byte*)(index + 2);
+        Found3:
+            return (int)(byte*)(index + 3);
+        }
+
+#if !netstandard11
+        // Vector sub-search adapted from https://github.com/aspnet/KestrelHttpServer/pull/1138
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        private static int LocateFirstFoundChar(Vector<ushort> match)
+        {
+            var vector64 = Vector.AsVectorUInt64(match);
+            ulong candidate = 0;
+            int i = 0;
+            // Pattern unrolled by jit https://github.com/dotnet/coreclr/pull/8001
+            for (; i < Vector<ulong>.Count; i++)
+            {
+                candidate = vector64[i];
+                if (candidate != 0)
+                {
+                    break;
+                }
+            }
+
+            // Single LEA instruction with jitted const (using function result)
+            return i * 4 + LocateFirstFoundChar(candidate);
+        }
+
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        private static int LocateFirstFoundChar(ulong match)
+        {
+            unchecked
+            {
+                // Flag least significant power of two bit
+                var powerOfTwoFlag = match ^ (match - 1);
+                // Shift all powers of two into the high byte and extract
+                return (int)((powerOfTwoFlag * XorPowerOfTwoToHighChar) >> 49);
+            }
+        }
+
+        private const ulong XorPowerOfTwoToHighChar = (0x03ul |
+                                                       0x02ul << 16 |
+                                                       0x01ul << 32) + 1;
+#endif
+    }
+}
diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs
index 818216bff..4567deddb 100644
--- a/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs
+++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs
@@ -127,85 +127,6 @@ namespace System
             return (int)(byte*)(index + 7);
         }
 
-        public static unsafe int IndexOf(ref char searchSpace, char value, int length)
-        {
-            Debug.Assert(length >= 0);
-
-            uint uValue = value; // Use uint for comparisons to avoid unnecessary 8->32 extensions
-            IntPtr index = (IntPtr)0; // Use IntPtr for arithmetic to avoid unnecessary 64->32->64 truncations
-            IntPtr nLength = (IntPtr)length;
-#if !netstandard11
-            if (Vector.IsHardwareAccelerated && length >= Vector<ushort>.Count * 2)
-            {
-                const int elementsPerByte = sizeof(ushort) / sizeof(byte);
-                int unaligned = ((int)Unsafe.AsPointer(ref searchSpace) & (Vector<byte>.Count - 1)) / elementsPerByte;
-                nLength = (IntPtr)((Vector<ushort>.Count - unaligned) & (Vector<ushort>.Count - 1));
-            }
-        SequentialScan:
-#endif
-            while ((byte*)nLength >= (byte*)4)
-            {
-                nLength -= 4;
-
-                if (uValue == Unsafe.Add(ref searchSpace, index))
-                    goto Found;
-                if (uValue == Unsafe.Add(ref searchSpace, index + 1))
-                    goto Found1;
-                if (uValue == Unsafe.Add(ref searchSpace, index + 2))
-                    goto Found2;
-                if (uValue == Unsafe.Add(ref searchSpace, index + 3))
-                    goto Found3;
-
-                index += 4;
-            }
-
-            while ((byte*)nLength > (byte*)0)
-            {
-                nLength -= 1;
-
-                if (uValue == Unsafe.Add(ref searchSpace, index))
-                    goto Found;
-
-                index += 1;
-            }
-#if !netstandard11
-            if (Vector.IsHardwareAccelerated && ((int)(byte*)index < length))
-            {
-                nLength = (IntPtr)((length - (int)(byte*)index) & ~(Vector<ushort>.Count - 1));
-
-                // Get comparison Vector
-                Vector<ushort> vComparison = new Vector<ushort>(value);
-
-                while ((byte*)nLength > (byte*)index)
-                {
-                    var vMatches = Vector.Equals(vComparison, Unsafe.ReadUnaligned<Vector<ushort>>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref searchSpace, index))));
-                    if (Vector<ushort>.Zero.Equals(vMatches))
-                    {
-                        index += Vector<ushort>.Count;
-                        continue;
-                    }
-                    // Find offset of first match
-                    return (int)(byte*)index + LocateFirstFoundChar(vMatches);
-                }
-
-                if ((int)(byte*)index < length)
-                {
-                    nLength = (IntPtr)(length - (int)(byte*)index);
-                    goto SequentialScan;
-                }
-            }
-#endif
-            return -1;
-        Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549
-            return (int)(byte*)index;
-        Found1:
-            return (int)(byte*)(index + 1);
-        Found2:
-            return (int)(byte*)(index + 2);
-        Found3:
-            return (int)(byte*)(index + 3);
-        }
-
         public static int IndexOfAny<T>(ref T searchSpace, T value0, T value1, int length)
             where T : IEquatable<T>
         {
@@ -761,45 +682,5 @@ namespace System
             }
             return firstLength.CompareTo(secondLength);
         }
-
-#if !netstandard11
-        // Vector sub-search adapted from https://github.com/aspnet/KestrelHttpServer/pull/1138
-        [MethodImpl(MethodImplOptions.AggressiveInlining)]
-        private static int LocateFirstFoundChar(Vector<ushort> match)
-        {
-            var vector64 = Vector.AsVectorUInt64(match);
-            ulong candidate = 0;
-            int i = 0;
-            // Pattern unrolled by jit https://github.com/dotnet/coreclr/pull/8001
-            for (; i < Vector<ulong>.Count; i++)
-            {
-                candidate = vector64[i];
-                if (candidate != 0)
-                {
-                    break;
-                }
-            }
-
-            // Single LEA instruction with jitted const (using function result)
-            return i * 4 + LocateFirstFoundChar(candidate);
-        }
-
-        [MethodImpl(MethodImplOptions.AggressiveInlining)]
-        private static int LocateFirstFoundChar(ulong match)
-        {
-            unchecked
-            {
-                // Flag least significant power of two bit
-                var powerOfTwoFlag = match ^ (match - 1);
-                // Shift all powers of two into the high byte and extract
-                return (int)((powerOfTwoFlag * XorPowerOfTwoToHighChar) >> 49);
-            }
-        }
-
-        private const ulong XorPowerOfTwoToHighChar = (0x03ul |
-                                                       0x02ul << 16 |
-                                                       0x01ul << 32) + 1;
-#endif
-
     }
 }
diff --git a/src/System.Private.CoreLib/shared/System/String.Manipulation.cs b/src/System.Private.CoreLib/shared/System/String.Manipulation.cs
index d2aac0d43..69609aacf 100644
--- a/src/System.Private.CoreLib/shared/System/String.Manipulation.cs
+++ b/src/System.Private.CoreLib/shared/System/String.Manipulation.cs
@@ -1541,7 +1541,7 @@ namespace System
                 if (this[i] == separator[0] && currentSepLength <= Length - i)
                 {
                     if (currentSepLength == 1
-                        || CompareOrdinal(this, i, separator, 0, currentSepLength) == 0)
+                        || this.AsSpan(i, currentSepLength).SequenceEqual(separator))
                     {
                         sepListBuilder.Append(i);
                         i += currentSepLength - 1;
@@ -1575,7 +1575,7 @@ namespace System
                     if (this[i] == separator[0] && currentSepLength <= Length - i)
                     {
                         if (currentSepLength == 1
-                            || CompareOrdinal(this, i, separator, 0, currentSepLength) == 0)
+                            || this.AsSpan(i, currentSepLength).SequenceEqual(separator))
                         {
                             sepListBuilder.Append(i);
                             lengthListBuilder.Append(currentSepLength);