GeezerVison

Overview:

Grisu3 is much faster (some numbers become almost 9 times faster, for instance, -1.79769313486232E+308's runtime change: 237.492 -> 28.660 ) than Dragon4. But when a number fails in Grisu3, we have to switch to Dragon4, obviously it is slower than the sole Dragon4 implementation in this case. For instance, comparing the test result of perftest.DoubleToStringTest.ToStringWithFormat(format: "G17", number: 250, innerIterations: 2000000). Because 250 in 17 digits precision fails in Grisu3, it becomes much slower in the new implementation.

Following are the benchmark:

Average runtime comparison:

Following are the details of each performance test result:

Before change (With only Dragon4):

After change (Grisu3 + Dragon4):

Above results were generated by the code: https://github.com/dotnet/corefx/blob/master/src/System.Runtime/tests/Performance/Perf.Double.cs

@tarekgh @tannergooding @jkotas PTAL.

Because 250 in 17 digits precision fails in Grisu3, it becomes much slower in the new implementation.

Do we know how much slower when we hit such cases? is there a way can detect such numbers early and call Dragon directly? I am trying to find a mitigation for the cases we are slower here.

@dotnet-bot test Windows_NT x64 corefx_baseline
@dotnet-bot test Ubuntu x64 corefx_baseline

Do we know how much slower when we hit such cases?

Following are the test results failed in Grisu3. The minimum regression is around 4%, the maximum regression is around 22%. The regression depends on the requested precision. We can exit Grisu3 quicker when requested precision smaller (If we can exhaust all the requested digit count then we success in Grisu3).

is there a way can detect such numbers early and call Dragon directly?

AFAIK we do not have an existing algorithm to do this (except the check algorithm in Grisu3 itself, which I'm using in the implementation). I may try to find a way to jump to Dragon4 earlier but we may need to set a bottom line for this - what's the acceptable regression rate for those numbers fail in Grisu3?

Note that even if we fall back to Dragon4, we still have a great performance improvement compare to current (2.0.0) implementation.

BTW, the CI failure seems caused by some jit compile error, which should not be introduced by my code.

but we may need to set a bottom line for this - what's the acceptable regression rate for those numbers fail in Grisu3?

I care about the common scenarios (e.g. Double.ToString() and Double.ToString("R")). from your data, we'll have around 14% regression with "E" and around 4% of "R". what is the regression with "G"? I think the regression with "R" is acceptable. if the regression with "G" is small too (around 5%) that will be acceptable. Also if the regression occurs with small set/ranges of numbers, that can mitigate the regression too.

In general, I am seeing the perf gain with Grisu3 is encouraging and worth to have it.

BTW, the CI failure seems caused by some jit compile error, which should not be introduced by my code.

right I looked early at the failures and I am not seeing it related to your changes

@tarekgh Following are the test for the failing numbers. I tested two numbers 1 and 250:

The regression of different numbers are variety, basically depends one the digits of numbers and the requested precision. We need to have a tradeoff - is it worthwhile to make 99.5% numbers 90% quicker but sacrifice performance of the left 0.5% numbers (up to 24% regression).

Meanwhile, I'm trying to mitigate the regression. Currently I don't have any good approach yet. Cache the failed numbers and precision in a limited memory space may be an easy way to go (e.g., a micro LRU cache system). Or we need to design a new algorithm for pre-checking the numbers specifically other than Grisu3's self-checking during producing digits. Or combine the above two approaches.

is it worthwhile to make 99.5% numbers 90% quicker but sacrifice performance of the left 0.5% numbers (up to 24% regression).

if we are sure that the failing numbers are in the range of 0.5% then I think it is worth it.

Cache the failed numbers and precision in a limited memory space may be an easy way to go (e.g., a micro LRU cache system).

I think we don't need to create that complication. if we don't have a simple way to check if the number will fail, then we shouldn't add any complexity and we may just accept the regression.

@mazong1123, @tarekgh: I still think it would be useful to know where these failing numbers fall.

Floating-point values that are normalized between -1.0 and +1.0 are fairly common in a number of different applications. If a large portion of the failing 0.5% (which is still 92.2 Quadrillion values) fall in that range, than it may actually be more common than the percentage would lead you to believe.

@tannergooding Sure I'm going to collect the number range of 0.5% in the next step. The paper didn't tell us this information. I need to collect it and prove it by myself so it may take sometime. But I agree it's worth doing it.

@tannergooding @tarekgh I've spent sometime to investigate what kind of numbers will fail in Grisu3 with fixed precision. And here is the brief result:

There're 3 factors can impact the result:

• The requested precision: count.
• The integral parts of the input double value: p1.
• The fractional parts of the input double value: p2.

The algorithm is first to produce digits according to p1. If the count can be exhausted during or after this process, that's good, we can use Grisu3 for this value. If there're left count to generate, we go to p2. If we can exhaust left count while producing digits of p2, we success in Grisu3 either. Otherwise, we fail in Grisu3.

We're easy to generate the numbers fail in Grisu3 - just make the precision large enough, and p1 and p2 small enough.

For example, let's say count is 17 (which is our round-trip precision), the input value is 1 (the p2 is 0, obviously). In fact we cannot generate 17 digits when producing the integral parts (p1), and since p2 is 0 which can generate nothing, we'll fail in Grisu3.

However, 1.1 with 17 digits precision can success because the fractional part (p2) is large enough so that we can generate the left count completely.

So you can imagine, in 17 digits precision. a large set of double numbers without factional parts will fail in Grisu3 (1, 2, ...100, 1000 will fail, 1.1, 1.2, 2.1 will success). Of cause, if the requested precision is small enough, those numbers can success in Grisu3 - For instance, 1 can success in Grisu3 with 5 digits precision.

Also, I think the 0.5% miss is probably for free format - generate for shortest length, not for fixed format, which is our case. I didn't do comparing test but you can think of it - I can give a very large requested count, and all the double values without fractional part will fail, it definitely does not limit to 0.5% seems like it's still around 99.5%.

I'm collecting the hit rate for all double numbers for 17 digits precision. Hope this can give us a brief idea. I'd like to collect the hit rate from 1 digits precision to 30 digits precision later on.

I've calculated to 109500000000 by now and the hit rate is 99.27%. My machine does not have that power to calculate all double numbers I guess:

The complete Grisu3 hit rate for precision count 17 in 109390000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109400000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109410000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109420000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109430000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109440000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109450000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109460000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109470000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109480000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109490000000 numbers is 99.27
The complete Grisu3 hit rate for precision count 17 in 109500000000 numbers is 99.27

Wrap up:

• The Grisu3 is applicable for 99.27%+ double numbers even for fixed format. (haven't finished the validation, but it should be close to 99.5% - claimed in the paper).
• The fail numbers are not particularly subnormals or NaNs etc. It depends on the required precision, its integral and fractional parts.
• The numbers success in Grisu3 have nearly 90% performance gain, whereas those fail in Grisu3 have up to 24% regression, compare to sole Dragon4.

For my opinion, it's worth having it. Not only for the 90% performance gain for 99.5% numbers, but also because it has been widely adopted in other frameworks/libraries (V8, Rust, Go).

Additionally, Python using Errol3, which claims have improvement from Grisu3, but there're some issues of this algorithm so I still think Grisu3 is a better choice for now. And maybe next time we can upgrade it to Errol3 - well, that's another topic.

@tarekgh @tannergooding thoughts?

@mazong1123 does Grisu3 always succeed with the lower precisions? I mean, you mentioned before it always fails with 17 digit precisions with the numbers doesn't have fractions. Is it true for 15-digits precisions?

What I am trying to get into is if we can have Grisu3 is on by default when lower precision is used and we can use Dragon for higher precision.

I am inclining to have Grisu3 enabled but in same time just want to reduce the regression in the failed case.

does Grisu3 always succeed with the lower precisions? I mean, you mentioned before it always fails with 17 digit precisions with the numbers doesn't have fractions. Is it true for 15-digits precisions?

Depends on the number, it will fail in 15-digits precisions either. For example, 10000000000000000000000.0 fail in both 17 and 15 digits precisions, but can be success in digits 1 ~ 3 precisions.

if we can have Grisu3 is on by default when lower precision is used and we can use Dragon for higher precision.

Unfortunately, it is not linear. For example, 10000000000000000000000.0 will fail in digits 5 precision, but 1000000000000000000000.0 (with 1 zero less) and 100000000000000000000000.0(with 1 additional zero) will both success in digits 5. Although the lower precision has greater chance to be success, we cannot compute the success rate simply relies on the input number's digit length.

To estimate the number being success in Grisu3 is part of Errol3's job. Although Errol3 can always success, it is slower than Grisu3 at sometime. See the paper: https://cseweb.ucsd.edu/~mandrysc/pub/dtoa.pdf

One possible optimization I think is to extract the error analysis from Errol3 and apply to Grisu3. Someone had the same idea: https://news.ycombinator.com/item?id=10922347

@mazong1123 thanks for the details, it is very helpful.

Is it possible we detect the numbers that don't have fraction part and then use Dragon? do you think this will reduce the possibilities of having Grisu3 to fail when it is used? As you see, I am trying to reduce the possibility of regressions as much as possible.

Is it possible we detect the numbers that don't have fraction part and then use Dragon?

@tarekgh Yes I'm trying to do that. The best is to extract the error analysis (determine whether the number will fail in Grisu3 quickly) from Errol3 and apply to Grisu3. That should increase the success rate from 99.5% to 99.95% in theory.

I finally have time to work on this issue. I found it's too complicated to extract the error analysis from Errorl and apply it to Grisu3. So I just made a shortcut in DigitGen: When p2 (fractional part) is 0, predicate if p1 is good to produce the numbers in requested digit count. I'll run the micro-benchmark to get the measurement result this week.

    if (p2 == 0 && (count >= 12 || p1 < GetPowerOfTen(count - 1)))
    {
        return false;
    }

@tarekgh good news. The shortcut does mitigate the regression. Please see following results for Grisu3's failing cases.

The shortcut does little affect for other success cases so I think this optimization should be good to go.

@mazong1123 I looked at the changes and it looks good to me. let's wait for @tannergooding review and then we can start consulting the legal again regarding the usage of Grisu algorithm.

I did a quick walkthrough of the new code and the paper and this looks to be generally correct.

I still want to dig into this more in depth, but we can probably start the other process while I do that.

@dotnet-bot test Ubuntu x64 Checked Build and Test (Jit - CoreFx)

Seems like I'm not able to restart the test Ubuntu x64 Checked Build and Test (Jit - CoreFx). Hmm... I'll focus on the review comments first.

@dotnet-bot test Ubuntu x64 Checked corefx_baseline

CC @joperezr

I have asked @joperezr to start following up with the LCA so we can proceed with the changes. meanwhile, @tannergooding can finish his code review so we'll be ready.

I have talked to LCA on our side and we are good to go to take this as long as @tannergooding approves the implementation, which looks good to me.

It looks correct to me as well, having dug more in depth.

I'd like to see the requested comments/documentation added to the source code and the minor error with the 1 / log2(10) constant resolved first (#14646 (comment)).

@mazong1123 could you please address the remaining comments on the code review so we can proceed to merge it?

Great! Will address the code review comments within next week :)

@mazong1123 did you have a chance to finish this one?

@tarekgh Will do this weekend. Sorry for the late. Busy for onboarding the new team...

@tarekgh @tannergooding I just updated the code according to the review comments. Please take a look. Thanks!

@tannergooding if you are ok with the latest changes, we can merge this one.

@joperezr please follow up if there is any license docs need to be updated.

Thanks @mazong1123 for getting this done.