Skip to content
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.

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

Possible shortcut for format_exact_opt in Grisu3 #110129

Closed
mazong1123 opened this issue Apr 10, 2023 · 1 comment · Fixed by #110389
Closed

Possible shortcut for format_exact_opt in Grisu3 #110129

mazong1123 opened this issue Apr 10, 2023 · 1 comment · Fixed by #110389
Labels
A-floating-point Area: Floating point numbers and arithmetic C-enhancement Category: An issue proposing an enhancement or a PR with one. I-slow Issue: Problems and improvements with respect to performance of generated code. T-libs Relevant to the library team, which will review and decide on the PR/issue.

Comments

@mazong1123
Copy link
Contributor

mazong1123 commented Apr 10, 2023

In the .NET implementation of Grisu3, there's a shortcut to jump out earlier when the fractionals or integrals cannot meet the determination of requested digits. This significantly improved the performance of converting floating number to string as it falls back even without starting trying the Grisu3 algorithm. This was originally added in this PR, and shipped along with all later .NET versions so it's proved working.

Below is the code snippet from current .NET repo:

                // We deviate from the original algorithm here and do some early checks to determine if we can satisfy requestedDigits.
                // If we determine that we can't, we exit early and avoid most of the heavy lifting that the algorithm otherwise does.
                //
                // When fractionals is zero, we can easily determine if integrals can satisfy requested digits:
                //      If requestedDigits >= 11, integrals is not able to exhaust the count by itself since 10^(11 -1) > uint.MaxValue >= integrals.
                //      If integrals < 10^(requestedDigits - 1), integrals cannot exhaust the count.
                //      Otherwise, integrals might be able to exhaust the count and we need to execute the rest of the code.
                if ((fractionals == 0) && ((requestedDigits >= 11) || (integrals < SmallPowersOfTen[requestedDigits - 1])))
                {
                    Debug.Assert(buffer[0] == '\0');
                    length = 0;
                    kappa = 0;
                    return false;
                }

I'm wondering do we consider apply the same shortcut just after vint and vfrac extracted at line 489 of grisu.rs?

@jyn514 jyn514 added I-slow Issue: Problems and improvements with respect to performance of generated code. C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs Relevant to the library team, which will review and decide on the PR/issue. A-floating-point Area: Floating point numbers and arithmetic labels Apr 10, 2023
@mazong1123
Copy link
Contributor Author

I'm going to prepare a PR later this week if no objection.

bors added a commit to rust-lang-ci/rust that referenced this issue Apr 25, 2023
…r=Mark-Simulacrum

Add shortcut for Grisu3 algorithm.

While Grisu3 is way more faster for most numbers compare to Dragon4, the fall back to Dragon4 procedure for certain numbers could cause some performance regressions compare to use Dragon4 directly. Mitigating the regression caused by falling back is important for a largely used core library.

In Grisu3 algorithm implementation, there's a shortcut to jump out earlier when the fractional or integrals cannot meet the requirement of requested digits. This could significantly improve the performance of converting floating number to string as it falls back even without starting trying the algorithm.

The original idea is from the [.NET implementation](https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Number.Grisu3.cs#L602-L615) and the code was originally added in [this PR](dotnet/coreclr#14646 (comment)). This shortcut has been shipped long time ago and has been proved working.

Fix rust-lang#110129
@bors bors closed this as completed in b0a85d6 Apr 25, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-floating-point Area: Floating point numbers and arithmetic C-enhancement Category: An issue proposing an enhancement or a PR with one. I-slow Issue: Problems and improvements with respect to performance of generated code. T-libs Relevant to the library team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants