Content-Length: 413837 | pFad | https://github.com/dotnet/runtime/pull/76519

15 Improve performance of FormattingHelper.CountDigits(uint) by stephentoub · Pull Request #76519 · dotnet/runtime · GitHub
Skip to content

Improve performance of FormattingHelper.CountDigits(uint) #76519

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
Oct 3, 2022
Merged

Improve performance of FormattingHelper.CountDigits(uint) #76519

merged 1 commit into from
Oct 3, 2022

Conversation

stephentoub
Copy link
Member

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

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

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

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

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

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

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

@mattzink mattzink mattzink left review comments

@jkotas jkotas jkotas left review comments

@tannergooding tannergooding tannergooding approved these changes

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








ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: https://github.com/dotnet/runtime/pull/76519

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy