From ba7d5ce44419bb419562d50ed1c720a3465dbf11 Mon Sep 17 00:00:00 2001
From: Ben Adams <thundercat@illyriad.co.uk>
Date: Wed, 21 Nov 2018 00:44:56 +0000
Subject: [PATCH] Vectorize Array.{Last}IndexOf<T>(...) for byte and char
 (#21116)

* Vectorize Array.IndexOf<T>(...) for byte and char

* Also LastIndexOf
---
 .../src/System/Array.cs                       | 48 +++++++++++++++++--
 .../Collections/Generic/EqualityComparer.cs   | 16 +++----
 2 files changed, 53 insertions(+), 11 deletions(-)

diff --git a/src/System.Private.CoreLib/src/System/Array.cs b/src/System.Private.CoreLib/src/System/Array.cs
index b181afccf8..253ac51005 100644
--- a/src/System.Private.CoreLib/src/System/Array.cs
+++ b/src/System.Private.CoreLib/src/System/Array.cs
@@ -1341,16 +1341,36 @@ namespace System
                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
             }
 
-            if (startIndex < 0 || startIndex > array.Length)
+            if ((uint)startIndex > (uint)array.Length)
             {
                 ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
             }
 
-            if (count < 0 || count > array.Length - startIndex)
+            if ((uint)count > (uint)(array.Length - startIndex))
             {
                 ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
             }
 
+            if (typeof(T) == typeof(byte))
+            {
+                int result = SpanHelpers.IndexOf(
+                    ref Unsafe.Add(ref array.GetRawSzArrayData(), startIndex),
+                    Unsafe.As<T, byte>(ref value),
+                    count);
+
+                return (result >= 0 ? startIndex : 0) + result;
+            }
+
+            if (typeof(T) == typeof(char))
+            {
+                int result = SpanHelpers.IndexOf(
+                    ref Unsafe.Add(ref Unsafe.As<byte, char>(ref array.GetRawSzArrayData()), startIndex),
+                    Unsafe.As<T, char>(ref value),
+                    count);
+
+                return (result >= 0 ? startIndex : 0) + result;
+            }
+
             return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count);
         }
 
@@ -1499,7 +1519,7 @@ namespace System
             }
 
             // Make sure we're not out of range            
-            if (startIndex < 0 || startIndex >= array.Length)
+            if ((uint)startIndex >= (uint)array.Length)
             {
                 ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
             }
@@ -1510,6 +1530,28 @@ namespace System
                 ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
             }
 
+            if (typeof(T) == typeof(byte))
+            {
+                int endIndex = startIndex - count + 1;
+                int result = SpanHelpers.LastIndexOf(
+                    ref Unsafe.Add(ref array.GetRawSzArrayData(), endIndex),
+                    Unsafe.As<T, byte>(ref value),
+                    count);
+
+                return (result >= 0 ? endIndex : 0) + result;
+            }
+
+            if (typeof(T) == typeof(char))
+            {
+                int endIndex = startIndex - count + 1;
+                int result = SpanHelpers.LastIndexOf(
+                    ref Unsafe.Add(ref Unsafe.As<byte, char>(ref array.GetRawSzArrayData()), endIndex),
+                    Unsafe.As<T, char>(ref value),
+                    count);
+
+                return (result >= 0 ? endIndex : 0) + result;
+            }
+
             return EqualityComparer<T>.Default.LastIndexOf(array, value, startIndex, count);
         }
 
diff --git a/src/System.Private.CoreLib/src/System/Collections/Generic/EqualityComparer.cs b/src/System.Private.CoreLib/src/System/Collections/Generic/EqualityComparer.cs
index 4c7a70553e..5e778fdb28 100644
--- a/src/System.Private.CoreLib/src/System/Collections/Generic/EqualityComparer.cs
+++ b/src/System.Private.CoreLib/src/System/Collections/Generic/EqualityComparer.cs
@@ -11,6 +11,7 @@ using System.Globalization;
 using System.Runtime;
 using System.Runtime.CompilerServices;
 using System.Runtime.Serialization;
+using System.Diagnostics;
 
 namespace System.Collections.Generic
 {
@@ -272,8 +273,6 @@ namespace System.Collections.Generic
             GetType().GetHashCode();
     }
 
-    // Performance of IndexOf on byte array is very important for some scenarios.
-    // We will call the C runtime function memchr, which is optimized.
     [Serializable]
     [System.Runtime.CompilerServices.TypeForwardedFrom("mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
     // Needs to be public to support binary serialization compatibility
@@ -291,18 +290,19 @@ namespace System.Collections.Generic
             return b.GetHashCode();
         }
 
-        internal unsafe override int IndexOf(byte[] array, byte value, int startIndex, int count)
+#if DEBUG
+        internal override int IndexOf(byte[] array, byte value, int startIndex, int count)
         {
-            int found = new ReadOnlySpan<byte>(array, startIndex, count).IndexOf(value);
-            return (found >= 0) ? (startIndex + found) : found;
+             Debug.Fail("Should not get here.");
+             return -1;
         }
 
         internal override int LastIndexOf(byte[] array, byte value, int startIndex, int count)
         {
-            int endIndex = startIndex - count + 1;
-            int found = new ReadOnlySpan<byte>(array, endIndex, count).LastIndexOf(value);
-            return (found >= 0) ? (endIndex + found) : found;
+             Debug.Fail("Should not get here.");
+             return -1;
         }
+#endif
 
         // Equals method for the comparer itself.
         public override bool Equals(object obj) =>
-- 
2.34.1