IonMonkey: Avoid double math in base.js's Math.random() replacement

RESOLVED FIXED in mozilla21

Status

()

defect
RESOLVED FIXED
7 years ago
7 years ago

People

(Reporter: sstangl, Assigned: h4writer)

Tracking

(Blocks 1 bug)

unspecified
mozilla21
x86_64
Linux
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

Reporter

Description

7 years ago
The following Math.random() replacement from v8's base.js uses double arithmetic:

> Math.random = (function() {
>   var seed = 49734321;
>   return function() {
>     // Robert Jenkins' 32 bit integer hash function.
>     seed = ((seed + 0x7ed55d16) + (seed << 12))  & 0xffffffff;
>     seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
>     seed = ((seed + 0x165667b1) + (seed << 5))   & 0xffffffff;
>     seed = ((seed + 0xd3a2646c) ^ (seed << 9))   & 0xffffffff;
>     seed = ((seed + 0xfd7046c5) + (seed << 3))   & 0xffffffff;
>     seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
>     return (seed & 0xfffffff) / 0x10000000;
>   };
> })();

Since the effective bits beyond 32 are discarded, the 0xffffffff (or |0) should propagate.

This is worth about 3% on v8-regexp.
Assignee

Comment 1

7 years ago
Looking quickly into this, we do use integer arithmetic.

The problem is
1) We don't specialize the loadFixedslot of "seed" to integer loadFixedSlotT
2) The code does StoreFixedSlot after LoadFixedSlot. This can get removed. See bug 801872.
Assignee

Comment 2

7 years ago
Okay, scratch that previous comment. I'll look tomorrow when I'm more awake ;).
There is a simple fix for this.  I recently added a pass that identifies computations that overflow and are truncated, and forces them back to integer computations.  It requires identifying int32->double conversions and removing them.  The problem here is that operations like |seed + 0xfd7046c5| involve seed getting coerced to double because the other operand is a double.  Since the constant 0xfd7046c5 is a double, and not converted from an integer, we don't convert the operation to an integer.  Adding a simple (in pseudo-code)
virtual bool MConstant::isBigIntOutput() { return typeIsNumber() && frac(number) == 0 && log_2(number) - 32; }
basically, if the constant is a double, and all of the fractional bits are zero, then we want to return the number of bits past the 32nd bit that would need to be set in order for the number to be represented exactly.  There may also be some magic required to truncate the double constant into an integer constant at compile time.
Assignee

Comment 4

7 years ago
Running this benchmark 1000000 times gives:

Without patch:
real	0m1.882s

With patch:
real	0m0.031s
Assignee: general → hv1989
Attachment #708086 - Flags: review?(mrosenberg)
Assignee

Comment 5

7 years ago
Comment on attachment 708086 [details] [diff] [review]
Truncate constants

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

I'll add testcases for the issues I found here.

::: js/src/ion/MIR.cpp
@@ +340,5 @@
> +    if (js::ion::EdgeCaseAnalysis::AllUsesTruncate(this) &&
> +        value_.isDouble() && isBigIntOutput())
> +    {
> +        // Truncate the double to int, since all uses truncates it.
> +        value_.setInt32(int32_t(value_.toDouble()));

Off course this should be: ToInt32() instead of int32_t cast

::: js/src/ion/MIR.h
@@ +710,5 @@
> +            double value = value_.toDouble();
> +            int64_t valint = value;
> +            int64_t max = 1LL<<53;
> +            if (double(valint) != value)
> +                return false;

if (valint < 0)
  valint = -valint;

// This should get added to handle the negative case.
Comment on attachment 708086 [details] [diff] [review]
Truncate constants

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

The patch mostly looks good.  You may want to lower the limit from 1<<53 to 1 << 33 for now... It will handle all of the cases present in the Math.random() replacement, and won't involve handling incredibly annoying cases such as:
var x = 0x123456789abcd;
x = x + x; // x = 640511947003802
x = x + x; // x = 1281023894007604
x = x + x; // x = 2562047788015208
x = x + x; // x = 5124095576030416
x = x + x; // x = 10248191152060832
print(x+1) // prints 10248191152060832
print(x+1 | 0) // prints -248153696, with optimization and without the previous print, will print -248153695
Since we cut off after 20 operations, limiting the size of the constant to 33 bits should prevent us from ever reaching the magical 2**53 plateau.  Or you can figure out how to limit the number of additions to a lower number when one of the immediates present is well over 2**32.
Attachment #708086 - Flags: review?(mrosenberg) → review+
https://hg.mozilla.org/mozilla-central/rev/efc9d9f5f30e
Status: NEW → RESOLVED
Closed: 7 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla21
You need to log in before you can comment on or make changes to this bug.