Closed Bug 808148 Opened 12 years ago Closed 11 years ago

prototype Math.imul

Categories

(Core :: JavaScript Engine, defect)

x86
macOS
defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla20

People

(Reporter: dherman, Assigned: evilpie)

References

()

Details

(Keywords: dev-doc-complete, Whiteboard: [js:p2])

Attachments

(1 file, 2 obsolete files)

Emscripten and similar code generators really want an optimized and concise way to do 32-bit integer multiplication. I have proposed Math.imul to es-discuss:

https://mail.mozilla.org/pipermail/es-discuss/2012-November/026126.html

This bug is for prototyping this in the JS engine.

Dave
Concretely, the semantics of imul is:

    imul(a, b) = ToInt32((ToUint32(a) x ToUint32(b)) mod 2^32)

where "x" is the "true" mathematical integer multiplication.

Or, more intuitively, the semantics is "coerce to int and do what C does."

Dave
Assignee: general → evilpies
Wow, already have an assignee!
Attached patch v1 (obsolete) — Splinter Review
Are there any other interesting values to test with (probably yes)? I assumed that everything below < 2 args produces 0, because (undefined >>> 0) == 0.

I am going to add JIT support for Ion soon, but it looks like this doesn't really want to implemented in terms of MMul (the normal multiplication operator).
Attachment #677895 - Flags: review?(jwalden+bmo)
Attachment #677895 - Flags: review?(jwalden+bmo)
Attached patch v1 with tests (obsolete) — Splinter Review
Yes the tests actually exists. Currently running through try: https://tbpl.mozilla.org/?tree=Try&rev=2fc501518375.
for (let [x, y, z] of table)
    assertEq(Math.imul(x, y), z);
(In reply to Jason Orendorff [:jorendorff] from comment #5)
> for (let [x, y, z] of table)
>     assertEq(Math.imul(x, y), z);
This aborts Ion compilation at the moment.
Comment on attachment 677908 [details] [diff] [review]
v1 with tests

Actually why not. Finishing the ionmonkey patch is going to take me a few more days.
Attachment #677908 - Flags: review?(jwalden+bmo)
Comment on attachment 677908 [details] [diff] [review]
v1 with tests

Review of attachment 677908 [details] [diff] [review]:
-----------------------------------------------------------------

r- until the various should-be questions are addressed -- rest is all trivial style changes or whatever.

dherman, should imul do a ToUint32 on the first argument if only a single argument is provided?  Or should it short-circuit to returning 0?  The spelled-out semantics here don't break it down step-by-step enough to say (and ideally they'd be clearer about the ordering of ToUint32 on the two arguments).  Any chance we could get an exact, step-by-step algorithm here, and be sure semantics for the edges considered here actually have been considered and deliberately chosen?

::: js/src/jit-test/tests/basic/mathImul.js
@@ +14,5 @@
> +	[0xffffffff, 0xffffffff, 1],
> +	[0xffffffff, -0xffffffff, -1],
> +	[0xffffffff, 0xfffffffe, 2],
> +	[0xffffffff, -0xfffffffe, -2],
> +

A random smattering of other tests I'd add here, in some vaguely logical place for each:

[0x10000, 0x10000, 0]
[-0, 0, 0]
[0, -0, 0]
[-1, -0, 0]
[1, -0, 0]
[{}, [], 0]
[[], {}, 0]

And a one-off test for Math.imul({ valueOf: function() { throw "ha ha ha"; } });.

@@ +28,5 @@
> +assertEq(Math.imul(100), 0);
> +assertEq(Math.imul(NaN, 100), 0);
> +assertEq(Math.imul(NaN, NaN), 0);
> +assertEq(Math.imul(5, Infinity), 0);
> +

A one-off test for this is needed, too:

var order = [];
assertEq(Math.imul({ valueOf: function() { order.push("first"); return 0; } },
                   { valueOf: function() { order.push("second"); return 0; } }),
         0);
assertEq(order[0], "first");
assertEq(order[1], "second");

Note that if the result of the first-performed ToUint32 is 0, we still need to ToUint32 the second one in case it has side effects or throws.  So we should probably have this as well:

var seen = [];
try
{
  Math.imul({ valueOf: function() { seen.push("one"); return 17; } },
            { valueOf: function() { throw "abort!"; } });
  assertEq(true, false, "no error thrown");
}
catch (e)
{
  assertEq(e, "abort!", "should have thrown partway through, instead threw " + e);
}
assertEq(seen.length, 1);
assertEq(seen[0], "one");

