Skip to content

Improve performance of FormattingHelper.CountDigits(uint)#76519

Merged
stephentoub merged 1 commit intodotnet:mainfrom
stephentoub:countdigits
Oct 3, 2022
Merged

Improve performance of FormattingHelper.CountDigits(uint)#76519
stephentoub merged 1 commit intodotnet:mainfrom
stephentoub:countdigits

Conversation

@stephentoub
Copy link
Member

@stephentoub stephentoub commented Oct 3, 2022

Branch-free, table-based lookup implementation.

Method Toolchain value Mean Ratio Code Size
AllLengthsToString \main\corerun.exe ? 132.378 ns 1.00 315 B
AllLengthsToString \pr\corerun.exe ? 115.465 ns 0.86 245 B
AllLengthsTryFormat \main\corerun.exe ? 81.336 ns 1.00 338 B
AllLengthsTryFormat \pr\corerun.exe ? 66.679 ns 0.82 276 B
FixedLengthToString \main\corerun.exe 1 1.278 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 1 1.118 ns 0.87 208 B
FixedLengthTryFormat \main\corerun.exe 1 2.948 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 1 1.802 ns 0.61 206 B
FixedLengthToString \main\corerun.exe 12 9.863 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 12 9.311 ns 0.94 208 B
FixedLengthTryFormat \main\corerun.exe 12 4.427 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 12 2.763 ns 0.62 206 B
FixedLengthToString \main\corerun.exe 123 11.306 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 123 9.830 ns 0.87 208 B
FixedLengthTryFormat \main\corerun.exe 123 6.108 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 123 3.418 ns 0.56 206 B
FixedLengthToString \main\corerun.exe 1234 12.235 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 1234 10.797 ns 0.88 208 B
FixedLengthTryFormat \main\corerun.exe 1234 8.026 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 1234 4.153 ns 0.52 206 B
FixedLengthToString \main\corerun.exe 12345 13.264 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 12345 11.592 ns 0.87 208 B
FixedLengthTryFormat \main\corerun.exe 12345 9.675 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 12345 4.948 ns 0.51 206 B
FixedLengthToString \main\corerun.exe 123456 13.974 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 123456 13.332 ns 0.95 208 B
FixedLengthTryFormat \main\corerun.exe 123456 10.444 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 123456 5.970 ns 0.57 206 B
FixedLengthToString \main\corerun.exe 1234567 15.367 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 1234567 14.046 ns 0.91 208 B
FixedLengthTryFormat \main\corerun.exe 1234567 12.668 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 1234567 6.599 ns 0.52 206 B
FixedLengthToString \main\corerun.exe 12345678 16.666 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 12345678 14.880 ns 0.89 208 B
FixedLengthTryFormat \main\corerun.exe 12345678 14.293 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 12345678 7.512 ns 0.53 206 B
FixedLengthToString \main\corerun.exe 123456789 18.165 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 123456789 15.920 ns 0.87 208 B
FixedLengthTryFormat \main\corerun.exe 123456789 16.049 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 123456789 8.479 ns 0.53 206 B
FixedLengthToString \main\corerun.exe 1234567890 19.486 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 1234567890 17.430 ns 0.90 208 B
FixedLengthTryFormat \main\corerun.exe 1234567890 17.680 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 1234567890 9.488 ns 0.51 206 B 
private uint[] _values = new uint[] { 1, 1234567890, 12, 123456789, 123, 12345678, 1234, 1234567, 12345, 123456 };
private char[] _scratch = new char[20];

[Benchmark]
[Arguments(1)]
[Arguments(12)]
[Arguments(123)]
[Arguments(1234)]
[Arguments(12345)]
[Arguments(123456)]
[Arguments(1234567)]
[Arguments(12345678)]
[Arguments(123456789)]
[Arguments(1234567890)]
public string FixedLengthToString(uint value) => value.ToString();

[Benchmark]
[Arguments(1)]
[Arguments(12)]
[Arguments(123)]
[Arguments(1234)]
[Arguments(12345)]
[Arguments(123456)]
[Arguments(1234567)]
[Arguments(12345678)]
[Arguments(123456789)]
[Arguments(1234567890)]
public bool FixedLengthTryFormat(uint value) => value.TryFormat(_scratch, out _);

