Implement Math.hypot

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Tibor Mészáros]

In the ES6 standard there is the Math.hypot specification which is currently not implemented in the JavaScriptCore. This could be a good feature implementation.

[Tibor Mészáros]

Created attachment 225476 [details]
Patch

This patch will add support for Math.hypot, and add tests for it.

[Darin Adler]

Comment on attachment 225476 [details]
Patch

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

There is insufficient test coverage for special case arguments in combinations orders (0, NaN) (NAN, 0), and for exception and side effect behavior of the function’s argument evaluation (valueOf functions on the arguments passed in). Existing math functions don’t have that level of exception/side effect test coverage, but they should.

> Source/JavaScriptCore/runtime/MathObject.cpp:186
> +    double* args = new double[argsCount];

Doing heap allocation here is bad for a variety of reasons:

1) This patch doesn’t include a delete, so it leaks.
2) It’s costly to do a heap allocation every time we evaluate this function, and pointless for small argument counts.
3) This uses new, but we prefer to use fastNew, which uses a more efficient version of malloc on some WebKit configurations.

If we really do need to copy all the arguments into a vector, then we should use WebKit’s Vector. It’s something like this:

    Vector<double, 16> args(argsCount);

Then we’ll only do heap allocation if the number of arguments is more than 16.

> Source/JavaScriptCore/runtime/MathObject.cpp:189
> +    for (unsigned k = 0; k < argsCount; ++k) {

Why "k" when we use "-" everywhere else?

> Source/JavaScriptCore/runtime/MathObject.cpp:192
> +        if (argsCount == 1 && (arg == -0 || arg == +0))
> +            return JSValue::encode(jsNumber(0));

For the number 0 we are returning immediately, but for infinity and NaN we are waiting until the end. Is that right? I don’t see test coverage for this difference.

Are you sure that "arg == -0 || arg == +0" does what you think it does in C/IEEE numerics? I’m pretty sure that both sides of the "||" will be true for either type of zero.

> Source/JavaScriptCore/runtime/MathObject.cpp:194
> +        if (std::isinf(arg))
> +            inf = true;

Do we really need a special case for infinity? Does the algorithm and IEEE math give us the right value without a special case? If so, we should just let it do that.

> Source/JavaScriptCore/runtime/MathObject.cpp:196
> +        else if (std::isnan(arg))
> +            nan = true;

Do we really need a special case for NaN? Does the algorithm and IEEE math give us the right value without a special case? If so, we should just let it do that.

> Source/JavaScriptCore/runtime/MathObject.cpp:207
> +        return JSValue::encode(jsDoubleNumber(QNaN));

This should be using jsNaN(), not jsDoubleNumber().

> Source/JavaScriptCore/runtime/MathObject.cpp:210
> +    if (max)
> +        max = 1;

What does this mean? We looped through all the arguments just to compute max, and then we convert it to either 0 or 1? Looks wrong to me.

> Source/JavaScriptCore/runtime/MathObject.cpp:212
> +    double comp = 0;

Do we really need to use the non-word "comp" for this argument? Is this a term of art that needs to be abbreviated?

> Source/JavaScriptCore/runtime/MathObject.cpp:216
> +        double prelim = sum + summand;

Same question about "prelim".

[Darin Adler]

Comment on attachment 225476 [details]
Patch

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

>> Source/JavaScriptCore/runtime/MathObject.cpp:189
>> +    for (unsigned k = 0; k < argsCount; ++k) {
> 
> Why "k" when we use "-" everywhere else?

I meant: Why "k" when we use "i" elsewhere in WebKit code for this?

[Tibor Mészáros]

(In reply to comment #3)
> (From update of attachment 225476 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=225476&action=review
> 
> >> Source/JavaScriptCore/runtime/MathObject.cpp:189
> >> +    for (unsigned k = 0; k < argsCount; ++k) {
> > 
> > Why "k" when we use "-" everywhere else?
> 
> I meant: Why "k" when we use "i" elsewhere in WebKit code for this?

Hi!

Thanks for the detailed review, I'm going to create a new patch today, to cover your remarks.

[Tibor Mészáros]

Most of your remarks has been fixed in this new patch, please review this too. Thanks

[Tibor Mészáros]

Created attachment 225660 [details]
Patch v2

[Build Bot]

Comment on attachment 225660 [details]
Patch v2

Attachment 225660 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/6609482155032576

New failing tests:
js/math.html
js/Object-getOwnPropertyNames.html

[Build Bot]

Created attachment 225669 [details]
Archive of layout-test-results from webkit-ews-07 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-07  Port: mac-mountainlion  Platform: Mac OS X 10.8.5

[Build Bot]

Comment on attachment 225660 [details]
Patch v2

Attachment 225660 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/5951759017050112

New failing tests:
js/math.html
js/Object-getOwnPropertyNames.html

[Build Bot]

Created attachment 225670 [details]
Archive of layout-test-results from webkit-ews-01 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-01  Port: mac-mountainlion  Platform: Mac OS X 10.8.5

[Build Bot]

Comment on attachment 225660 [details]
Patch v2

Attachment 225660 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/4873585592107008

New failing tests:
js/math.html
js/Object-getOwnPropertyNames.html

[Build Bot]

Created attachment 225672 [details]
Archive of layout-test-results from webkit-ews-11 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-11  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.5

[Tibor Mészáros]

Created attachment 225766 [details]
Patch v3

Support for mac.

[Build Bot]

Comment on attachment 225766 [details]
Patch v3

Attachment 225766 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/4580807066779648

New failing tests:
js/math.html

[Build Bot]

Created attachment 225769 [details]
Archive of layout-test-results from webkit-ews-16 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-16  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.5

[Tibor Mészáros]

Created attachment 225778 [details]
Patch v4

The problems with the math-expected.txt has been fixed.

[Tibor Mészáros]

Created attachment 225779 [details]
Patch v5

[Build Bot]

Comment on attachment 225779 [details]
Patch v5

Attachment 225779 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/5346863876145152

New failing tests:
js/math.html

[Build Bot]

Created attachment 225782 [details]
Archive of layout-test-results from webkit-ews-10 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-10  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.5

[Tibor Mészáros]

Created attachment 225783 [details]
Patch v6

Fixed the difference between expected and actual results.

[Darin Adler]

Comment on attachment 225783 [details]
Patch v6

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

This is OK, but needs some work. I am going to say review+ but I would appreciate an improved patch that addresses the exception-correctness and multiple-evaluation issues, and removes some of the unneeded code that is included here.

> Source/JavaScriptCore/runtime/MathObject.cpp:186
> +    double sum = 0;
> +    double compensation = 0;

These two variables should be declared down below right at the point where we do the summation algorithm rather than at the top of the function.

> Source/JavaScriptCore/runtime/MathObject.cpp:187
> +    bool nan = false;

No need for a separate nan boolean. The code should just set max to NaN. We don’t need to optimize NaN cases, just make sure they work correctly.

> Source/JavaScriptCore/runtime/MathObject.cpp:189
> +    if (!argsCount)
> +        return JSValue::encode(jsNumber(0));

Why this special case? The function already handles zero arguments correctly without a special case, and I see no need to optimize this for speed. Please remove this code unless it’s needed to get a correct result.

> Source/JavaScriptCore/runtime/MathObject.cpp:193
> +        if (argsCount == 1 && (arg == 0.0 || (arg+0.0) == 0.0 ))
> +            return JSValue::encode(jsNumber(0));

This is not the right way to check for both positive and negative zero. The IEEE floating point standard mandates that negative and positive zero both compare as equal so this should work:

    if (argsCount == 1 && !arg)

But also, why do we need this special case at all? I would imagine the algorithm would yield zero without a special case. If we do need a special case, I suggest we put it outside the loop, and check max rather than checking the argument directly.

> Source/JavaScriptCore/runtime/MathObject.cpp:195
> +        if (std::isinf(arg))
> +            return JSValue::encode(jsDoubleNumber(+std::numeric_limits<double>::infinity()));

Do we need this special case? If we remove this, do we still correctly get a result of positive infinity? If so, please remove this code.

> Source/JavaScriptCore/runtime/MathObject.cpp:197
> +        if (std::isnan(arg))
> +            nan = true;

Do we need this special case? If we remove this, do we still correctly get a result of NaN? If so, please remove this code.

> Source/JavaScriptCore/runtime/MathObject.cpp:199
> +        else if (fabs(arg)>max)
> +            max = fabs(arg);

It would be better to write this using std::max:

    max = std::max(fabs(arg), max);

I believe that this will yield NaN if arg is NaN, although of course we should test to be sure that works correctly. If we were keeping this code we’d need to fix the formatting. WebKit coding style puts spaces around the ">" operator that are missing here. I also am not sure the compiler will optimize the two calls to fabs into only a single call, so we could consider using a local variable.

> Source/JavaScriptCore/runtime/MathObject.cpp:205
> +    // Kahan summation algorithm significantly reduces the numerical error in the total obtained.

Do we have tests that demonstrate the reduced numerical error, which would detect the poorer results we would see if we did simpler summation?

> Source/JavaScriptCore/runtime/MathObject.cpp:207
> +        double arg = exec->argument(i).toNumber(exec) / max;

I’m not sure that "arg" is quite the right name here, since this is "arg / max". I might call this scaledArgument.

It’s not correct for this function to evaluate all the arguments twice. Programs can observe the side effect of an argument being evaluated, and can detect if it’s done twice. The algorithm must do it only once. So we need to store the argument values somewhere so we don’t have to compute them again. An easy way to do that is to use a Vector<double, 32>, which should be relatively high performance.

This function needs to exit early if we get an exception when calling toNumber.

We should create tests that cover both these issues: That each valueOf function is called only once, not twice, and that no additional functions are called after a prior function throws an exception. We should test other math functions too; I’m pretty sure some of them are handling these issues incorrectly.

[Darin Adler]

Comment on attachment 225783 [details]
Patch v6

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

> Source/JavaScriptCore/runtime/MathObject.cpp:191
> +        double arg = exec->argument(i).toNumber(exec);

This should be calling uncheckedArgument instead of argument. The uncheckedArgument function should be used any time we can guarantee the index is < the argument count, and here we can indeed guarantee that.

[Tibor Mészáros]

Created attachment 226912 [details]
Patch v7

Argument function has been changed to uncheckedArgument.

[Tibor Mészáros]

Created attachment 226924 [details]
Patch v8

Updated to match with Darin's opinion.

[Tibor Mészáros]

(In reply to comment #21)
> (From update of attachment 225783 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=225783&action=review
> 
> This is OK, but needs some work. I am going to say review+ but I would appreciate an improved patch that addresses the exception-correctness and multiple-evaluation issues, and removes some of the unneeded code that is included here.
> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:186
> > +    double sum = 0;
> > +    double compensation = 0;
> 
> These two variables should be declared down below right at the point where we do the summation algorithm rather than at the top of the function.

- The declaration has been moved to down.

> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:187
> > +    bool nan = false;
> 
> No need for a separate nan boolean. The code should just set max to NaN. We don’t need to optimize NaN cases, just make sure they work correctly.

- removed

> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:189
> > +    if (!argsCount)
> > +        return JSValue::encode(jsNumber(0));
> 
> Why this special case? The function already handles zero arguments correctly without a special case, and I see no need to optimize this for speed. Please remove this code unless it’s needed to get a correct result.

- removed

> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:193
> > +        if (argsCount == 1 && (arg == 0.0 || (arg+0.0) == 0.0 ))
> > +            return JSValue::encode(jsNumber(0));
> 
> This is not the right way to check for both positive and negative zero. The IEEE floating point standard mandates that negative and positive zero both compare as equal so this should work:
> 
>     if (argsCount == 1 && !arg)
> 
> But also, why do we need this special case at all? I would imagine the algorithm would yield zero without a special case. If we do need a special case, I suggest we put it outside the loop, and check max rather than checking the argument directly.

- removed

> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:195
> > +        if (std::isinf(arg))
> > +            return JSValue::encode(jsDoubleNumber(+std::numeric_limits<double>::infinity()));
> 
> Do we need this special case? If we remove this, do we still correctly get a result of positive infinity? If so, please remove this code.

- Yes, we need this case, because if isn't there, the result will be NaN, instead of Infinity, if there were a NaN before.

> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:197
> > +        if (std::isnan(arg))
> > +            nan = true;
> 
> Do we need this special case? If we remove this, do we still correctly get a result of NaN? If so, please remove this code.

- removed

> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:199
> > +        else if (fabs(arg)>max)
> > +            max = fabs(arg);
> 
> It would be better to write this using std::max:
> 
>     max = std::max(fabs(arg), max);
> 
> I believe that this will yield NaN if arg is NaN, although of course we should test to be sure that works correctly. If we were keeping this code we’d need to fix the formatting. WebKit coding style puts spaces around the ">" operator that are missing here. I also am not sure the compiler will optimize the two calls to fabs into only a single call, so we could consider using a local variable.

- changed to this 

> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:205
> > +    // Kahan summation algorithm significantly reduces the numerical error in the total obtained.
> 
> Do we have tests that demonstrate the reduced numerical error, which would detect the poorer results we would see if we did simpler summation?
> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:207
> > +        double arg = exec->argument(i).toNumber(exec) / max;
> 
> I’m not sure that "arg" is quite the right name here, since this is "arg / max". I might call this scaledArgument.

- arg changed to scaledArgument

> 
> It’s not correct for this function to evaluate all the arguments twice. Programs can observe the side effect of an argument being evaluated, and can detect if it’s done twice. The algorithm must do it only once. So we need to store the argument values somewhere so we don’t have to compute them again. An easy way to do that is to use a Vector<double, 32>, which should be relatively high performance.

- The second loop is working with Vector for now.

> 
> This function needs to exit early if we get an exception when calling toNumber.

- Added the exception handling after the toNumber call.

> 
> We should create tests that cover both these issues: That each valueOf function is called only once, not twice, and that no additional functions are called after a prior function throws an exception. We should test other math functions too; I’m pretty sure some of them are handling these issues incorrectly.

- Ok, I will test them.

[Tibor Mészáros]

Created attachment 226925 [details]
Patch v9

removed the "if (argsCount == 1 && !arg)" check

[Darin Adler]

(In reply to comment #25)
> - Yes, we need this case, because if isn't there, the result will be NaN, instead of Infinity, if there were a NaN before.

I believe that is correct behavior. If any argument is NaN the overall result should be NaN, even if another argument is Infinity. That’s the general rule about NaN for all contexts. Could you point me to documentation that proves otherwise?

[Darin Adler]

Comment on attachment 226925 [details]
Patch v9

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

review- because of incorrect behavior when Infinity and NaN are combined

> LayoutTests/js/math-expected.txt:94
> +PASS Math.hypot(1, NaN, Infinity) is Infinity

Shouldn’t the expected result here be NaN, not Infinity?

> Source/JavaScriptCore/runtime/MathObject.cpp:113
> +    putDirectNativeFunctionWithoutTransition(vm, globalObject, Identifier(&vm, "hypot"), 2, mathProtoFuncHypot, NoIntrinsic, DontEnum | Function);

No test coverage for the number of arguments? We should be testing that.

> Source/JavaScriptCore/runtime/MathObject.cpp:185
> +    Vector<double> args; 

We can get significantly better efficiency, avoiding heap allocation by saying:

    Vector<double, 8> args;

Choosing some number that is larger than the typical number of arguments passed to this function.

We should also do:

    args.reserveInitialCapacity(argsCount);

> Source/JavaScriptCore/runtime/MathObject.cpp:187
> +        args.append(exec->uncheckedArgument(i).toNumber(exec));

This can and should be args.uncheckedAppend if we use args.reserveInitialCapacity above.

> Source/JavaScriptCore/runtime/MathObject.cpp:191
> +        if (std::isinf(args[i]))
> +            return JSValue::encode(jsDoubleNumber(+std::numeric_limits<double>::infinity()));

Please remove this unless the behavior where we expect Infinity even if there is a NaN is correct. I do not believe it’s correct.

> Source/JavaScriptCore/runtime/MathObject.cpp:198
> +    // Kahan summation algorithm significantly reduces the numerical error in the total obtained.

I suggest putting this comment before the definitions of sum and compensation; they seem like part of the loop to me.

> Source/JavaScriptCore/runtime/MathObject.cpp:200
> +    for (unsigned i = 0; i < args.size(); ++i) {
> +        double scaledArgument = args[i] / max;

A nicer way to write this is:

    for (double argument : args) {
        double scaledArgument = argument / max;

No need for the use of "i" or "size".

[Tibor Mészáros]

(In reply to comment #28)
> (From update of attachment 226925 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=226925&action=review
> 
> review- because of incorrect behavior when Infinity and NaN are combined
> 
> > LayoutTests/js/math-expected.txt:94
> > +PASS Math.hypot(1, NaN, Infinity) is Infinity
> 
> Shouldn’t the expected result here be NaN, not Infinity?

- The standard say: 
If any argument is +∞, the result is +∞.
If any argument is −∞, the result is +∞.
If no argument is +∞ or −∞, and any argument is NaN, the result is NaN.

> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:113
> > +    putDirectNativeFunctionWithoutTransition(vm, globalObject, Identifier(&vm, "hypot"), 2, mathProtoFuncHypot, NoIntrinsic, DontEnum | Function);
> 
> No test coverage for the number of arguments? We should be testing that.
> 

- added

> > Source/JavaScriptCore/runtime/MathObject.cpp:185
> > +    Vector<double> args; 
> 
> We can get significantly better efficiency, avoiding heap allocation by saying:
> 
>     Vector<double, 8> args;
> 
> Choosing some number that is larger than the typical number of arguments passed to this function.
> 
> We should also do:
> 
>     args.reserveInitialCapacity(argsCount);
> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:187
> > +        args.append(exec->uncheckedArgument(i).toNumber(exec));
> 
> This can and should be args.uncheckedAppend if we use args.reserveInitialCapacity above.

- Added, and changed code to match with your explanation.

> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:191
> > +        if (std::isinf(args[i]))
> > +            return JSValue::encode(jsDoubleNumber(+std::numeric_limits<double>::infinity()));
> 
> Please remove this unless the behavior where we expect Infinity even if there is a NaN is correct. I do not believe it’s correct.

- if it's not there, the NaN will be the result in some cases, so we have to check the inf.

> 
> > Source/JavaScriptCore/runtime/MathObject.cpp:198
> > +    // Kahan summation algorithm significantly reduces the numerical error in the total obtained.
> 
> I suggest putting this comment before the definitions of sum and compensation; they seem like part of the loop to me.
> 

- Moved to above the variables.

> > Source/JavaScriptCore/runtime/MathObject.cpp:200
> > +    for (unsigned i = 0; i < args.size(); ++i) {
> > +        double scaledArgument = args[i] / max;
> 
> A nicer way to write this is:
> 
>     for (double argument : args) {
>         double scaledArgument = argument / max;
> 
> No need for the use of "i" or "size".

- changed

[Tibor Mészáros]

Created attachment 226942 [details]
Patch v10

Updated patch

[Oliver Hunt]

(In reply to comment #29)
> (In reply to comment #28)
> > (From update of attachment 226925 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=226925&action=review
> > 
> > review- because of incorrect behavior when Infinity and NaN are combined
> > 
> > > LayoutTests/js/math-expected.txt:94
> > > +PASS Math.hypot(1, NaN, Infinity) is Infinity
> > 
> > Shouldn’t the expected result here be NaN, not Infinity?
> 
> - The standard say: 
> If any argument is +∞, the result is +∞.
> If any argument is −∞, the result is +∞.
> If no argument is +∞ or −∞, and any argument is NaN, the result is NaN.

I suspect this is a spec bug.  We (AllenWB and I) are investigating -- cc'ing brendan, i'm not sure if AllenWB or dherman have b.w.o accounts

[Oliver Hunt]

(In reply to comment #31)
> (In reply to comment #29)
> > (In reply to comment #28)
> > > (From update of attachment 226925 [details] [details] [details])
> > > View in context: https://bugs.webkit.org/attachment.cgi?id=226925&action=review
> > > 
> > > review- because of incorrect behavior when Infinity and NaN are combined
> > > 
> > > > LayoutTests/js/math-expected.txt:94
> > > > +PASS Math.hypot(1, NaN, Infinity) is Infinity
> > > 
> > > Shouldn’t the expected result here be NaN, not Infinity?
> > 
> > - The standard say: 
> > If any argument is +∞, the result is +∞.
> > If any argument is −∞, the result is +∞.
> > If no argument is +∞ or −∞, and any argument is NaN, the result is NaN.
> 
> I suspect this is a spec bug.  We (AllenWB and I) are investigating -- cc'ing brendan, i'm not sure if AllenWB or dherman have b.w.o accounts

Our consensus is that this is a spec bug, if any value is NaN the result should be NaN

[Allen Wirfs-Brock]

I've created ECMAScript bug https://bugs.ecmascript.org/show_bug.cgi?id=2580 
to track this.

However, the bottom line may be that the currently specified behavior matches the IEEE spec. and is what is commonly implemented by C libraries.

Additional reference links in the bugs.ecmascript.org ticket.

[WebKit Commit Bot]

Comment on attachment 226942 [details]
Patch v10

Clearing flags on attachment: 226942

Committed r165795: <http://trac.webkit.org/changeset/165795>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Frédéric Wang (:fredw)]

Hey. When you implement a new Web features, could please add the WebExposed keyword? That will help MDN documentation writer to keep track of improvements in WebKit. See https://lists.webkit.org/pipermail/webkit-dev/2014-March/026298.html

[Tibor Mészáros]

(In reply to comment #36)
> Hey. When you implement a new Web features, could please add the WebExposed keyword? That will help MDN documentation writer to keep track of improvements in WebKit. See https://lists.webkit.org/pipermail/webkit-dev/2014-March/026298.html

Hi! Okay, I will add the WebExposed next time.