diff options
author | Jan Kotas <jkotas@microsoft.com> | 2018-03-27 10:27:21 +0300 |
---|---|---|
committer | Jan Kotas <jkotas@microsoft.com> | 2018-03-27 17:08:29 +0300 |
commit | 4fc352f3863dc36af329c4e6af7da7bcb4a0adb2 (patch) | |
tree | 535cd1e00757a627fd380e2a8f988d1dabd09d94 /src | |
parent | 5911cea5aad2d9fd020adf25d68234e3e2358fca (diff) |
Vectorized SequenceCompareTo for Span<char> (dotnet/coreclr#17237)
- This change makes the compare for very short Span strings a bit slower and for longer Span strings many times faster.
- Switch several places where it was a clear benefit to use it.
`String.CompareOrdinal(string,string)` is notable exception that I have left intact for now. It is fine tuned for current string layout, and replacing with a call of vectorized SequenceCompareTo gives mixed results.
Signed-off-by: dotnet-bot <dotnet-bot@microsoft.com>
Diffstat (limited to 'src')
6 files changed, 226 insertions, 141 deletions
diff --git a/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems b/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems index f4f8dd32a..4f7e0614e 100644 --- a/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems +++ b/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems @@ -492,6 +492,7 @@ <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.BinarySearch.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.Byte.cs" /> + <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.Char.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.T.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\String.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\String.Manipulation.cs" /> diff --git a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs index 4ccd739bc..079b8afbc 100644 --- a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs +++ b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs @@ -341,7 +341,7 @@ namespace System.Globalization if (_invariantMode) { if ((options & CompareOptions.IgnoreCase) != 0) - return CompareOrdinalIgnoreCase(string1, 0, string1.Length, string2, 0, string2.Length); + return CompareOrdinalIgnoreCase(string1, string2); return String.CompareOrdinal(string1, string2); } @@ -501,35 +501,23 @@ namespace System.Globalization return (1); } + ReadOnlySpan<char> span1 = string1.AsSpan(offset1, length1); + ReadOnlySpan<char> span2 = string2.AsSpan(offset2, length2); + if (options == CompareOptions.Ordinal) { - return CompareOrdinal(string1, offset1, length1, - string2, offset2, length2); + return string.CompareOrdinal(span1, span2); } if (_invariantMode) { if ((options & CompareOptions.IgnoreCase) != 0) - return CompareOrdinalIgnoreCase(string1, offset1, length1, string2, offset2, length2); + return CompareOrdinalIgnoreCase(span1, span2); - return CompareOrdinal(string1, offset1, length1, string2, offset2, length2); + return string.CompareOrdinal(span1, span2); } - return CompareString( - string1.AsSpan(offset1, length1), - string2.AsSpan(offset2, length2), - options); - } - - private static int CompareOrdinal(string string1, int offset1, int length1, string string2, int offset2, int length2) - { - int result = String.CompareOrdinal(string1, offset1, string2, offset2, - (length1 < length2 ? length1 : length2)); - if ((length1 != length2) && result == 0) - { - return (length1 > length2 ? 1 : -1); - } - return (result); + return CompareString(span1, span2, options); } // diff --git a/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs b/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs index 0a06f3584..1a3b33acc 100644 --- a/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs +++ b/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs @@ -301,6 +301,13 @@ namespace System ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(other)), other.Length); + if (typeof(T) == typeof(char)) + return SpanHelpers.SequenceCompareTo( + ref Unsafe.As<T, char>(ref MemoryMarshal.GetReference(span)), + span.Length, + ref Unsafe.As<T, char>(ref MemoryMarshal.GetReference(other)), + other.Length); + return SpanHelpers.SequenceCompareTo(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(other), other.Length); } @@ -659,6 +666,13 @@ namespace System ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(other)), other.Length); + if (typeof(T) == typeof(char)) + return SpanHelpers.SequenceCompareTo( + ref Unsafe.As<T, char>(ref MemoryMarshal.GetReference(span)), + span.Length, + ref Unsafe.As<T, char>(ref MemoryMarshal.GetReference(other)), + other.Length); + return SpanHelpers.SequenceCompareTo(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(other), other.Length); } diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs new file mode 100644 index 000000000..2033d8b90 --- /dev/null +++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs @@ -0,0 +1,201 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Diagnostics; +using System.Runtime.CompilerServices; + +#if !netstandard +using Internal.Runtime.CompilerServices; +#endif + +#if !netstandard11 +using System.Numerics; +#endif + +namespace System +{ + internal static partial class SpanHelpers + { + public static unsafe int SequenceCompareTo(ref char first, int firstLength, ref char second, int secondLength) + { + Debug.Assert(firstLength >= 0); + Debug.Assert(secondLength >= 0); + + int lengthDelta = firstLength - secondLength; + + if (Unsafe.AreSame(ref first, ref second)) + goto Equal; + + IntPtr minLength = (IntPtr)((firstLength < secondLength) ? firstLength : secondLength); + IntPtr i = (IntPtr)0; // Use IntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + + if ((byte*)minLength >= (byte*)(sizeof(UIntPtr) / sizeof(char))) + { +#if !netstandard11 + if (Vector.IsHardwareAccelerated && (byte*)minLength >= (byte*)Vector<ushort>.Count) + { + IntPtr nLength = minLength - Vector<ushort>.Count; + do + { + if (Unsafe.ReadUnaligned<Vector<ushort>>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref first, i))) != + Unsafe.ReadUnaligned<Vector<ushort>>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref second, i)))) + { + break; + } + i += Vector<ushort>.Count; + } + while ((byte*)nLength >= (byte*)i); + } +#endif + + while ((byte*)minLength >= (byte*)(i + sizeof(UIntPtr) / sizeof(char))) + { + if (Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref first, i))) != + Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref second, i)))) + { + break; + } + i += sizeof(UIntPtr) / sizeof(char); + } + } + + if (sizeof(UIntPtr) > sizeof(int) && (byte*)minLength >= (byte*)(i + sizeof(int) / sizeof(char))) + { + if (Unsafe.ReadUnaligned<int>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref first, i))) == + Unsafe.ReadUnaligned<int>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref second, i)))) + { + i += sizeof(int) / sizeof(char); + } + } + + while ((byte*)i < (byte*)minLength) + { + int result = Unsafe.Add(ref first, i).CompareTo(Unsafe.Add(ref second, i)); + if (result != 0) return result; + i += 1; + } + + Equal: + return lengthDelta; + } + + 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<ushort>.Count * 2) + { + 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: +#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<ushort>.Count - 1)); + + // 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)) + { + index += Vector<ushort>.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); + } + +#if !netstandard11 + // 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; +#endif + } +} diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs index 818216bff..4567deddb 100644 --- a/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs +++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs @@ -127,85 +127,6 @@ 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<ushort>.Count * 2) - { - 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: -#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<ushort>.Count - 1)); - - // 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)) - { - index += Vector<ushort>.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<T>(ref T searchSpace, T value0, T value1, int length) where T : IEquatable<T> { @@ -761,45 +682,5 @@ 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<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; -#endif - } } diff --git a/src/System.Private.CoreLib/shared/System/String.Manipulation.cs b/src/System.Private.CoreLib/shared/System/String.Manipulation.cs index d2aac0d43..69609aacf 100644 --- a/src/System.Private.CoreLib/shared/System/String.Manipulation.cs +++ b/src/System.Private.CoreLib/shared/System/String.Manipulation.cs @@ -1541,7 +1541,7 @@ namespace System if (this[i] == separator[0] && currentSepLength <= Length - i) { if (currentSepLength == 1 - || CompareOrdinal(this, i, separator, 0, currentSepLength) == 0) + || this.AsSpan(i, currentSepLength).SequenceEqual(separator)) { sepListBuilder.Append(i); i += currentSepLength - 1; @@ -1575,7 +1575,7 @@ namespace System if (this[i] == separator[0] && currentSepLength <= Length - i) { if (currentSepLength == 1 - || CompareOrdinal(this, i, separator, 0, currentSepLength) == 0) + || this.AsSpan(i, currentSepLength).SequenceEqual(separator)) { sepListBuilder.Append(i); lengthListBuilder.Append(currentSepLength); |