[Benchmark]
public int AllLengthsToString()
{
    int sum = 0;
    foreach (uint value in _values)
    {
        sum += value.ToString().Length;
    }
    return sum;
}

[Benchmark]
public bool AllLengthsTryFormat()
{
    bool success = true;
    foreach (uint value in _values)
    {
        success |= value.TryFormat(_scratch, out _);
    }
    return success;
}

@stephentoub
Improve FormattingHelper.CountDigit(uint)
2a248c7 
Branch-free, table-based lookup implementation.
@stephentoub stephentoub added this to the 8.0.0 milestone Oct 3, 2022
@ghost
Copy link

ghost commented Oct 3, 2022

Tagging subscribers to this area: @dotnet/area-system-runtime
See info in area-owners.md if you want to be subscribed.

Issue Details

Branch-free, table-based lookup implementation.

Method Toolchain value Mean Ratio Code Size
AllLengthsToString \main\corerun.exe ? 132.378 ns 1.00 315 B
AllLengthsToString \pr\corerun.exe ? 115.465 ns 0.86 245 B
AllLengthsTryFormat \main\corerun.exe ? 81.336 ns 1.00 338 B
AllLengthsTryFormat \pr\corerun.exe ? 66.679 ns 0.82 276 B
FixedLengthToString \main\corerun.exe 1 1.278 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 1 1.118 ns 0.87 208 B
FixedLengthTryFormat \main\corerun.exe 1 2.948 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 1 1.802 ns 0.61 206 B
FixedLengthToString \main\corerun.exe 12 9.863 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 12 9.311 ns 0.94 208 B
FixedLengthTryFormat \main\corerun.exe 12 4.427 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 12 2.763 ns 0.62 206 B
FixedLengthToString \main\corerun.exe 123 11.306 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 123 9.830 ns 0.87 208 B
FixedLengthTryFormat \main\corerun.exe 123 6.108 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 123 3.418 ns 0.56 206 B
FixedLengthToString \main\corerun.exe 1234 12.235 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 1234 10.797 ns 0.88 208 B
FixedLengthTryFormat \main\corerun.exe 1234 8.026 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 1234 4.153 ns 0.52 206 B
FixedLengthToString \main\corerun.exe 12345 13.264 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 12345 11.592 ns 0.87 208 B
FixedLengthTryFormat \main\corerun.exe 12345 9.675 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 12345 4.948 ns 0.51 206 B
FixedLengthToString \main\corerun.exe 123456 13.974 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 123456 13.332 ns 0.95 208 B
FixedLengthTryFormat \main\corerun.exe 123456 10.444 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 123456 5.970 ns 0.57 206 B
FixedLengthToString \main\corerun.exe 1234567 15.367 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 1234567 14.046 ns 0.91 208 B
FixedLengthTryFormat \main\corerun.exe 1234567 12.668 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 1234567 6.599 ns 0.52 206 B
FixedLengthToString \main\corerun.exe 12345678 16.666 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 12345678 14.880 ns 0.89 208 B
FixedLengthTryFormat \main\corerun.exe 12345678 14.293 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 12345678 7.512 ns 0.53 206 B
FixedLengthToString \main\corerun.exe 123456789 18.165 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 123456789 15.920 ns 0.87 208 B
FixedLengthTryFormat \main\corerun.exe 123456789 16.049 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 123456789 8.479 ns 0.53 206 B
FixedLengthToString \main\corerun.exe 1234567890 19.486 ns 1.00 278 B
FixedLengthToString \pr\corerun.exe 1234567890 17.430 ns 0.90 208 B
FixedLengthTryFormat \main\corerun.exe 1234567890 17.680 ns 1.00 272 B
FixedLengthTryFormat \pr\corerun.exe 1234567890 9.488 ns 0.51 206 B 
private uint[] _values = new uint[] { 1, 1234567890, 12, 123456789, 123, 12345678, 1234, 1234567, 12345, 123456 };
private char[] _scratch = new char[20];

[Benchmark]
[Arguments(1)]
[Arguments(12)]
[Arguments(123)]
[Arguments(1234)]
[Arguments(12345)]
[Arguments(123456)]
[Arguments(1234567)]
[Arguments(12345678)]
[Arguments(123456789)]
[Arguments(1234567890)]
public string FixedLengthToString(uint value) => value.ToString();

