Last Comment Bug 808148 - prototype Math.imul
: prototype Math.imul
Status: RESOLVED FIXED
[js:p2]
: dev-doc-complete
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86 Mac OS X
: -- normal (vote)
: mozilla20
Assigned To: Tom Schuster [:evilpie]
:
: Jason Orendorff [:jorendorff]
Mentors:
https://mail.mozilla.org/pipermail/es...
Depends on:
Blocks: 822436
  Show dependency treegraph
 
Reported: 2012-11-02 12:41 PDT by Dave Herman [:dherman]
Modified: 2013-04-15 21:53 PDT (History)
15 users (show)
ryanvm: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
v1 (1.46 KB, patch)
2012-11-02 14:41 PDT, Tom Schuster [:evilpie]
no flags Details | Diff | Splinter Review
v1 with tests (2.34 KB, patch)
2012-11-02 15:25 PDT, Tom Schuster [:evilpie]
jwalden+bmo: review-
Details | Diff | Splinter Review
v2 (4.47 KB, patch)
2012-11-27 10:39 PST, Tom Schuster [:evilpie]
jwalden+bmo: review+
Details | Diff | Splinter Review

Description Dave Herman [:dherman] 2012-11-02 12:41:59 PDT
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
Comment 1 Dave Herman [:dherman] 2012-11-02 12:51:20 PDT
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
Comment 2 Luke Wagner [:luke] 2012-11-02 14:10:50 PDT
Wow, already have an assignee!
Comment 3 Tom Schuster [:evilpie] 2012-11-02 14:41:24 PDT
Created attachment 677895 [details] [diff] [review]
v1

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).
Comment 4 Tom Schuster [:evilpie] 2012-11-02 15:25:30 PDT
Created attachment 677908 [details] [diff] [review]
v1 with tests

Yes the tests actually exists. Currently running through try: https://tbpl.mozilla.org/?tree=Try&rev=2fc501518375.
Comment 5 Jason Orendorff [:jorendorff] 2012-11-02 15:43:12 PDT
for (let [x, y, z] of table)
    assertEq(Math.imul(x, y), z);
Comment 6 Tom Schuster [:evilpie] 2012-11-03 04:43:12 PDT
(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 7 Tom Schuster [:evilpie] 2012-11-07 09:21:45 PST
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.
Comment 8 Jeff Walden [:Waldo] (remove +bmo to email) 2012-11-12 15:19:14 PST
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));
Comment 9 Tom Schuster [:evilpie] 2012-11-27 10:39:46 PST
Created attachment 685707 [details] [diff] [review]
v2

Fixed all the comments. Still waiting on feedback from dherman.
Comment 10 Dave Herman [:dherman] 2012-12-01 14:56:36 PST
> 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
Comment 11 Tom Schuster [:evilpie] 2012-12-04 11:11:55 PST
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.
Comment 12 :Ms2ger (⌚ UTC+1/+2) 2012-12-04 11:18:52 PST
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 13 Jeff Walden [:Waldo] (remove +bmo to email) 2012-12-07 15:31:05 PST
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.
Comment 15 Ryan VanderMeulen [:RyanVM] 2012-12-15 13:32:53 PST
https://hg.mozilla.org/mozilla-central/rev/1237d9a6ce46
Comment 17 Grant Galitz 2013-01-11 07:26:47 PST
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.
Comment 18 Alon Zakai (:azakai) 2013-01-11 10:17:04 PST
There is work on 64-bit ints in ES7, so adding Math.imul64(low1, high1, low2, high2) or such might be redundant.

Note You need to log in before you can comment on or make changes to this bug.