From 69a2e2dd3324a090a928e914e07c09e267ff435a Mon Sep 17 00:00:00 2001 From: Grant Date: Fri, 7 Sep 2018 15:25:42 -0700 Subject: [PATCH] MemoryExtensions.Contains (dotnet/coreclr#19863) Commit migrated from https://github.com/dotnet/coreclr/commit/91820bdd42711266faae1c15d2176b9f47e48efe --- .../System.Private.CoreLib/src/System/Guid.cs | 2 +- .../src/System/MemoryExtensions.Fast.cs | 14 --- .../src/System/MemoryExtensions.cs | 54 ++++++++++ .../src/System/SpanHelpers.Byte.cs | 94 ++++++++++++++++- .../src/System/SpanHelpers.Char.cs | 113 +++++++++++++++++---- .../src/System/SpanHelpers.T.cs | 64 +++++++++++- .../System.Private.CoreLib/src/System/Version.cs | 2 +- 7 files changed, 304 insertions(+), 39 deletions(-) diff --git a/src/libraries/System.Private.CoreLib/src/System/Guid.cs b/src/libraries/System.Private.CoreLib/src/System/Guid.cs index 01c0e88..c57d3c4 100644 --- a/src/libraries/System.Private.CoreLib/src/System/Guid.cs +++ b/src/libraries/System.Private.CoreLib/src/System/Guid.cs @@ -427,7 +427,7 @@ namespace System } // Check for dashes - bool dashesExistInString = guidString.IndexOf('-') >= 0; + bool dashesExistInString = guidString.Contains('-'); if (dashesExistInString) { diff --git a/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.Fast.cs b/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.Fast.cs index efd11c9..e86ca4f 100644 --- a/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.Fast.cs +++ b/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.Fast.cs @@ -83,20 +83,6 @@ namespace System return CompareInfo.EqualsOrdinalIgnoreCase(ref MemoryMarshal.GetReference(span), ref MemoryMarshal.GetReference(value), span.Length); } - // TODO https://github.com/dotnet/corefx/issues/27526 - internal static bool Contains(this ReadOnlySpan source, char value) - { - for (int i = 0; i < source.Length; i++) - { - if (source[i] == value) - { - return true; - } - } - - return false; - } - /// /// Compares the specified and using the specified , /// and returns an integer that indicates their relative position in the sort order. diff --git a/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.cs b/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.cs index 739bc31..f0937c4 100644 --- a/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.cs +++ b/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.cs @@ -183,6 +183,56 @@ namespace System } /// + /// Searches for the specified value and returns true if found. If not found, returns false. Values are compared using IEquatable{T}.Equals(T). + /// + /// + /// The span to search. + /// The value to search for. + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static bool Contains(this Span span, T value) + where T : IEquatable + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.Contains( + ref Unsafe.As(ref MemoryMarshal.GetReference(span)), + Unsafe.As(ref value), + span.Length); + + if (typeof(T) == typeof(char)) + return SpanHelpers.Contains( + ref Unsafe.As(ref MemoryMarshal.GetReference(span)), + Unsafe.As(ref value), + span.Length); + + return SpanHelpers.Contains(ref MemoryMarshal.GetReference(span), value, span.Length); + } + + /// + /// Searches for the specified value and returns true if found. If not found, returns false. Values are compared using IEquatable{T}.Equals(T). + /// + /// + /// The span to search. + /// The value to search for. + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static bool Contains(this ReadOnlySpan span, T value) + where T : IEquatable + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.Contains( + ref Unsafe.As(ref MemoryMarshal.GetReference(span)), + Unsafe.As(ref value), + span.Length); + + if (typeof(T) == typeof(char)) + return SpanHelpers.Contains( + ref Unsafe.As(ref MemoryMarshal.GetReference(span)), + Unsafe.As(ref value), + span.Length); + + return SpanHelpers.Contains(ref MemoryMarshal.GetReference(span), value, span.Length); + } + + /// /// Searches for the specified value and returns the index of its first occurrence. If not found, returns -1. Values are compared using IEquatable{T}.Equals(T). /// /// The span to search. @@ -196,6 +246,7 @@ 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)), @@ -238,6 +289,7 @@ namespace System ref Unsafe.As(ref MemoryMarshal.GetReference(span)), Unsafe.As(ref value), span.Length); + if (typeof(T) == typeof(char)) return SpanHelpers.LastIndexOf( ref Unsafe.As(ref MemoryMarshal.GetReference(span)), @@ -322,6 +374,7 @@ 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)), @@ -364,6 +417,7 @@ namespace System ref Unsafe.As(ref MemoryMarshal.GetReference(span)), Unsafe.As(ref value), span.Length); + if (typeof(T) == typeof(char)) return SpanHelpers.LastIndexOf( ref Unsafe.As(ref MemoryMarshal.GetReference(span)), diff --git a/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Byte.cs b/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Byte.cs index 2890adb..3730653 100644 --- a/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Byte.cs +++ b/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Byte.cs @@ -16,7 +16,7 @@ using nuint = System.UInt32; namespace System { - internal static partial class SpanHelpers + internal static partial class SpanHelpers // .Byte { public static int IndexOf(ref byte searchSpace, int searchSpaceLength, ref byte value, int valueLength) { @@ -96,6 +96,98 @@ namespace System return index; } + // Adapted from IndexOf(...) + public static unsafe bool Contains(ref byte searchSpace, byte 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 (Vector.IsHardwareAccelerated && length >= Vector.Count * 2) + { + int unaligned = (int)Unsafe.AsPointer(ref searchSpace) & (Vector.Count - 1); + nLength = (IntPtr)((Vector.Count - unaligned) & (Vector.Count - 1)); + } + + SequentialScan: + while ((byte*)nLength >= (byte*)8) + { + nLength -= 8; + + if (uValue == Unsafe.AddByteOffset(ref searchSpace, index + 0) || + uValue == Unsafe.AddByteOffset(ref searchSpace, index + 1) || + uValue == Unsafe.AddByteOffset(ref searchSpace, index + 2) || + uValue == Unsafe.AddByteOffset(ref searchSpace, index + 3) || + uValue == Unsafe.AddByteOffset(ref searchSpace, index + 4) || + uValue == Unsafe.AddByteOffset(ref searchSpace, index + 5) || + uValue == Unsafe.AddByteOffset(ref searchSpace, index + 6) || + uValue == Unsafe.AddByteOffset(ref searchSpace, index + 7)) + { + goto Found; + } + + index += 8; + } + + if ((byte*)nLength >= (byte*)4) + { + nLength -= 4; + + if (uValue == Unsafe.AddByteOffset(ref searchSpace, index + 0) || + uValue == Unsafe.AddByteOffset(ref searchSpace, index + 1) || + uValue == Unsafe.AddByteOffset(ref searchSpace, index + 2) || + uValue == Unsafe.AddByteOffset(ref searchSpace, index + 3)) + { + goto Found; + } + + index += 4; + } + + while ((byte*)nLength > (byte*)0) + { + nLength -= 1; + + if (uValue == Unsafe.AddByteOffset(ref searchSpace, index)) + goto Found; + + index += 1; + } + + 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.AddByteOffset(ref searchSpace, index))); + if (Vector.Zero.Equals(vMatches)) + { + index += Vector.Count; + continue; + } + + goto Found; + } + + if ((int)(byte*)index < length) + { + nLength = (IntPtr)(length - (int)(byte*)index); + goto SequentialScan; + } + } + + return false; + + Found: + return true; + } + public static unsafe int IndexOf(ref byte searchSpace, byte value, int length) { Debug.Assert(length >= 0); diff --git a/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Char.cs b/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Char.cs index 51ace58..02df69f 100644 --- a/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Char.cs +++ b/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Char.cs @@ -4,18 +4,15 @@ using System.Diagnostics; using System.Runtime.CompilerServices; +using System.Numerics; #if !netstandard using Internal.Runtime.CompilerServices; #endif -#if !netstandard11 -using System.Numerics; -#endif - namespace System { - internal static partial class SpanHelpers + internal static partial class SpanHelpers // .Char { public static unsafe int SequenceCompareTo(ref char first, int firstLength, ref char second, int secondLength) { @@ -32,7 +29,6 @@ namespace System if ((byte*)minLength >= (byte*)(sizeof(UIntPtr) / sizeof(char))) { -#if !netstandard11 if (Vector.IsHardwareAccelerated && (byte*)minLength >= (byte*)Vector.Count) { IntPtr nLength = minLength - Vector.Count; @@ -47,7 +43,6 @@ namespace System } while ((byte*)nLength >= (byte*)i); } -#endif while ((byte*)minLength >= (byte*)(i + sizeof(UIntPtr) / sizeof(char))) { @@ -81,6 +76,94 @@ namespace System return lengthDelta; } + // Adapted from IndexOf(...) + public static unsafe bool Contains(ref char searchSpace, char value, int length) + { + Debug.Assert(length >= 0); + + fixed (char* pChars = &searchSpace) + { + char* pCh = pChars; + char* pEndCh = pCh + length; + + if (Vector.IsHardwareAccelerated && length >= Vector.Count * 2) + { + // Figure out how many characters to read sequentially until we are vector aligned + // This is equivalent to: + // unaligned = ((int)pCh % Unsafe.SizeOf>()) / elementsPerByte + // length = (Vector.Count - unaligned) % Vector.Count + const int elementsPerByte = sizeof(ushort) / sizeof(byte); + int unaligned = ((int)pCh & (Unsafe.SizeOf>() - 1)) / elementsPerByte; + length = (Vector.Count - unaligned) & (Vector.Count - 1); + } + + SequentialScan: + while (length >= 4) + { + length -= 4; + + if (value == *pCh || + value == *(pCh + 1) || + value == *(pCh + 2) || + value == *(pCh + 3)) + { + goto Found; + } + + pCh += 4; + } + + while (length > 0) + { + length -= 1; + + if (value == *pCh) + goto Found; + + pCh += 1; + } + + // We get past SequentialScan only if IsHardwareAccelerated is true. However, we still have the redundant check to allow + // the JIT to see that the code is unreachable and eliminate it when the platform does not have hardware accelerated. + if (Vector.IsHardwareAccelerated && pCh < pEndCh) + { + // Get the highest multiple of Vector.Count that is within the search space. + // That will be how many times we iterate in the loop below. + // This is equivalent to: length = Vector.Count * ((int)(pEndCh - pCh) / Vector.Count) + length = (int)((pEndCh - pCh) & ~(Vector.Count - 1)); + + // Get comparison Vector + Vector vComparison = new Vector(value); + + while (length > 0) + { + // Using Unsafe.Read instead of ReadUnaligned since the search space is pinned and pCh is always vector aligned + Debug.Assert(((int)pCh & (Unsafe.SizeOf>() - 1)) == 0); + Vector vMatches = Vector.Equals(vComparison, Unsafe.Read>(pCh)); + if (Vector.Zero.Equals(vMatches)) + { + pCh += Vector.Count; + length -= Vector.Count; + continue; + } + + goto Found; + } + + if (pCh < pEndCh) + { + length = (int)(pEndCh - pCh); + goto SequentialScan; + } + } + + return false; + + Found: + return true; + } + } + public static unsafe int IndexOf(ref char searchSpace, char value, int length) { Debug.Assert(length >= 0); @@ -90,7 +173,6 @@ namespace System char* pCh = pChars; char* pEndCh = pCh + length; -#if !netstandard11 if (Vector.IsHardwareAccelerated && length >= Vector.Count * 2) { // Figure out how many characters to read sequentially until we are vector aligned @@ -101,8 +183,8 @@ namespace System int unaligned = ((int)pCh & (Unsafe.SizeOf>() - 1)) / elementsPerByte; length = (Vector.Count - unaligned) & (Vector.Count - 1); } + SequentialScan: -#endif while (length >= 4) { length -= 4; @@ -128,7 +210,7 @@ namespace System pCh += 1; } -#if !netstandard11 + // We get past SequentialScan only if IsHardwareAccelerated is true. However, we still have the redundant check to allow // the JIT to see that the code is unreachable and eliminate it when the platform does not have hardware accelerated. if (Vector.IsHardwareAccelerated && pCh < pEndCh) @@ -162,7 +244,7 @@ namespace System goto SequentialScan; } } -#endif + return -1; Found3: pCh++; @@ -184,7 +266,6 @@ namespace System char* pCh = pChars + length; char* pEndCh = pChars; -#if !netstandard11 if (Vector.IsHardwareAccelerated && length >= Vector.Count * 2) { // Figure out how many characters to read sequentially from the end until we are vector aligned @@ -192,8 +273,8 @@ namespace System const int elementsPerByte = sizeof(ushort) / sizeof(byte); length = ((int)pCh & (Unsafe.SizeOf>() - 1)) / elementsPerByte; } + SequentialScan: -#endif while (length >= 4) { length -= 4; @@ -217,7 +298,7 @@ namespace System if (*pCh == value) goto Found; } -#if !netstandard11 + // We get past SequentialScan only if IsHardwareAccelerated is true. However, we still have the redundant check to allow // the JIT to see that the code is unreachable and eliminate it when the platform does not have hardware accelerated. if (Vector.IsHardwareAccelerated && pCh > pEndCh) @@ -252,7 +333,7 @@ namespace System goto SequentialScan; } } -#endif + return -1; Found: return (int)(pCh - pEndCh); @@ -265,7 +346,6 @@ namespace System } } -#if !netstandard11 // Vector sub-search adapted from https://github.com/aspnet/KestrelHttpServer/pull/1138 [MethodImpl(MethodImplOptions.AggressiveInlining)] private static int LocateFirstFoundChar(Vector match) @@ -336,6 +416,5 @@ namespace System } return index; } -#endif } } diff --git a/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.T.cs b/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.T.cs index d7a27fd..20fdc61 100644 --- a/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.T.cs +++ b/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.T.cs @@ -4,18 +4,15 @@ using System.Diagnostics; using System.Runtime.CompilerServices; // Do not remove. This is necessary for netstandard, since this file is mirrored into corefx +using System.Numerics; #if !netstandard using Internal.Runtime.CompilerServices; #endif -#if !netstandard11 -using System.Numerics; -#endif - namespace System { - internal static partial class SpanHelpers + internal static partial class SpanHelpers // .T { public static int IndexOf(ref T searchSpace, int searchSpaceLength, ref T value, int valueLength) where T : IEquatable @@ -53,6 +50,63 @@ namespace System return -1; } + // Adapted from IndexOf(...) + public static unsafe bool Contains(ref T searchSpace, T value, int length) + where T : IEquatable + { + Debug.Assert(length >= 0); + + IntPtr index = (IntPtr)0; // Use IntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + while (length >= 8) + { + length -= 8; + + if (value.Equals(Unsafe.Add(ref searchSpace, index + 0)) || + value.Equals(Unsafe.Add(ref searchSpace, index + 1)) || + value.Equals(Unsafe.Add(ref searchSpace, index + 2)) || + value.Equals(Unsafe.Add(ref searchSpace, index + 3)) || + value.Equals(Unsafe.Add(ref searchSpace, index + 4)) || + value.Equals(Unsafe.Add(ref searchSpace, index + 5)) || + value.Equals(Unsafe.Add(ref searchSpace, index + 6)) || + value.Equals(Unsafe.Add(ref searchSpace, index + 7))) + { + goto Found; + } + + index += 8; + } + + if (length >= 4) + { + length -= 4; + + if (value.Equals(Unsafe.Add(ref searchSpace, index + 0)) || + value.Equals(Unsafe.Add(ref searchSpace, index + 1)) || + value.Equals(Unsafe.Add(ref searchSpace, index + 2)) || + value.Equals(Unsafe.Add(ref searchSpace, index + 3))) + { + goto Found; + } + + index += 4; + } + + while (length > 0) + { + length -= 1; + + if (value.Equals(Unsafe.Add(ref searchSpace, index))) + goto Found; + + index += 1; + } + + return false; + + Found: + return true; + } + public static unsafe int IndexOf(ref T searchSpace, T value, int length) where T : IEquatable { diff --git a/src/libraries/System.Private.CoreLib/src/System/Version.cs b/src/libraries/System.Private.CoreLib/src/System/Version.cs index 9d24270..444ee48 100644 --- a/src/libraries/System.Private.CoreLib/src/System/Version.cs +++ b/src/libraries/System.Private.CoreLib/src/System/Version.cs @@ -341,7 +341,7 @@ namespace System if (buildEnd != -1) { buildEnd += (minorEnd + 1); - if (input.Slice(buildEnd + 1).IndexOf('.') != -1) + if (input.Slice(buildEnd + 1).Contains('.')) { if (throwOnFailure) throw new ArgumentException(SR.Arg_VersionString, nameof(input)); return null; -- 2.7.4