From 6860d110a843e882357d82d2a72205343339b11b Mon Sep 17 00:00:00 2001 From: Stephen Toub Date: Fri, 20 Jul 2018 03:56:57 -0700 Subject: [PATCH] Improve throughput of TimeSpan.ToString/TryFormat with "g"/"G" (#19051) * Improve throughput of TimeSpan.ToString/TryFormat with "g"/"G" TimeSpan has three standard formats: "c", "g", and "G". Yesterday I updated its implementation with throughput improvements for "c" (the default) based on porting the design from Utf8Formatter; this PR does so for "g"/"G". Initially I wasn't going to handle "g"/"G" as they factor in culture (Utf8Formatter doesn't), but even with accessing the current culture there are still significant wins to be had. I was also going to keep the "c" and "g"/"G" implementations separate, to avoid bogging down the default "c" formatting with additional conditions needed to support "g"/"G", but the overhead incurred for that turns out to be minimal enough that it's worth keeping one implementation rather than two mostly-similar ones... the impact on "c" is mostly within noise. This PR makes a significant throughput improvement for "g"/"G" formatting. It also removes several unnecessary allocations, such that TryFormat with "g"/"G" is now allocation-free (and ToString just allocates the asked-for string). * Address PR feedback --- .../Buffers/Text/FormattingHelpers.CountDigits.cs | 29 +++ .../System/Globalization/DateTimeFormatInfo.cs | 28 ++- .../shared/System/Globalization/TimeSpanFormat.cs | 238 +++++++++++---------- 3 files changed, 175 insertions(+), 120 deletions(-) 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 index 709ac4f..b6140ad 100644 --- a/src/System.Private.CoreLib/shared/System/Buffers/Text/FormattingHelpers.CountDigits.cs +++ b/src/System.Private.CoreLib/shared/System/Buffers/Text/FormattingHelpers.CountDigits.cs @@ -128,5 +128,34 @@ namespace System.Buffers.Text return digits; } + + + // Counts the number of trailing '0' digits in a decimal number. + // e.g., value = 0 => retVal = 0, valueWithoutTrailingZeros = 0 + // value = 1234 => retVal = 0, valueWithoutTrailingZeros = 1234 + // value = 320900 => retVal = 2, valueWithoutTrailingZeros = 3209 + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int CountDecimalTrailingZeros(uint value, out uint valueWithoutTrailingZeros) + { + int zeroCount = 0; + + if (value != 0) + { + while (true) + { + uint temp = value / 10; + if (value != (temp * 10)) + { + break; + } + + value = temp; + zeroCount++; + } + } + + valueWithoutTrailingZeros = value; + return zeroCount; + } } } diff --git a/src/System.Private.CoreLib/shared/System/Globalization/DateTimeFormatInfo.cs b/src/System.Private.CoreLib/shared/System/Globalization/DateTimeFormatInfo.cs index 1b47c37..8fc6f7b 100644 --- a/src/System.Private.CoreLib/shared/System/Globalization/DateTimeFormatInfo.cs +++ b/src/System.Private.CoreLib/shared/System/Globalization/DateTimeFormatInfo.cs @@ -2010,6 +2010,25 @@ namespace System.Globalization } // + // Decimal separator used by positive TimeSpan pattern + // + private string _decimalSeparator; + internal string DecimalSeparator + { + get + { + if (_decimalSeparator == null) + { + CultureData cultureDataWithoutUserOverrides = _cultureData.UseUserOverride ? + CultureData.GetCultureData(_cultureData.CultureName, false) : + _cultureData; + _decimalSeparator = new NumberFormatInfo(cultureDataWithoutUserOverrides).NumberDecimalSeparator; + } + return _decimalSeparator; + } + } + + // // Positive TimeSpan Pattern // private string _fullTimeSpanPositivePattern; @@ -2019,14 +2038,7 @@ namespace System.Globalization { if (_fullTimeSpanPositivePattern == null) { - CultureData cultureDataWithoutUserOverrides; - if (_cultureData.UseUserOverride) - cultureDataWithoutUserOverrides = CultureData.GetCultureData(_cultureData.CultureName, false); - else - cultureDataWithoutUserOverrides = _cultureData; - string decimalSeparator = new NumberFormatInfo(cultureDataWithoutUserOverrides).NumberDecimalSeparator; - - _fullTimeSpanPositivePattern = "d':'h':'mm':'ss'" + decimalSeparator + "'FFFFFFF"; + _fullTimeSpanPositivePattern = "d':'h':'mm':'ss'" + DecimalSeparator + "'FFFFFFF"; } return _fullTimeSpanPositivePattern; } diff --git a/src/System.Private.CoreLib/shared/System/Globalization/TimeSpanFormat.cs b/src/System.Private.CoreLib/shared/System/Globalization/TimeSpanFormat.cs index 169e12f..786ada3 100644 --- a/src/System.Private.CoreLib/shared/System/Globalization/TimeSpanFormat.cs +++ b/src/System.Private.CoreLib/shared/System/Globalization/TimeSpanFormat.cs @@ -3,10 +3,10 @@ // See the LICENSE file in the project root for more information. using System.Buffers.Text; -using System.Text; using System.Diagnostics; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; +using System.Text; namespace System.Globalization { @@ -41,20 +41,57 @@ namespace System.Globalization /// Main method called from TimeSpan.ToString. internal static string Format(TimeSpan value, string format, IFormatProvider formatProvider) { - return IsFormatC(format) ? // special-case to optimize the default TimeSpan format - FormatC(value) : // formatProvider ignored, as "c" is invariant - StringBuilderCache.GetStringAndRelease(FormatToBuilder(value, format, formatProvider)); + if (string.IsNullOrEmpty(format)) + { + return FormatC(value); // formatProvider ignored, as "c" is invariant + } + + if (format.Length == 1) + { + char c = format[0]; + + if (c == 'c' || (c | 0x20) == 't') // special-case to optimize the default TimeSpan format + { + return FormatC(value); // formatProvider ignored, as "c" is invariant + } + + if ((c | 0x20) == 'g') // special-case to optimize the remaining 'g'/'G' standard formats + { + return FormatG(value, DateTimeFormatInfo.GetInstance(formatProvider), c == 'G' ? StandardFormat.G : StandardFormat.g); + } + + throw new FormatException(SR.Format_InvalidString); + } + + return StringBuilderCache.GetStringAndRelease(FormatCustomized(value, format, DateTimeFormatInfo.GetInstance(formatProvider), result: null)); } /// Main method called from TimeSpan.TryFormat. internal static bool TryFormat(TimeSpan value, Span destination, out int charsWritten, ReadOnlySpan format, IFormatProvider formatProvider) { - if (IsFormatC(format)) // special-case to optimize the default TimeSpan format + if (format.Length == 0) + { + return TryFormatStandard(value, StandardFormat.C, null, destination, out charsWritten); + } + + if (format.Length == 1) { - return TryFormatC(value, destination, out charsWritten); // formatProvider ignored, as "c" is invariant + char c = format[0]; + if (c == 'c' || ((c | 0x20) == 't')) + { + return TryFormatStandard(value, StandardFormat.C, null, destination, out charsWritten); + } + else + { + StandardFormat sf = + c == 'g' ? StandardFormat.g : + c == 'G' ? StandardFormat.G : + throw new FormatException(SR.Format_InvalidString); + return TryFormatStandard(value, sf, DateTimeFormatInfo.GetInstance(formatProvider).DecimalSeparator, destination, out charsWritten); + } } - StringBuilder sb = FormatToBuilder(value, format, formatProvider); + StringBuilder sb = FormatCustomized(value, format, DateTimeFormatInfo.GetInstance(formatProvider), result: null); if (sb.Length <= destination.Length) { @@ -69,45 +106,30 @@ namespace System.Globalization return false; } - private static StringBuilder FormatToBuilder(TimeSpan value, ReadOnlySpan format, IFormatProvider formatProvider) + internal static string FormatC(TimeSpan value) { - // Standard formats other than 'c'/'t'/'T', which should have already been handled. - if (format.Length == 1) - { - char f = format[0]; - switch (f) - { - case 'g': - case 'G': - DateTimeFormatInfo dtfi = DateTimeFormatInfo.GetInstance(formatProvider); - return FormatG( - value, - format: value.Ticks < 0 ? dtfi.FullTimeSpanNegativePattern : dtfi.FullTimeSpanPositivePattern, - full: f == 'G'); - - default: - throw new FormatException(SR.Format_InvalidString); - } - } - - // Custom formats - return FormatCustomized(value, format, DateTimeFormatInfo.GetInstance(formatProvider), result: null); + Span destination = stackalloc char[26]; // large enough for any "c" TimeSpan + TryFormatStandard(value, StandardFormat.C, null, destination, out int charsWritten); + return new string(destination.Slice(0, charsWritten)); } - [MethodImpl(MethodImplOptions.AggressiveInlining)] - private static bool IsFormatC(ReadOnlySpan format) => - format.Length == 0 || - (format.Length == 1 && (format[0] == 'c' || (format[0] | 0x20) == 't')); - - internal static string FormatC(TimeSpan value) + private static string FormatG(TimeSpan value, DateTimeFormatInfo dtfi, StandardFormat format) { - Span destination = stackalloc char[26]; // large enough for any "c" TimeSpan - TryFormatC(value, destination, out int charsWritten); + string decimalSeparator = dtfi.DecimalSeparator; + int maxLength = 25 + decimalSeparator.Length; // large enough for any "g"/"G" TimeSpan + Span destination = maxLength < 128 ? + stackalloc char[maxLength] : + new char[maxLength]; // the chances of needing this case are almost 0, as DecimalSeparator.Length will basically always == 1 + TryFormatStandard(value, format, dtfi.DecimalSeparator, destination, out int charsWritten); return new string(destination.Slice(0, charsWritten)); } - private static bool TryFormatC(TimeSpan value, Span destination, out int charsWritten) + private enum StandardFormat { C, G, g } + + private static bool TryFormatStandard(TimeSpan value, StandardFormat format, string decimalSeparator, Span destination, out int charsWritten) { + Debug.Assert(format == StandardFormat.C || format == StandardFormat.G || format == StandardFormat.g); + // First, calculate how large an output buffer is needed to hold the entire output. int requiredOutputLength = 8; // start with "hh:mm:ss" and adjust as necessary @@ -138,12 +160,34 @@ namespace System.Globalization AfterComputeFraction: // Only write out the fraction if it's non-zero, and in that // case write out the entire fraction (all digits). + Debug.Assert(fraction < 10_000_000); int fractionDigits = 0; - if (fraction != 0) + switch (format) { - Debug.Assert(fraction < 10_000_000); - fractionDigits = DateTimeFormat.MaxSecondsFractionDigits; - requiredOutputLength += fractionDigits + 1; // If we're going to write out a fraction, also need to write the leading decimal. + case StandardFormat.C: + // "c": Write out a fraction only if it's non-zero, and write out all 7 digits of it. + if (fraction != 0) + { + fractionDigits = DateTimeFormat.MaxSecondsFractionDigits; + requiredOutputLength += fractionDigits + 1; // digits plus leading decimal separator + } + break; + + case StandardFormat.G: + // "G": Write out a fraction regardless of whether it's 0, and write out all 7 digits of it. + fractionDigits = DateTimeFormat.MaxSecondsFractionDigits; + requiredOutputLength += fractionDigits + 1; // digits plus leading decimal separator + break; + + default: + // "g": Write out a fraction only if it's non-zero, and write out only the most significant digits. + Debug.Assert(format == StandardFormat.g); + if (fraction != 0) + { + fractionDigits = DateTimeFormat.MaxSecondsFractionDigits - FormattingHelpers.CountDecimalTrailingZeros(fraction, out fraction); + requiredOutputLength += fractionDigits + 1; // digits plus leading decimal separator + } + break; } ulong totalMinutesRemaining = 0, seconds = 0; @@ -173,6 +217,14 @@ namespace System.Globalization Debug.Assert(hours < 24); } + int hourDigits = 2; + if (format == StandardFormat.g && hours < 10) + { + // "g": Only writing a one-digit hour, rather than expected two-digit hour + hourDigits = 1; + requiredOutputLength--; + } + int dayDigits = 0; if (days > 0) { @@ -180,6 +232,12 @@ namespace System.Globalization Debug.Assert(dayDigits <= 8); requiredOutputLength += dayDigits + 1; // for the leading "d." } + else if (format == StandardFormat.G) + { + // "G": has a leading "0:" if days is 0 + requiredOutputLength += 2; + dayDigits = 1; + } if (destination.Length < requiredOutputLength) { @@ -199,12 +257,20 @@ namespace System.Globalization { WriteDigits(days, destination.Slice(idx, dayDigits)); idx += dayDigits; - destination[idx++] = '.'; + destination[idx++] = format == StandardFormat.C ? '.' : ':'; } - // Write "hh:mm:ss" - WriteTwoDigits(hours, destination.Slice(idx)); - idx += 2; + // Write "[h]h:mm:ss + Debug.Assert(hourDigits == 1 || hourDigits == 2); + if (hourDigits == 2) + { + WriteTwoDigits(hours, destination.Slice(idx)); + idx += 2; + } + else + { + destination[idx++] = (char)('0' + hours); + } destination[idx++] = ':'; WriteTwoDigits((uint)minutes, destination.Slice(idx)); idx += 2; @@ -215,7 +281,19 @@ namespace System.Globalization // Write fraction and separator, if necessary if (fractionDigits != 0) { - destination[idx++] = '.'; + if (format == StandardFormat.C) + { + destination[idx++] = '.'; + } + else if (decimalSeparator.Length == 1) + { + destination[idx++] = decimalSeparator[0]; + } + else + { + decimalSeparator.AsSpan().CopyTo(destination); + idx += decimalSeparator.Length; + } WriteDigits(fraction, destination.Slice(idx, fractionDigits)); idx += fractionDigits; } @@ -252,71 +330,7 @@ namespace System.Globalization } /// Format the TimeSpan instance using the specified format. - private static StringBuilder FormatG(TimeSpan value, ReadOnlySpan format, bool full) - { - int day = (int)(value.Ticks / TimeSpan.TicksPerDay); - long time = value.Ticks % TimeSpan.TicksPerDay; - - if (value.Ticks < 0) - { - day = -day; - time = -time; - } - int hours = (int)(time / TimeSpan.TicksPerHour % 24); - int minutes = (int)(time / TimeSpan.TicksPerMinute % 60); - int seconds = (int)(time / TimeSpan.TicksPerSecond % 60); - int fraction = (int)(time % TimeSpan.TicksPerSecond); - - FormatLiterals literal = new FormatLiterals(); - literal.Init(format, full); - - if (fraction != 0) - { - // truncate the partial second to the specified length - fraction = (int)(fraction / TimeSpanParse.Pow10(DateTimeFormat.MaxSecondsFractionDigits - literal.ff)); - } - - // full: [-]dd.hh:mm:ss.fffffff - // !full: [-][d.]hh:mm:ss[.fffffff] - - StringBuilder sb = StringBuilderCache.Acquire(InternalGlobalizationHelper.StringBuilderDefaultCapacity); - sb.Append(literal.Start); // [-] - if (full || day != 0) - { - sb.Append(day); // [dd] - sb.Append(literal.DayHourSep); // [.] - } // - AppendNonNegativeInt32(sb, hours, literal.hh); // hh - sb.Append(literal.HourMinuteSep); // : - AppendNonNegativeInt32(sb, minutes, literal.mm); // mm - sb.Append(literal.MinuteSecondSep); // : - AppendNonNegativeInt32(sb, seconds, literal.ss); // ss - if (!full) - { - int effectiveDigits = literal.ff; - while (effectiveDigits > 0 && fraction % 10 == 0) - { - fraction = fraction / 10; - effectiveDigits--; - } - if (effectiveDigits > 0) - { - sb.Append(literal.SecondFractionSep); // [.FFFFFFF] - sb.Append((fraction).ToString(DateTimeFormat.fixedNumberFormats[effectiveDigits - 1], CultureInfo.InvariantCulture)); - } - } - else - { - sb.Append(literal.SecondFractionSep); // [.] - AppendNonNegativeInt32(sb, fraction, literal.ff); // [fffffff] - } - sb.Append(literal.End); - - return sb; - } - - /// Format the TimeSpan instance using the specified format. - private static StringBuilder FormatCustomized(TimeSpan value, ReadOnlySpan format, DateTimeFormatInfo dtfi, StringBuilder result) + private static StringBuilder FormatCustomized(TimeSpan value, ReadOnlySpan format, DateTimeFormatInfo dtfi, StringBuilder result = null) { Debug.Assert(dtfi != null); -- 2.7.4