[Benchmark]
[Arguments(1)]
[Arguments(12)]
[Arguments(123)]
[Arguments(1234)]
[Arguments(12345)]
[Arguments(123456)]
[Arguments(1234567)]
[Arguments(12345678)]
[Arguments(123456789)]
[Arguments(1234567890)]
public bool FixedLengthTryFormat(uint value) => value.TryFormat(_scratch, out _);

[Benchmark]
public int AllLengthsToString()
{
    int sum = 0;
    foreach (uint value in _values)
    {
        sum += value.ToString().Length;
    }
    return sum;
}

[Benchmark]
public bool AllLengthsTryFormat()
{
    bool success = true;
    foreach (uint value in _values)
    {
        success |= value.TryFormat(_scratch, out _);
    }
    return success;
}
Author: stephentoub
Assignees: -
Labels:

area-System.Runtime, tenet-performance
Milestone: 8.0.0

@ghost ghost assigned stephentoub Oct 3, 2022
@stephentoub stephentoub changed the title Improve FormattingHelper.CountDigit(uint) Improve performance of FormattingHelper.CountDigits(uint) Oct 3, 2022
jkotas
jkotas reviewed Oct 3, 2022
View reviewed changes
src/libraries/System.Private.CoreLib/src/System/Buffers/Text/FormattingHelpers.CountDigits.cs
@@ -109,36 +111,52 @@ public static int CountDigits(ulong value)
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int CountDigits(uint value)
Copy link
Member

@jkotas jkotas Oct 3, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Update CountDigits(ulong value) above to take advantage of this?

Copy link

@mattzink mattzink Oct 3, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Update CountDigits(ulong value) above to take advantage of this?

FYI: There is a 64-bit version in the comments of Lemire's post

Copy link
Member Author

@stephentoub stephentoub Oct 3, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

FYI: There is a 64-bit version in the comments of Lemire's post

Which specifically? The variants I'd seen were only good up to a smaller number of bits, like 57.

Copy link
Member

@EgorBo EgorBo Oct 3, 2022 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I assume Jan meant

if (longValue <= uint.MaxValue)
    return CountDigits((uint)longValue);

?

Copy link
Member

@jkotas jkotas Oct 3, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

More like:

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int CountDigits(ulong value)
        {
            int digits;
            uint part;
            if (value >= 1_000_000_000)
            {
                if (part >= 1_000_000_000_000_000_000)
                {
                    part = (uint)(value / 1_000_000_000_000_000_000);
                    digits = 18;
                }
                else
                {
                    part = (uint)(value / 1_000_000_000);
                    digits = 9;
                }
            }
            else
            {
                part = (uint)value;
                digits = 0;
            }
            
            return digits + CountDigits(part);
        }

Copy link
Member Author

@stephentoub stephentoub Oct 4, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

More like

Yeah, that's what I was planning on doing, but I want to experiment.

@EgorBo EgorBo mentioned this pull request Oct 3, 2022
Closed
@stephentoub
Copy link
Member Author

stephentoub commented Oct 3, 2022

I'll merge this and follow-up on the 64-bit case.

@stephentoub stephentoub merged commit 1cce2df into dotnet:main Oct 3, 2022
@stephentoub stephentoub deleted the countdigits branch October 3, 2022 23:09
@stephentoub stephentoub mentioned this pull request Oct 6, 2022
Merged
This was referenced Oct 11, 2022
Closed
Closed
Closed
@EgorBo EgorBo mentioned this pull request Oct 13, 2022
Closed
@ghost ghost locked as resolved and limited conversation to collaborators Nov 3, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

@EgorBo EgorBo EgorBo left review comments

@jkotas jkotas jkotas left review comments

@tannergooding tannergooding tannergooding approved these changes

+1 more reviewer

@mattzink mattzink mattzink left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

@stephentoub stephentoub

Labels

area-System.Runtime tenet-performance Performance related issue

Projects

None yet

Milestone

8.0.0

Development

Successfully merging this pull request may close these issues.

5 participants

@stephentoub @EgorBo @mattzink @jkotas @tannergooding