Reduce allocations in BigInt functions and add fast-paths for uint64 BigInts
Categories
(Core :: JavaScript Engine, enhancement, P1)
Tracking
()
People
(Reporter: anba, Assigned: anba)
Details
Attachments
(14 files)
47 bytes,
text/x-phabricator-request
|
Details | Review | |
Bug 1599465 - Part 2: Implement in-place modification in destructivelyTrimHighZeroDigits. r=jwalden!
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review | |
47 bytes,
text/x-phabricator-request
|
Details | Review |
Including:
- Resolve the TODO in
BigInt::destructivelyTrimHighZeroDigits
to modify in-place. - Add fast-paths for BigInts fitting in uint64.
- And some other clean-ups noted while working on this code.
function f(op) {
var xs = [5n, 6n]
var ys = [10n, 20n]
var r = 0;
var t = dateNow()
for (var i = 0; i < 1000000; ++i) {
var z = op(xs[i&1], ys[i&1]);
if (z) r++;
}
return [dateNow() - t, r];
}
function test(op) {
// Create a new function for each test.
return Function(`return ${f}`)()(op);
}
// Addition improves from 230-850ms (varies b/c of extra allocations) to ~85ms:
test((x, y) => x + y);
// Subtraction improves from 105ms to ~85ms:
test((x, y) => x - y);
// Multiplication improves from 230-850ms (varies b/c of extra allocations) to ~75ms:
test((x, y) => x * y);
// Exponentiation improves from ~3000ms to ~100ms:
test((x, y) => x ** y);
Assignee | ||
Comment 1•1 year ago
|
||
When additionally nursery allocating BigInts:
- Addition and subtraction improve to ~65ms.
- Multiplication improves to ~55ms.
- Exponentiation improves to ~80ms.
And the numbers are more stable when nursery allocating BigInts.
Assignee | ||
Comment 2•1 year ago
|
||
This allows to use these functions without pulling in the complete jsnum.h
header.
Assignee | ||
Comment 3•1 year ago
|
||
Resolves the TODO in destructivelyTrimHighZeroDigits
and additionally removes
trimHighZeroDigits
, because it is no longer used. This change is especially
beneficial for functions which are most of the time over-estimating the result
digit length, like for example BigInt::absoluteAdd
.
Depends on D54757
Assignee | ||
Comment 4•1 year ago
|
||
Adds fitsInUint64
to check if a BigInt fits into uint64_t and uint64FromNonZero
to extract an uint64_t value from a non-zero BigInt. Boths function are inline
because the next patches will use them in fast-paths.
Depends on D54758
Assignee | ||
Comment 5•1 year ago
|
||
Add a fast path for uint64 BigInts to BigInt::absoluteAdd
. This fast path
gives a substantial speed-up, because addition for uint64 BigInts no longer
needs allocate malloc memory when the result also fits into uint64_t.
Depends on D54759
Assignee | ||
Comment 6•1 year ago
|
||
Similar to the previous part, also add a fast-path when multiplying two Bigints
which fit into uint64_t. When the result also fits into uint64_t, this approach
avoids allocating unused malloc memory.
Depends on D54760
Assignee | ||
Comment 7•1 year ago
|
||
We never define HAVE_INT128_SUPPORT
, so the uint128 code path is never
enabled. Change the test to use __SIZEOF_INT128__
to enable it on
applicable platforms.
Depends on D54761
Assignee | ||
Comment 8•1 year ago
|
||
Add the suffix in preparation for part 8.
Depends on D54762
Assignee | ||
Comment 9•1 year ago
|
||
Depends on D54763
Assignee | ||
Comment 10•1 year ago
|
||
An earlier part changed the digit
function to be const
, so we can now make
these two functions const
, too.
Depends on D54764
Assignee | ||
Comment 11•1 year ago
|
||
absoluteCompare()
is currently called twice when subtracting two BigInts,
avoiding the second call gives a slight speed-up.
Depends on D54765
Assignee | ||
Comment 12•1 year ago
|
||
Subtraction doesn't have the same unused malloc memory problem which was present
for addition and subtraction, so the relative speed-up when adding a uint64
fast-path is less prominent (only about 10%), but it still seems worthwhile to
provide a fast-path, too.
Depends on D54767
Assignee | ||
Comment 13•1 year ago
|
||
Removes rooting when the allocation isn't followed by any operation which can
GC resp. takes a JSContext
argument.
Depends on D54768
Assignee | ||
Comment 14•1 year ago
|
||
Changes the existing fast-path for 2^n to any (2^m)^n. And adds a fast-path for
uint64 BigInts, so we only need to allocate a single BigInt when the result also
fits in uint64.
The for-loop was changed to a while-loop, because that made it easier to give
both loops the same structure.
Depends on D54769
Updated•1 year ago
|
Comment 15•1 year ago
|
||
Pushed by apavel@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/953b1e11b401 Part 1: Move checked arithmetic functions into their own header. r=jwalden https://hg.mozilla.org/integration/autoland/rev/751fec3b521b Part 2: Implement in-place modification in destructivelyTrimHighZeroDigits. r=jwalden https://hg.mozilla.org/integration/autoland/rev/c0bae66161b9 Part 3: Add fitsInUint64 and uint64FromNonZero to BigInt. r=jwalden https://hg.mozilla.org/integration/autoland/rev/035686cce4d8 Part 4: Add fast path for BigInt addition with uint64 magnitude. r=jwalden https://hg.mozilla.org/integration/autoland/rev/b2d5b77d8e78 Part 5: Add fast path for BigInt multiplication with uint64 magnitude. r=jwalden https://hg.mozilla.org/integration/autoland/rev/434ff032438c Part 6: Change test to check if uint128 types are available. r=jwalden https://hg.mozilla.org/integration/autoland/rev/9e864c88ccb4 Part 7: Add "Value" suffix to BigInt operations on Values types. r=jandem https://hg.mozilla.org/integration/autoland/rev/6f84a86e1fb9 Part 8: Remove function call indirection when calling BigInt operations from jit-code. r=jandem https://hg.mozilla.org/integration/autoland/rev/efbe6cad4fe1 Part 9: Add 'const' modifier to hash() and dump() methods. r=jwalden https://hg.mozilla.org/integration/autoland/rev/7c2030a7c4eb Part 10: Avoid calling absoluteCompare() twice in BigInt subtraction. r=jwalden https://hg.mozilla.org/integration/autoland/rev/7348a9f6d8a5 Part 11: Add fast path for BigInt subtraction with uint64 magnitude. r=jwalden https://hg.mozilla.org/integration/autoland/rev/1152088adc0c Part 12: Remove extra rooting. r=jwalden
Assignee | ||
Updated•1 year ago
|
Comment 16•1 year ago
|
||
bugherder |
https://hg.mozilla.org/mozilla-central/rev/953b1e11b401
https://hg.mozilla.org/mozilla-central/rev/751fec3b521b
https://hg.mozilla.org/mozilla-central/rev/c0bae66161b9
https://hg.mozilla.org/mozilla-central/rev/035686cce4d8
https://hg.mozilla.org/mozilla-central/rev/b2d5b77d8e78
https://hg.mozilla.org/mozilla-central/rev/434ff032438c
https://hg.mozilla.org/mozilla-central/rev/9e864c88ccb4
https://hg.mozilla.org/mozilla-central/rev/6f84a86e1fb9
https://hg.mozilla.org/mozilla-central/rev/efbe6cad4fe1
https://hg.mozilla.org/mozilla-central/rev/7c2030a7c4eb
https://hg.mozilla.org/mozilla-central/rev/7348a9f6d8a5
https://hg.mozilla.org/mozilla-central/rev/1152088adc0c
Comment 17•1 year ago
|
||
I suppose to a very minor degree I would prefer writing out an explicit division by two to right-shifting by one -- this is not a strength reduction any compiler is going to fail to perform -- but it's not extremely important.
Comment 18•1 year ago
|
||
Pushed by ccoroiu@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/5600a9888163 Part 13: Add fast path for BigInt exponentiation with uint64 magnitude. r=jwalden
Assignee | ||
Updated•1 year ago
|
Assignee | ||
Comment 19•1 year ago
|
||
left
's magnitude in BigInt::absoluteAdd
resp. x
's magnitude in
BigInt::absoluteSub
is always larger than the other operand, so we don't need
to check if both operands fit in uint64.
Assignee | ||
Updated•1 year ago
|
Comment 20•1 year ago
|
||
bugherder |
Assignee | ||
Updated•1 year ago
|
Comment 21•1 year ago
|
||
Pushed by ccoroiu@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/ee1fdd7df642 Part 14: Addition and subtraction don't need to check if both operands fit in uint64. r=jwalden
Comment 22•1 year ago
|
||
bugherder |
Updated•1 year ago
|
Description
•