Closed
Bug 836102
Opened 10 years ago
Closed 10 years ago
IonMonkey: Avoid double math in base.js's Math.random() replacement
Categories
(Core :: JavaScript Engine, defect)
Tracking
()
RESOLVED
FIXED
mozilla21
People
(Reporter: sstangl, Assigned: h4writer)
References
(Blocks 1 open bug)
Details
Attachments
(1 file)
3.34 KB,
patch
|
mjrosenb
:
review+
|
Details | Diff | Splinter Review |
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•10 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•10 years ago
|
||
Okay, scratch that previous comment. I'll look tomorrow when I'm more awake ;).
Comment 3•10 years ago
|
||
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•10 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•10 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 6•10 years ago
|
||
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+
Assignee | ||
Comment 7•10 years ago
|
||
https://hg.mozilla.org/integration/mozilla-inbound/rev/efc9d9f5f30e Follow-up bug to do this better: https://bugzilla.mozilla.org/show_bug.cgi?id=836826
Comment 8•10 years ago
|
||
https://hg.mozilla.org/mozilla-central/rev/efc9d9f5f30e
Status: NEW → RESOLVED
Closed: 10 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.
Description
•