diff options
author | Stephen Toub <stoub@microsoft.com> | 2018-04-05 18:55:43 +0300 |
---|---|---|
committer | Stephen Toub <stoub@microsoft.com> | 2018-04-05 20:59:39 +0300 |
commit | 79215333d1dac7e23d59743ecbcbf9e0e04f23d7 (patch) | |
tree | 73ec0f1a0dfb611ee5dda6e2a42d5066f3120c1b /src | |
parent | 4596d662c7598f67ccbb808561aa1e35a013ddb2 (diff) |
Merge pull request dotnet/coreclr#17432 from stephentoub/portnumericperf
Improve {u}int/long.ToString/TryFormat throughput by pre-computing the length
Signed-off-by: dotnet-bot <dotnet-bot@microsoft.com>
Diffstat (limited to 'src')
3 files changed, 329 insertions, 139 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 d5c432e12..542c91e2f 100644 --- a/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems +++ b/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems @@ -52,6 +52,7 @@ <Compile Include="$(MSBuildThisFileDirectory)System\Buffers\MemoryManager.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\Buffers\TlsOverPerCoreLockedStacksArrayPool.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\Buffers\Utilities.cs" /> + <Compile Include="$(MSBuildThisFileDirectory)System\Buffers\Text\FormattingHelpers.CountDigits.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\Byte.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\Char.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\CharEnumerator.cs" /> diff --git a/src/System.Private.CoreLib/shared/System/Buffers/Text/FormattingHelpers.CountDigits.cs b/src/System.Private.CoreLib/shared/System/Buffers/Text/FormattingHelpers.CountDigits.cs new file mode 100644 index 000000000..709ac4fba --- /dev/null +++ b/src/System.Private.CoreLib/shared/System/Buffers/Text/FormattingHelpers.CountDigits.cs @@ -0,0 +1,132 @@ +// 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; + +namespace System.Buffers.Text +{ + internal static partial class FormattingHelpers + { + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int CountDigits(ulong value) + { + int digits = 1; + uint part; + if (value >= 10000000) + { + if (value >= 100000000000000) + { + part = (uint)(value / 100000000000000); + digits += 14; + } + else + { + part = (uint)(value / 10000000); + digits += 7; + } + } + else + { + part = (uint)value; + } + + if (part < 10) + { + // no-op + } + else if (part < 100) + { + digits += 1; + } + else if (part < 1000) + { + digits += 2; + } + else if (part < 10000) + { + digits += 3; + } + else if (part < 100000) + { + digits += 4; + } + else if (part < 1000000) + { + digits += 5; + } + else + { + Debug.Assert(part < 10000000); + digits += 6; + } + + return digits; + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int CountDigits(uint value) + { + int digits = 1; + if (value >= 100000) + { + value = value / 100000; + digits += 5; + } + + if (value < 10) + { + // no-op + } + else if (value < 100) + { + digits += 1; + } + else if (value < 1000) + { + digits += 2; + } + else if (value < 10000) + { + digits += 3; + } + else + { + Debug.Assert(value < 100000); + digits += 4; + } + + return digits; + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int CountHexDigits(ulong value) + { + // TODO: When x86 intrinsic support comes online, experiment with implementing this using lzcnt. + // return 16 - (int)((uint)Lzcnt.LeadingZeroCount(value | 1) >> 3); + + int digits = 1; + + if (value > 0xFFFFFFFF) + { + digits += 8; + value >>= 0x20; + } + if (value > 0xFFFF) + { + digits += 4; + value >>= 0x10; + } + if (value > 0xFF) + { + digits += 2; + value >>= 0x8; + } + if (value > 0xF) + digits++; + + return digits; + } + } +} diff --git a/src/System.Private.CoreLib/shared/System/Number.Formatting.cs b/src/System.Private.CoreLib/shared/System/Number.Formatting.cs index 24d5db1da..74395ab2f 100644 --- a/src/System.Private.CoreLib/shared/System/Number.Formatting.cs +++ b/src/System.Private.CoreLib/shared/System/Number.Formatting.cs @@ -2,6 +2,7 @@ // 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.Buffers.Text; using System.Diagnostics; using System.Globalization; using System.Runtime.CompilerServices; @@ -246,9 +247,7 @@ namespace System private const int DoublePrecision = 15; private const int ScaleNAN = unchecked((int)0x80000000); private const int ScaleINF = 0x7FFFFFFF; - private const int MaxUInt32HexDigits = 8; private const int MaxUInt32DecDigits = 10; - private const int MaxUInt64DecDigits = 20; private const int CharStackBufferSize = 32; private const string PosNumberFormat = "#"; @@ -972,18 +971,20 @@ namespace System if (digits < 1) digits = 1; - int bufferLength = Math.Max(digits, MaxUInt32DecDigits) + sNegative.Length; - int index = bufferLength; - - char* buffer = stackalloc char[bufferLength]; - char* p = UInt32ToDecChars(buffer + bufferLength, (uint)(-value), digits); - for (int i = sNegative.Length - 1; i >= 0; i--) + int bufferLength = Math.Max(digits, FormattingHelpers.CountDigits((uint)(-value))) + sNegative.Length; + string result = string.FastAllocateString(bufferLength); + fixed (char* buffer = result) { - *(--p) = sNegative[i]; - } + char* p = UInt32ToDecChars(buffer + bufferLength, (uint)(-value), digits); + Debug.Assert(p == buffer + sNegative.Length); - Debug.Assert(buffer + bufferLength - p >= 0 && buffer <= p); - return new string(p, 0, (int)(buffer + bufferLength - p)); + for (int i = sNegative.Length - 1; i >= 0; i--) + { + *(--p) = sNegative[i]; + } + Debug.Assert(p == buffer); + } + return result; } private static unsafe bool TryNegativeInt32ToDecStr(int value, int digits, string sNegative, Span<char> destination, out int charsWritten) @@ -993,18 +994,26 @@ namespace System if (digits < 1) digits = 1; - int bufferLength = Math.Max(digits, MaxUInt32DecDigits) + sNegative.Length; - int index = bufferLength; - - char* buffer = stackalloc char[bufferLength]; - char* p = UInt32ToDecChars(buffer + bufferLength, (uint)(-value), digits); - for (int i = sNegative.Length - 1; i >= 0; i--) + int bufferLength = Math.Max(digits, FormattingHelpers.CountDigits((uint)(-value))) + sNegative.Length; + if (bufferLength > destination.Length) { - *(--p) = sNegative[i]; + charsWritten = 0; + return false; } - Debug.Assert(buffer + bufferLength - p >= 0 && buffer <= p); - return TryCopyTo(p, (int)(buffer + bufferLength - p), destination, out charsWritten); + charsWritten = bufferLength; + fixed (char* buffer = &MemoryMarshal.GetReference(destination)) + { + char* p = UInt32ToDecChars(buffer + bufferLength, (uint)(-value), digits); + Debug.Assert(p == buffer + sNegative.Length); + + for (int i = sNegative.Length - 1; i >= 0; i--) + { + *(--p) = sNegative[i]; + } + Debug.Assert(p == buffer); + } + return true; } private static unsafe string Int32ToHexStr(int value, char hexBase, int digits) @@ -1012,11 +1021,14 @@ namespace System if (digits < 1) digits = 1; - int bufferLength = Math.Max(digits, MaxUInt32HexDigits); - char* buffer = stackalloc char[bufferLength]; - - char* p = Int32ToHexChars(buffer + bufferLength, (uint)value, hexBase, digits); - return new string(p, 0, (int)(buffer + bufferLength - p)); + int bufferLength = Math.Max(digits, FormattingHelpers.CountHexDigits((uint)value)); + string result = string.FastAllocateString(bufferLength); + fixed (char* buffer = result) + { + char* p = Int32ToHexChars(buffer + bufferLength, (uint)value, hexBase, digits); + Debug.Assert(p == buffer); + } + return result; } private static unsafe bool TryInt32ToHexStr(int value, char hexBase, int digits, Span<char> destination, out int charsWritten) @@ -1024,11 +1036,20 @@ namespace System if (digits < 1) digits = 1; - int bufferLength = Math.Max(digits, MaxUInt32HexDigits); - char* buffer = stackalloc char[bufferLength]; + int bufferLength = Math.Max(digits, FormattingHelpers.CountHexDigits((uint)value)); + if (bufferLength > destination.Length) + { + charsWritten = 0; + return false; + } - char* p = Int32ToHexChars(buffer + bufferLength, (uint)value, hexBase, digits); - return TryCopyTo(p, (int)(buffer + bufferLength - p), destination, out charsWritten); + charsWritten = bufferLength; + fixed (char* buffer = &MemoryMarshal.GetReference(destination)) + { + char* p = Int32ToHexChars(buffer + bufferLength, (uint)value, hexBase, digits); + Debug.Assert(p == buffer); + } + return true; } private static unsafe char* Int32ToHexChars(char* buffer, uint value, int hexBase, int digits) @@ -1073,56 +1094,62 @@ namespace System private static unsafe string UInt32ToDecStr(uint value, int digits) { - if (digits <= 1) + int bufferLength = Math.Max(digits, FormattingHelpers.CountDigits(value)); + string result = string.FastAllocateString(bufferLength); + fixed (char* buffer = result) { - char* buffer = stackalloc char[MaxUInt32DecDigits]; - - char* start = buffer + MaxUInt32DecDigits; - char* p = start; - do + char* p = buffer + bufferLength; + if (digits <= 1) + { + do + { + // TODO https://github.com/dotnet/coreclr/issues/3439 + uint div = value / 10; + *(--p) = (char)('0' + value - (div * 10)); + value = div; + } + while (value != 0); + } + else { - // TODO https://github.com/dotnet/coreclr/issues/3439 - uint div = value / 10; - *(--p) = (char)('0' + value - (div * 10)); - value = div; + p = UInt32ToDecChars(p, value, digits); } - while (value != 0); - - return new string(p, 0, (int)(start - p)); - } - else - { - int bufferSize = Math.Max(digits, MaxUInt32DecDigits); - char* buffer = stackalloc char[bufferSize]; - char* p = UInt32ToDecChars(buffer + bufferSize, value, digits); - return new string(p, 0, (int)(buffer + bufferSize - p)); + Debug.Assert(p == buffer); } + return result; } private static unsafe bool TryUInt32ToDecStr(uint value, int digits, Span<char> destination, out int charsWritten) { - if (digits <= 1) + int bufferLength = Math.Max(digits, FormattingHelpers.CountDigits(value)); + if (bufferLength > destination.Length) { - char* buffer = stackalloc char[MaxUInt32DecDigits]; - char* start = buffer + MaxUInt32DecDigits; - char* p = start; - do - { - // TODO https://github.com/dotnet/coreclr/issues/3439 - uint div = value / 10; - *(--p) = (char)('0' + value - (div * 10)); - value = div; - } - while (value != 0); - return TryCopyTo(p, (int)(start - p), destination, out charsWritten); + charsWritten = 0; + return false; } - else + + charsWritten = bufferLength; + fixed (char* buffer = &MemoryMarshal.GetReference(destination)) { - int bufferSize = Math.Max(digits, MaxUInt32DecDigits); - char* buffer = stackalloc char[bufferSize]; - char* p = UInt32ToDecChars(buffer + bufferSize, value, digits); - return TryCopyTo(p, (int)(buffer + bufferSize - p), destination, out charsWritten); + char* p = buffer + bufferLength; + if (digits <= 1) + { + do + { + // TODO https://github.com/dotnet/coreclr/issues/3439 + uint div = value / 10; + *(--p) = (char)('0' + value - (div * 10)); + value = div; + } + while (value != 0); + } + else + { + p = UInt32ToDecChars(p, value, digits); + } + Debug.Assert(p == buffer); } + return true; } [MethodImpl(MethodImplOptions.AggressiveInlining)] @@ -1176,24 +1203,26 @@ namespace System ulong value = (ulong)(-input); - int bufferLength = Math.Max(digits, MaxUInt64DecDigits) + sNegative.Length; - int index = bufferLength; - - char* buffer = stackalloc char[bufferLength]; - char* p = buffer + bufferLength; - while (High32(value) != 0) + int bufferLength = Math.Max(digits, FormattingHelpers.CountDigits(value)) + sNegative.Length; + string result = string.FastAllocateString(bufferLength); + fixed (char* buffer = result) { - p = UInt32ToDecChars(p, Int64DivMod1E9(ref value), 9); - digits -= 9; - } - p = UInt32ToDecChars(p, Low32(value), digits); + char* p = buffer + bufferLength; + while (High32(value) != 0) + { + p = UInt32ToDecChars(p, Int64DivMod1E9(ref value), 9); + digits -= 9; + } + p = UInt32ToDecChars(p, Low32(value), digits); + Debug.Assert(p == buffer + sNegative.Length); - for (int i = sNegative.Length - 1; i >= 0; i--) - { - *(--p) = sNegative[i]; + for (int i = sNegative.Length - 1; i >= 0; i--) + { + *(--p) = sNegative[i]; + } + Debug.Assert(p == buffer); } - - return new string(p, 0, (int)(buffer + bufferLength - p)); + return result; } private static unsafe bool TryNegativeInt64ToDecStr(long input, int digits, string sNegative, Span<char> destination, out int charsWritten) @@ -1207,64 +1236,80 @@ namespace System ulong value = (ulong)(-input); - int bufferLength = Math.Max(digits, MaxUInt64DecDigits) + sNegative.Length; - int index = bufferLength; - - char* buffer = stackalloc char[bufferLength]; - char* p = buffer + bufferLength; - while (High32(value) != 0) + int bufferLength = Math.Max(digits, FormattingHelpers.CountDigits((ulong)(-input))) + sNegative.Length; + if (bufferLength > destination.Length) { - p = UInt32ToDecChars(p, Int64DivMod1E9(ref value), 9); - digits -= 9; + charsWritten = 0; + return false; } - p = UInt32ToDecChars(p, Low32(value), digits); - for (int i = sNegative.Length - 1; i >= 0; i--) + charsWritten = bufferLength; + fixed (char* buffer = &MemoryMarshal.GetReference(destination)) { - *(--p) = sNegative[i]; - } + char* p = buffer + bufferLength; + while (High32(value) != 0) + { + p = UInt32ToDecChars(p, Int64DivMod1E9(ref value), 9); + digits -= 9; + } + p = UInt32ToDecChars(p, Low32(value), digits); + Debug.Assert(p == buffer + sNegative.Length); - return TryCopyTo(p, (int)(buffer + bufferLength - p), destination, out charsWritten); + for (int i = sNegative.Length - 1; i >= 0; i--) + { + *(--p) = sNegative[i]; + } + Debug.Assert(p == buffer); + } + return true; } private static unsafe string Int64ToHexStr(long value, char hexBase, int digits) { - int bufferLength = Math.Max(digits, MaxUInt32HexDigits * 2); - char* buffer = stackalloc char[bufferLength]; - int index = bufferLength; - - char* p; - if (High32((ulong)value) != 0) + int bufferLength = Math.Max(digits, FormattingHelpers.CountHexDigits((ulong)value)); + string result = string.FastAllocateString(bufferLength); + fixed (char* buffer = result) { - p = Int32ToHexChars(buffer + index, Low32((ulong)value), hexBase, 8); - p = Int32ToHexChars(p, High32((ulong)value), hexBase, digits - 8); - } - else - { - p = Int32ToHexChars(buffer + index, Low32((ulong)value), hexBase, Math.Max(digits, 1)); + char* p = buffer + bufferLength; + if (High32((ulong)value) != 0) + { + p = Int32ToHexChars(p, Low32((ulong)value), hexBase, 8); + p = Int32ToHexChars(p, High32((ulong)value), hexBase, digits - 8); + } + else + { + p = Int32ToHexChars(p, Low32((ulong)value), hexBase, Math.Max(digits, 1)); + } + Debug.Assert(p == buffer); } - - return new string(p, 0, (int)(buffer + bufferLength - p)); + return result; } private static unsafe bool TryInt64ToHexStr(long value, char hexBase, int digits, Span<char> destination, out int charsWritten) { - int bufferLength = Math.Max(digits, MaxUInt32HexDigits * 2); - char* buffer = stackalloc char[bufferLength]; - int index = bufferLength; - - char* p; - if (High32((ulong)value) != 0) + int bufferLength = Math.Max(digits, FormattingHelpers.CountHexDigits((ulong)value)); + if (bufferLength > destination.Length) { - p = Int32ToHexChars(buffer + index, Low32((ulong)value), hexBase, 8); - p = Int32ToHexChars(p, High32((ulong)value), hexBase, digits - 8); + charsWritten = 0; + return false; } - else + + charsWritten = bufferLength; + fixed (char* buffer = &MemoryMarshal.GetReference(destination)) { - p = Int32ToHexChars(buffer + index, Low32((ulong)value), hexBase, Math.Max(digits, 1)); + char* p = buffer + bufferLength; + if (High32((ulong)value) != 0) + { + p = Int32ToHexChars(p, Low32((ulong)value), hexBase, 8); + p = Int32ToHexChars(p, High32((ulong)value), hexBase, digits - 8); + } + else + { + p = Int32ToHexChars(p, Low32((ulong)value), hexBase, Math.Max(digits, 1)); + } + Debug.Assert(p == buffer); } - - return TryCopyTo(p, (int)(buffer + bufferLength - p), destination, out charsWritten); + return true; } private static unsafe void UInt64ToNumber(ulong value, ref NumberBuffer number) @@ -1293,17 +1338,20 @@ namespace System if (digits < 1) digits = 1; - int bufferSize = Math.Max(digits, MaxUInt64DecDigits); - char* buffer = stackalloc char[bufferSize]; - char* p = buffer + bufferSize; - while (High32(value) != 0) + int bufferLength = Math.Max(digits, FormattingHelpers.CountDigits(value)); + string result = string.FastAllocateString(bufferLength); + fixed (char* buffer = result) { - p = UInt32ToDecChars(p, Int64DivMod1E9(ref value), 9); - digits -= 9; + char* p = buffer + bufferLength; + while (High32(value) != 0) + { + p = UInt32ToDecChars(p, Int64DivMod1E9(ref value), 9); + digits -= 9; + } + p = UInt32ToDecChars(p, Low32(value), digits); + Debug.Assert(p == buffer); } - p = UInt32ToDecChars(p, Low32(value), digits); - - return new string(p, 0, (int)(buffer + bufferSize - p)); + return result; } private static unsafe bool TryUInt64ToDecStr(ulong value, int digits, Span<char> destination, out int charsWritten) @@ -1311,17 +1359,26 @@ namespace System if (digits < 1) digits = 1; - int bufferSize = Math.Max(digits, MaxUInt64DecDigits); - char* buffer = stackalloc char[bufferSize]; - char* p = buffer + bufferSize; - while (High32(value) != 0) + int bufferLength = Math.Max(digits, FormattingHelpers.CountDigits(value)); + if (bufferLength > destination.Length) { - p = UInt32ToDecChars(p, Int64DivMod1E9(ref value), 9); - digits -= 9; + charsWritten = 0; + return false; } - p = UInt32ToDecChars(p, Low32(value), digits); - return TryCopyTo(p, (int)(buffer + bufferSize - p), destination, out charsWritten); + charsWritten = bufferLength; + fixed (char* buffer = &MemoryMarshal.GetReference(destination)) + { + char* p = buffer + bufferLength; + while (High32(value) != 0) + { + p = UInt32ToDecChars(p, Int64DivMod1E9(ref value), 9); + digits -= 9; + } + p = UInt32ToDecChars(p, Low32(value), digits); + Debug.Assert(p == buffer); + } + return true; } internal static unsafe char ParseFormatSpecifier(ReadOnlySpan<char> format, out int digits) |