Bug 147167 – stress/math-pow-with-constants.js fails in cloop

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Filip Pizlo]

stress/math-pow-with-constants.js.default: Exception: Error: exponentIsIntegerConstant(2.1) should be 34135823067412.42, was = 34135823067412.465
stress/math-pow-with-constants.js.default: ERROR: Unexpected exit code: 3

[Mark Lam]

Some facts:
The CLoop and ASM llint (useJIT=0) both yield 34135823067412.465.
The Mac Calculator yields 34135823067412.46.
With the JIT enabled, JSC yields 34135823067412.42.
Chrome and Firefox yields 34135823067412.42.

[Mark Lam]

For the record, a C++ test function to call pow(2.1, 42) and printed with %20.3f formatting also yields 34135823067412.465.

[Basile Clement]

(In reply to comment #1)
> Some facts:
> The CLoop and ASM llint (useJIT=0) both yield 34135823067412.465.
> The Mac Calculator yields 34135823067412.46.
> With the JIT enabled, JSC yields 34135823067412.42.
> Chrome and Firefox yields 34135823067412.42.

(In reply to comment #2)
> For the record, a C++ test function to call pow(2.1, 42) and printed with
> %20.3f formatting also yields 34135823067412.465.

Could we just be doing some kind of fast path computation when JITting Math.pow that is invalid in floating point land?

[Yusuke Suzuki]

I guess this is due to x87 floating point width (80bit).
If I'm saying something wrong, please ignore it :)

[Filip Pizlo]

(In reply to comment #4)
> I guess this is due to x87 floating point width (80bit).
> If I'm saying something wrong, please ignore it :)

If this is 64bit, then we wouldn't be using x87. More generally, it would be a bug to implement JS floating point using x87 and I don't think we ever do that.

[Filip Pizlo]

(In reply to comment #3)
> (In reply to comment #1)
> > Some facts:
> > The CLoop and ASM llint (useJIT=0) both yield 34135823067412.465.
> > The Mac Calculator yields 34135823067412.46.
> > With the JIT enabled, JSC yields 34135823067412.42.
> > Chrome and Firefox yields 34135823067412.42.
> 
> (In reply to comment #2)
> > For the record, a C++ test function to call pow(2.1, 42) and printed with
> > %20.3f formatting also yields 34135823067412.465.
> 
> Could we just be doing some kind of fast path computation when JITting
> Math.pow that is invalid in floating point land?

thr opposite might also be true. :-) the JIT could be calling variant of pow that is more compliant. 

I think that it's okto fix this by making the C++ code agree with the JIT or vice versa. The spec is very permissive about what pow returns and we really just want to have internal consistency in our engine.

[Basile Clement]

(In reply to comment #6)
> (In reply to comment #3)
> > (In reply to comment #1)
> > > Some facts:
> > > The CLoop and ASM llint (useJIT=0) both yield 34135823067412.465.
> > > The Mac Calculator yields 34135823067412.46.
> > > With the JIT enabled, JSC yields 34135823067412.42.
> > > Chrome and Firefox yields 34135823067412.42.
> > 
> > (In reply to comment #2)
> > > For the record, a C++ test function to call pow(2.1, 42) and printed with
> > > %20.3f formatting also yields 34135823067412.465.
> > 
> > Could we just be doing some kind of fast path computation when JITting
> > Math.pow that is invalid in floating point land?
> 
> thr opposite might also be true. :-) the JIT could be calling variant of pow
> that is more compliant. 
> 
> I think that it's okto fix this by making the C++ code agree with the JIT or
> vice versa. The spec is very permissive about what pow returns and we really
> just want to have internal consistency in our engine.

Just checked; JIT code is doing a fast exponentiation when the exponent is an integer but LLInt is not.

[Mark Lam]

More facts:

    double result = 1;
    double v = 2.1;
    for (int i = 0; i < 42; i++)
        result *= v;
    printf("   2.1 * ... * 2.1 (42 times) = %f\n", result);

yields:
   2.1 * ... * 2.1 (42 times) = 34135823067412.472656

The powThunkGenerator algorithm:

    double result = 1;
    double v = 2.1;
    int exp = 42;
    do {
        if (exp & 1)
            result *= v;
        result *= result;
        exp = exp >> 1;
    } while (exp);
    printf("   powThunkGenerator algo(2.1, 42) = %f\n", result);

yields:
   powThunkGenerator algo(2.1, 42) = 34135823067412.433594

Neither of these are consistent with the 34135823067412.464844 returned by the C pow(), nor the 34135823067412.42 returned by the JITted code.

[Basile Clement]

(In reply to comment #8)
> More facts:
> 
>     double result = 1;
>     double v = 2.1;
>     for (int i = 0; i < 42; i++)
>         result *= v;
>     printf("   2.1 * ... * 2.1 (42 times) = %f\n", result);
> 
> yields:
>    2.1 * ... * 2.1 (42 times) = 34135823067412.472656
> 
> The powThunkGenerator algorithm:
> 
>     double result = 1;
>     double v = 2.1;
>     int exp = 42;
>     do {
>         if (exp & 1)
>             result *= v;
>         result *= result;

This should be v *= v, and just happen to (almost) work for 42 because when repeatedly divided by 2 we get 42 -> 21 -> 10 -> 5 -> 2 -> 1 which is an alternative sequence of even and odd numbers, so the odd step does the multiplication the even step should have been doing and all is good - for real numbers. Using v *= v instead gives the same result as JITted code, preparing a patch.

>         exp = exp >> 1;
>     } while (exp);
>     printf("   powThunkGenerator algo(2.1, 42) = %f\n", result);
> 
> yields:
>    powThunkGenerator algo(2.1, 42) = 34135823067412.433594
> 
> Neither of these are consistent with the 34135823067412.464844 returned by
> the C pow(), nor the 34135823067412.42 returned by the JITted code.

[Basile Clement]

We currently have different ways of calling Math.pow:

1) In the LLInt when the JIT is disabled
2) In the LLInt with the JIT enabled
3) In the baseline JIT
4) Through constant folding in the DFG or FTL
5) Without constant folding in the DFG
6) Without constant folding in the FTL

Cases 1 and 4 are calling operationMathPow, which is essentially a call to std::pow.

Cases 2 and 3 use the powThunkGenerator from jit/ThunkGenerators.cpp, which performs fast exponentiation if the exponent is represented as a boxed int32 value, and falls back to operationMathPow otherwise.

Cases 5 and 6 have their own functionally identical implementations that performs fast exponentiation if the exponent can be converted to an int32 value, and falls back to operationMathPow otherwise (case 6 falling back to the LLVM pow intrinsic).

Since the fast exponentiation can yield different outputs than the standard pow() function, we can thus get different results depending on the representation of arguments and the tier we are on.

I see two valid fixes here:

 - We don't care. Floating point arithmetic is never exact anyway, and the results are still close. In this case, we shouldn't compare the results of Math.pow for equality in our tests however, and the fix would be to change the math-pow-with-constants test to check for closeness instead of equality.

 - We want Math.pow to give an illusion of consistency by making Math.pow deterministic on a given platform.

I think the second option is more desirable, as long as that doesn't impact too much on performances. I have a patch for always taking the fast exponentiation path when the exponent is convertible to an int32, I'll run the benchmarks tomorrow to see how it goes performance-wise.

[Basile Clement]

Created attachment 257459 [details]
Benchmark results

[Basile Clement]

Created attachment 257460 [details]
Patch

[Basile Clement]

(In reply to comment #11)
> Created attachment 257459 [details]
> Benchmark results

This is essentially perf neutral except for:

   math-partial-sums                                  7.0537+-0.0603     !      7.5745+-0.0369        ! definitely 1.0738x slower

   math-partial-sums                                696.1862+-8.3549     !    749.4553+-3.7285        ! definitely 1.0765x slower

in SunSpider and LongSpider, which is weird because all of the calls to Math.pow in that benchmark should be using the fast paths AFAICT.

[Geoffrey Garen]

Comment on attachment 257460 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=257460&action=review

> Source/JavaScriptCore/ChangeLog:12
> +        Baseline JIT, DFG and FTL are using a fast exponentiation fast path
> +        when computing Math.pow() with an integer exponent that is not taken in
> +        the LLInt (or the DFG abstract interpreter). This leads to the result
> +        of pow changing depending on the compilation tier or the fact that
> +        constant propagation kicks in, which is undesirable.

Why is it OK for fast exponentiation to produce a result that a different from slow exponentiation? Isn't that a bug in fast exponentiation? Under what conditions is the result different?

[Basile Clement]

(In reply to comment #14)
> Comment on attachment 257460 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=257460&action=review
> 
> > Source/JavaScriptCore/ChangeLog:12
> > +        Baseline JIT, DFG and FTL are using a fast exponentiation fast path
> > +        when computing Math.pow() with an integer exponent that is not taken in
> > +        the LLInt (or the DFG abstract interpreter). This leads to the result
> > +        of pow changing depending on the compilation tier or the fact that
> > +        constant propagation kicks in, which is undesirable.
> 
> Why is it OK for fast exponentiation to produce a result that a different
> from slow exponentiation? Isn't that a bug in fast exponentiation? Under
> what conditions is the result different?

The fast path is using fast exponentiation[0] when the exponent is an integer, which would yield the same result (except faster) than the usual std::pow() function in a perfect and ideal mathematical world. But, we are using floating point math, and thus these two ways of computing pow() yield different approximations of the exponentiation (which can't usually be represented exactly as a double anyway).

Note that the ES6 spec[1] (as well as IEEE 754) only says that Math.pow(x, y) should return "an implementation-dependent approximation to the result of raising x to the power y." It is perfectly fine for us to choose that approximation to be the result of the fast exponentiation algorithm when the exponent is an integer, and the result of std::pow() otherwise - we just should be consistent in our choice.


0: https://en.wikipedia.org/wiki/Exponentiation_by_squaring
1: http://www.ecma-international.org/ecma-262/6.0/index.html#sec-math.pow

[Basile Clement]

(In reply to comment #15)
> (In reply to comment #14)
> > Comment on attachment 257460 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=257460&action=review
> > 
> > > Source/JavaScriptCore/ChangeLog:12
> > > +        Baseline JIT, DFG and FTL are using a fast exponentiation fast path
> > > +        when computing Math.pow() with an integer exponent that is not taken in
> > > +        the LLInt (or the DFG abstract interpreter). This leads to the result
> > > +        of pow changing depending on the compilation tier or the fact that
> > > +        constant propagation kicks in, which is undesirable.
> > 
> > Why is it OK for fast exponentiation to produce a result that a different
> > from slow exponentiation? Isn't that a bug in fast exponentiation? Under
> > what conditions is the result different?
> 
> The fast path is using fast exponentiation[0] when the exponent is an
> integer, which would yield the same result (except faster) than the usual
> std::pow() function in a perfect and ideal mathematical world. But, we are
> using floating point math, and thus these two ways of computing pow() yield
> different approximations of the exponentiation (which can't usually be
> represented exactly as a double anyway).
> 
> Note that the ES6 spec[1] (as well as IEEE 754) only says that Math.pow(x,
> y) should return "an implementation-dependent approximation to the result of
> raising x to the power y." It is perfectly fine for us to choose that
> approximation to be the result of the fast exponentiation algorithm when the
> exponent is an integer, and the result of std::pow() otherwise - we just
> should be consistent in our choice.

Just to be clear - the spec mandates particular values for the infinity, zero and NaN cases, with which the fast exponentiation algorithm is consistent.

[Filip Pizlo]

Comment on attachment 257460 [details]
Patch

LGTM.

[Geoffrey Garen]

Comment on attachment 257460 [details]
Patch

r=me

Thanks for the explanation.

[Basile Clement]

Committed r187497: <http://trac.webkit.org/changeset/187497>

[Simon Fraser (smfr)]

This caused 6 JSC tests to fail on Windows:
https://build.webkit.org/builders/Apple%20Win%207%20Debug%20%28Tests%29/builds/67036/steps/jscore-test/logs/stdio

[Basile Clement]

(In reply to comment #20)
> This caused 6 JSC tests to fail on Windows:
> https://build.webkit.org/builders/Apple%20Win%207%20Debug%20%28Tests%29/
> builds/67036/steps/jscore-test/logs/stdio

That is the test added in this patch timing out on debug builds. I'll lower the number of test iterations by 10x, hopefully that should be enough to not time out.

[Basile Clement]

(In reply to comment #21)
> (In reply to comment #20)
> > This caused 6 JSC tests to fail on Windows:
> > https://build.webkit.org/builders/Apple%20Win%207%20Debug%20%28Tests%29/
> > builds/67036/steps/jscore-test/logs/stdio
> 
> That is the test added in this patch timing out on debug builds. I'll lower
> the number of test iterations by 10x, hopefully that should be enough to not
> time out.

Hopefully fixed by http://trac.webkit.org/changeset/187548

[Basile Clement]

This test is now failing on some platforms due to not always being compiled up to the fourth tier. I skipped it temporarily in http://trac.webkit.org/changeset/187551 while I figure out how to simplify the test while still testing what it should test.