From 1aaace7e617d40d92e6f97cf8ed2b211c34151be Mon Sep 17 00:00:00 2001 From: dotnet bot Date: Mon, 26 Mar 2018 00:58:25 -0700 Subject: [PATCH] Vectorize Span.IndexOf for T = char, similar to T = byte. (#28464) (#17218) Signed-off-by: dotnet-bot-corefx-mirror --- src/mscorlib/shared/System/MemoryExtensions.cs | 10 ++ src/mscorlib/shared/System/SpanHelpers.T.cs | 126 ++++++++++++++++++++++++- 2 files changed, 134 insertions(+), 2 deletions(-) diff --git a/src/mscorlib/shared/System/MemoryExtensions.cs b/src/mscorlib/shared/System/MemoryExtensions.cs index 46cf7a1..0a06f35 100644 --- a/src/mscorlib/shared/System/MemoryExtensions.cs +++ b/src/mscorlib/shared/System/MemoryExtensions.cs @@ -204,6 +204,11 @@ namespace System ref Unsafe.As(ref MemoryMarshal.GetReference(span)), Unsafe.As(ref value), span.Length); + if (typeof(T) == typeof(char)) + return SpanHelpers.IndexOf( + ref Unsafe.As(ref MemoryMarshal.GetReference(span)), + Unsafe.As(ref value), + span.Length); return SpanHelpers.IndexOf(ref MemoryMarshal.GetReference(span), value, span.Length); } @@ -313,6 +318,11 @@ namespace System ref Unsafe.As(ref MemoryMarshal.GetReference(span)), Unsafe.As(ref value), span.Length); + if (typeof(T) == typeof(char)) + return SpanHelpers.IndexOf( + ref Unsafe.As(ref MemoryMarshal.GetReference(span)), + Unsafe.As(ref value), + span.Length); return SpanHelpers.IndexOf(ref MemoryMarshal.GetReference(span), value, span.Length); } diff --git a/src/mscorlib/shared/System/SpanHelpers.T.cs b/src/mscorlib/shared/System/SpanHelpers.T.cs index 88938ac..818216b 100644 --- a/src/mscorlib/shared/System/SpanHelpers.T.cs +++ b/src/mscorlib/shared/System/SpanHelpers.T.cs @@ -3,11 +3,14 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; +using System.Runtime.CompilerServices; #if !netstandard using Internal.Runtime.CompilerServices; -#else -using System.Runtime.CompilerServices; +#endif + +#if !netstandard11 +using System.Numerics; #endif namespace System @@ -124,6 +127,85 @@ 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.Count * 2) + { + const int elementsPerByte = sizeof(ushort) / sizeof(byte); + int unaligned = ((int)Unsafe.AsPointer(ref searchSpace) & (Vector.Count - 1)) / elementsPerByte; + nLength = (IntPtr)((Vector.Count - unaligned) & (Vector.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.Count - 1)); + + // Get comparison Vector + Vector vComparison = new Vector(value); + + while ((byte*)nLength > (byte*)index) + { + var vMatches = Vector.Equals(vComparison, Unsafe.ReadUnaligned>(ref Unsafe.As(ref Unsafe.Add(ref searchSpace, index)))); + if (Vector.Zero.Equals(vMatches)) + { + index += Vector.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(ref T searchSpace, T value0, T value1, int length) where T : IEquatable { @@ -679,5 +761,45 @@ 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 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.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 + } } -- 2.7.4