diff options
author | Ahson Khan <ahkha@microsoft.com> | 2018-03-29 02:33:56 +0300 |
---|---|---|
committer | Ahson Khan <ahkha@microsoft.com> | 2018-03-29 20:31:34 +0300 |
commit | de3f215edb25f753fd20335a9737b0c3a96dbb34 (patch) | |
tree | 10d9134422b463fe52ad47c1fbc3657ae3f1bc2c /src | |
parent | d2a2400241aeb7604e8acc1c3be7f3146bf24662 (diff) |
Use ROSpan.IndexOf as the workhorse for string.IndexOf (#17284)
* Use ROSpan.IndexOf as the workhorse for string.IndexOf
* Make changes to Span.IndexOf to follow what string.IndexOf did.
* Address PR feedback.
* Use Unsafe.Read instead of Unsafe.ReadUnaligned.
* Remove special casing for count == 0
* Fix up debug assert to use vector count instead of intptr.size
* Use size of Vector<ushort> instead of Vector<byte>.Count
Signed-off-by: dotnet-bot <dotnet-bot@microsoft.com>
Diffstat (limited to 'src')
-rw-r--r-- | src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs | 128 | ||||
-rw-r--r-- | src/System.Private.CoreLib/shared/System/String.Searching.cs | 116 |
2 files changed, 73 insertions, 171 deletions
diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs index 2033d8b90..47e83b7b2 100644 --- a/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs +++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs @@ -84,79 +84,87 @@ namespace System { 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) + fixed (char* pChars = &searchSpace) { - 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: + char* pCh = pChars; + char* pEndCh = pCh + length; + +#if !netstandard11 + if (Vector.IsHardwareAccelerated && length >= Vector<ushort>.Count * 2) + { + const int elementsPerByte = sizeof(ushort) / sizeof(byte); + int unaligned = ((int)pCh & (Unsafe.SizeOf<Vector<ushort>>() - 1)) / elementsPerByte; + length = ((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 (length >= 4) + { + length -= 4; + + if (*pCh == value) + goto Found; + if (*(pCh + 1) == value) + goto Found1; + if (*(pCh + 2) == value) + goto Found2; + if (*(pCh + 3) == value) + goto Found3; + + pCh += 4; + } - while ((byte*)nLength > (byte*)0) - { - nLength -= 1; + while (length > 0) + { + length -= 1; - if (uValue == Unsafe.Add(ref searchSpace, index)) - goto Found; + if (*pCh == value) + goto Found; - index += 1; - } + pCh += 1; + } #if !netstandard11 - if (Vector.IsHardwareAccelerated && ((int)(byte*)index < length)) - { - nLength = (IntPtr)((length - (int)(byte*)index) & ~(Vector<ushort>.Count - 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) + { + length = (int)((pEndCh - pCh) & ~(Vector<ushort>.Count - 1)); - // Get comparison Vector - Vector<ushort> vComparison = new Vector<ushort>(value); + // 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)) + while (length > 0) { - index += Vector<ushort>.Count; - continue; + // Using Unsafe.Read instead of ReadUnaligned since the search space is pinned and pCh is always vector aligned + Debug.Assert(((int)pCh & (Unsafe.SizeOf<Vector<ushort>>() - 1)) == 0); + Vector<ushort> vMatches = Vector.Equals(vComparison, Unsafe.Read<Vector<ushort>>(pCh)); + if (Vector<ushort>.Zero.Equals(vMatches)) + { + pCh += Vector<ushort>.Count; + length -= Vector<ushort>.Count; + continue; + } + // Find offset of first match + return (int)(pCh - pChars) + LocateFirstFoundChar(vMatches); } - // Find offset of first match - return (int)(byte*)index + LocateFirstFoundChar(vMatches); - } - if ((int)(byte*)index < length) - { - nLength = (IntPtr)(length - (int)(byte*)index); - goto SequentialScan; + if (pCh < pEndCh) + { + length = (int)(pEndCh - pCh); + 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); + return -1; + Found3: + pCh++; + Found2: + pCh++; + Found1: + pCh++; + Found: + return (int)(pCh - pChars); + } } #if !netstandard11 diff --git a/src/System.Private.CoreLib/shared/System/String.Searching.cs b/src/System.Private.CoreLib/shared/System/String.Searching.cs index cc6e218d8..a4e5bbb62 100644 --- a/src/System.Private.CoreLib/shared/System/String.Searching.cs +++ b/src/System.Private.CoreLib/shared/System/String.Searching.cs @@ -35,10 +35,7 @@ namespace System // Returns the index of the first occurrence of a specified character in the current instance. // The search starts at startIndex and runs thorough the next count characters. // - public int IndexOf(char value) - { - return IndexOf(value, 0, this.Length); - } + public int IndexOf(char value) => SpanHelpers.IndexOf(ref _firstChar, value, Length); public int IndexOf(char value, int startIndex) { @@ -74,122 +71,19 @@ namespace System public unsafe int IndexOf(char value, int startIndex, int count) { + // These bounds checks are redundant since AsSpan does them already, but are required + // so that the correct parameter name is thrown as part of the exception. if ((uint)startIndex > (uint)Length) throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index); 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; - if (*(pCh + 1) == value) goto ReturnIndex1; - if (*(pCh + 2) == value) goto ReturnIndex2; - if (*(pCh + 3) == value) goto ReturnIndex3; - - count -= 4; - pCh += 4; - } - - while (count > 0) - { - if (*pCh == value) - goto ReturnIndex; - - count--; - 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; + int result = SpanHelpers.IndexOf(ref Unsafe.Add(ref _firstChar, startIndex), value, count); - ReturnIndex3: pCh++; - ReturnIndex2: pCh++; - ReturnIndex1: pCh++; - ReturnIndex: - return (int)(pCh - pChars); - } + return result == -1 ? result : result + startIndex; } - // 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. // |