Closed Bug 1599465 Opened 2 months ago Closed 2 months ago

Reduce allocations in BigInt functions and add fast-paths for uint64 BigInts

Categories

(Core :: JavaScript Engine, enhancement, P1)

enhancement

Tracking

()

RESOLVED FIXED
mozilla73
Tracking Status
firefox72 --- wontfix
firefox73 --- fixed

People

(Reporter: anba, Assigned: anba)

Details

Attachments

(14 files)

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
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);

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.

This allows to use these functions without pulling in the complete jsnum.h header.

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

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

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

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

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

Add the suffix in preparation for part 8.

Depends on D54762

An earlier part changed the digit function to be const, so we can now make
these two functions const, too.

Depends on D54764

absoluteCompare() is currently called twice when subtracting two BigInts,
avoiding the second call gives a slight speed-up.

Depends on D54765

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

Removes rooting when the allocation isn't followed by any operation which can
GC resp. takes a JSContext argument.

Depends on D54768

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

Priority: -- → P1
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
Keywords: leave-open

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.

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
Keywords: leave-open

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.

Keywords: leave-open
Keywords: leave-open
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
Status: ASSIGNED → RESOLVED
Closed: 2 months ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla73
You need to log in before you can comment on or make changes to this bug.