Vectorize String.IndexOf(char) and String.LastIndexOf(char) (#16392)

* Vectorize String.IndexOf(char) using the same algorithm as SpanHelpers
IndexOf(byte).

* Respond to feedback.

* Vectorize String.LastIndexOf

Clean up IndexOf vectorization.

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

1 files changed, 158 insertions, 6 deletions

diff --git a/src/System.Private.CoreLib/shared/System/String.Searching.cs b/src/System.Private.CoreLib/shared/System/String.Searching.cs
index 8a67feff3..c86d13524 100644
--- a/src/System.Private.CoreLib/shared/System/String.Searching.cs
+++ b/src/System.Private.CoreLib/shared/System/String.Searching.cs
@@ -3,7 +3,10 @@
 // See the LICENSE file in the project root for more information.
 
 using System.Globalization;
+using System.Numerics;
+using System.Runtime.CompilerServices;
 using System.Runtime.InteropServices;
+using Internal.Runtime.CompilerServices;
 
 namespace System
 {
@@ -63,24 +66,35 @@ namespace System
 
                 case StringComparison.OrdinalIgnoreCase:
                     return CompareInfo.Invariant.IndexOf(this, value, CompareOptions.OrdinalIgnoreCase);
-                    
+
                 default:
                     throw new ArgumentException(SR.NotSupported_StringComparison, nameof(comparisonType));
             }
         }
-        
+
         public unsafe int IndexOf(char value, int startIndex, int count)
         {
-            if (startIndex < 0 || startIndex > Length)
+            if ((uint)startIndex > (uint)Length)
                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
 
-            if (count < 0 || count > Length - startIndex)
+            if ((uint)count > (uint)(Length - startIndex))
                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
 
             fixed (char* pChars = &_firstChar)
             {
                 char* pCh = pChars + startIndex;
+                char* pEndCh = pCh + count;
 
+                if (Vector.IsHardwareAccelerated && count >= Vector<ushort>.Count * 2)
+                {
+                    unchecked
+                    {
+                        const int elementsPerByte = sizeof(ushort) / sizeof(byte);
+                        int unaligned = ((int)pCh & (Vector<byte>.Count - 1)) / elementsPerByte;
+                        count = ((Vector<ushort>.Count - unaligned) & (Vector<ushort>.Count - 1));
+                    }
+                }
+            SequentialScan:
                 while (count >= 4)
                 {
                     if (*pCh == value) goto ReturnIndex;
@@ -101,6 +115,34 @@ namespace System
                     pCh++;
                 }
 
+                if (pCh < pEndCh)
+                {
+                    count = (int)((pEndCh - pCh) & ~(Vector<ushort>.Count - 1));
+                    // Get comparison Vector
+                    Vector<ushort> vComparison = new Vector<ushort>(value);
+                    while (count > 0)
+                    {
+                        var vMatches = Vector.Equals(vComparison, Unsafe.ReadUnaligned<Vector<ushort>>(pCh));
+                        if (Vector<ushort>.Zero.Equals(vMatches))
+                        {
+                            pCh += Vector<ushort>.Count;
+                            count -= Vector<ushort>.Count;
+                            continue;
+                        }
+                        // Find offset of first match
+                        return (int)(pCh - pChars) + LocateFirstFoundChar(vMatches);
+                    }
+
+                    if (pCh < pEndCh)
+                    {
+                        unchecked
+                        {
+                            count = (int)(pEndCh - pCh);
+                        }
+                        goto SequentialScan;
+                    }
+                }
+
                 return -1;
 
             ReturnIndex3: pCh++;
@@ -111,6 +153,43 @@ namespace System
             }
         }
 
+        // 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;
+
         // Returns the index of the first occurrence of any specified character in the current instance.
         // The search starts at startIndex and runs to startIndex + count - 1.
         //
@@ -397,17 +476,27 @@ namespace System
             if (Length == 0)
                 return -1;
 
-            if (startIndex < 0 || startIndex >= Length)
+            if ((uint)startIndex >= (uint)Length)
                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
 
-            if (count < 0 || count - 1 > startIndex)
+            if ((uint)count > (uint)startIndex + 1)
                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
 
             fixed (char* pChars = &_firstChar)
             {
                 char* pCh = pChars + startIndex;
+                char* pEndCh = pCh - count;
 
                 //We search [startIndex..EndIndex]
+                if (Vector.IsHardwareAccelerated && count >= Vector<ushort>.Count * 2)
+                {
+                    unchecked
+                    {
+                        const int elementsPerByte = sizeof(ushort) / sizeof(byte);
+                        count = (((int)pCh & (Vector<byte>.Count - 1)) / elementsPerByte) + 1;
+                    }
+                }
+            SequentialScan:
                 while (count >= 4)
                 {
                     if (*pCh == value) goto ReturnIndex;
@@ -428,6 +517,35 @@ namespace System
                     pCh--;
                 }
 
+                if (pCh > pEndCh)
+                {
+                    count = (int)((pCh - pEndCh) & ~(Vector<ushort>.Count - 1));
+
+                    // Get comparison Vector
+                    Vector<ushort> vComparison = new Vector<ushort>(value);
+                    while (count > 0)
+                    {
+                        char* pStart = pCh - Vector<ushort>.Count + 1;
+                        var vMatches = Vector.Equals(vComparison, Unsafe.ReadUnaligned<Vector<ushort>>(pStart));
+                        if (Vector<ushort>.Zero.Equals(vMatches))
+                        {
+                            pCh -= Vector<ushort>.Count;
+                            count -= Vector<ushort>.Count;
+                            continue;
+                        }
+                        // Find offset of last match
+                        return (int)(pStart - pChars) + LocateLastFoundChar(vMatches);
+                    }
+
+                    if (pCh > pEndCh)
+                    {
+                        unchecked
+                        {
+                            count = (int)(pCh - pEndCh);
+                        }
+                        goto SequentialScan;
+                    }
+                }
                 return -1;
 
             ReturnIndex3: pCh--;
@@ -438,6 +556,40 @@ namespace System
             }
         }
 
+        // Vector sub-search adapted from https://github.com/aspnet/KestrelHttpServer/pull/1138
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        private static int LocateLastFoundChar(Vector<ushort> match)
+        {
+            var vector64 = Vector.AsVectorUInt64(match);
+            ulong candidate = 0;
+            int i = Vector<ulong>.Count - 1;
+            // Pattern unrolled by jit https://github.com/dotnet/coreclr/pull/8001
+            for (; i >= 0; i--)
+            {
+                candidate = vector64[i];
+                if (candidate != 0)
+                {
+                    break;
+                }
+            }
+
+            // Single LEA instruction with jitted const (using function result)
+            return i * 4 + LocateLastFoundChar(candidate);
+        }
+
+        [MethodImpl(MethodImplOptions.AggressiveInlining)]
+        private static int LocateLastFoundChar(ulong match)
+        {
+            // Find the most significant char that has its highest bit set
+            int index = 3;
+            while ((long)match > 0)
+            {
+                match = match << 16;
+                index--;
+            }
+            return index;
+        }
+
         // Returns the index of the last occurrence of any specified character in the current instance.
         // The search starts at startIndex and runs backwards to startIndex - count + 1.
         // The character at position startIndex is included in the search.  startIndex is the larger