@@ +30,5 @@
> +assertEq(Math.imul(NaN, NaN), 0);
> +assertEq(Math.imul(5, Infinity), 0);
> +
> +for (var i = 0; i < table.length; i++) {
> +	assertEq(Math.imul(table[i][0], table[i][1]), table[i][2]);

A tab character, really?  :-P

::: js/src/jsmath.cpp
@@ +335,5 @@
> +
> +    if (args.length() < 2) {
> +        args.rval().setInt32(0);
> +        return true;
> +    }

What should be the result of this?

  Math.imul({ valueOf: function() { throw "ha ha ha"; } });

dherman?  Having that throw is consistent with everything else in the language, so that seems desirable to me, no matter that it makes this a bit messy.  :-\

@@ +341,5 @@
> +    uint32_t a, b;
> +    if (!ToUint32(cx, args[0], &a) || !ToUint32(cx, args[1], &b))
> +        return false;
> +
> +    args.rval().setInt32(static_cast<int32_t>(a * b));

You ignore C++ undefined behavior at your peril when you assign a uint32_t that doesn't fit in an int32_t, into an int32_t.  This is a little messy but I think fixes it:

    uint32_t product = a * b;
    args.rval().setInt32(product > INT32_MAX
                         ? int32_t(INT32_MIN + (product - INT32_MAX))
                         : int32_t(product));
Attachment #677908 - Flags: review?(jwalden+bmo)
Attachment #677908 - Flags: review-
Attachment #677908 - Flags: feedback?(dherman)
Attached patch v2Splinter Review
Fixed all the comments. Still waiting on feedback from dherman.
Attachment #677895 - Attachment is obsolete: true
Attachment #677908 - Attachment is obsolete: true
Attachment #677908 - Flags: feedback?(dherman)
Flags: needinfo?(dherman)
> dherman, should imul do a ToUint32 on the first argument if only a single
> argument is provided?  Or should it short-circuit to returning 0?

Let's avoid special short-circuiting cases, since conceptually it should be considered a set of coercions wrapping a pure (int x int) -> int operation.

> The spelled-out semantics here don't break it down step-by-step enough to say
> (and ideally they'd be clearer about the ordering of ToUint32 on the two
> arguments).

The semantics should perform ToUint32 to each of the first two arguments (using `undefined` as the value to pass to ToUint32 if the argument is not provided), in left-to-right order -- this is consistent with the other Math functions, which all perform their ToNumber coercions in left-to-right order. If either one of the coercions throws, the entire operation throws.

> Any chance we could get an exact, step-by-step algorithm here,
> and be sure semantics for the edges considered here actually have been
> considered and deliberately chosen?

That's about as much step-by-step instruction as you get from any of the other parts of the spec for Math functions. Perform the coercions in left-to-right order, then if neither one throws, do the mathematical operation.

> What should be the result of this?
> 
>   Math.imul({ valueOf: function() { throw "ha ha ha"; } });
> 
> dherman?  Having that throw is consistent with everything else in the
> language, so that seems desirable to me, no matter that it makes this a bit
> messy.  :-\

Yes, it throws. This isn't spelled out in ES5:

    http://ecma-international.org/ecma-262/5.1/#sec-15.8.2

but the latest edition of Allen's draft ES6 does spell it out explicitly. If either coercion fails with an abrupt completion, then the operation is canceled and the abrupt completion becomes the completion of the entire operation.

Dave
Flags: needinfo?(dherman)
Whiteboard: [js:p2]
Comment on attachment 685707 [details] [diff] [review]
v2

Thank you for answering these questions dherman. Looks like Waldo predicted the right semantics, and thus this patch should be okay.
Attachment #685707 - Flags: review?(jwalden+bmo)
Comment on attachment 685707 [details] [diff] [review]
v2

Review of attachment 685707 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsmath.cpp
@@ +341,5 @@
> +
> +    uint32_t product = a * b;
> +    args.rval().setInt32(product > INT32_MAX
> +                         ? int32_t(INT32_MIN + (product - INT32_MAX - 1))
> +                         : int32_t(product));

Why not setNumber(uint32_t)?
Comment on attachment 685707 [details] [diff] [review]
v2

Review of attachment 685707 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit-test/tests/basic/mathImul.js
@@ +31,5 @@
> +    [3.4, 6, 18]
> +];
> +
> +try {
> +    assertEq(Math.imul({ valueOf: function() { throw "ha ha ha"; } }, 0));

Remove the assertEq on this line, since it's actively misleading about what this Math.imul() is expected to do until you read the subsequent line.

@@ +67,5 @@
> +
> +for (var i = 0; i < table.length; i++) {
> +    print(table[i][0] + " * " + table[i][1])
> +    assertEq(Math.imul(table[i][0], table[i][1]), table[i][2]);
> +}

Any reason not to repeat this loop, but switching the order of the arguments to Math.imul?  All the entries should be effect-free and so perfectly commutative, looks like.

::: js/src/jsmath.cpp
@@ +341,5 @@
> +
> +    uint32_t product = a * b;
> +    args.rval().setInt32(product > INT32_MAX
> +                         ? int32_t(INT32_MIN + (product - INT32_MAX - 1))
> +                         : int32_t(product));

setNumber(uint32_t) isn't what this does -- this does setInt32(ToInt32(product)), just that the only ToInt32 we have takes double and not uint32_t.
Attachment #685707 - Flags: review?(jwalden+bmo) → review+
https://hg.mozilla.org/mozilla-central/rev/1237d9a6ce46
Status: NEW → RESOLVED
Closed: 11 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla20
Keywords: dev-doc-needed
Blocks: 822436
Any 64 bit mul flavor of Math.imul as well? The high and low 32 bit halfs can be stored in two Numbers if needed to ensure no precision loss.
There is work on 64-bit ints in ES7, so adding Math.imul64(low1, high1, low2, high2) or such might be redundant.
You need to log in before you can comment on or make changes to this bug.