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

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P1)

Description

[André Bargull [:anba]]

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

Comment 1

[André Bargull [:anba]]

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.

Comment 2

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 1: Move checked arithmetic functions into their own header. r=jwalden!

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

Comment 3

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 2: Implement in-place modification in destructivelyTrimHighZeroDigits. r=jwalden!

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

Comment 4

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 3: Add fitsInUint64 and uint64FromNonZero to BigInt. r=jwalden!

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

Comment 5

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 4: Add fast path for BigInt addition with uint64 magnitude. r=jwalden!

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

Comment 6

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 5: Add fast path for BigInt multiplication with uint64 magnitude. r=jwalden!

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

Comment 7

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 6: Change test to check if uint128 types are available. r=jwalden!

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

Comment 8

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 7: Add "Value" suffix to BigInt operations on Values types. r=jandem!

Add the suffix in preparation for part 8.

Depends on D54762

Comment 9

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 8: Remove function call indirection when calling BigInt operations from jit-code. r=jandem!

Depends on D54763

Comment 10

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 9: Add 'const' modifier to hash() and dump() methods. r=jwalden!

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

Depends on D54764

Comment 11

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 10: Avoid calling absoluteCompare() twice in BigInt subtraction. r=jwalden!

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

Depends on D54765

Comment 12

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 11: Add fast path for BigInt subtraction with uint64 magnitude. r=jwalden!

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

Comment 13

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 12: Remove extra rooting. r=jwalden!

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

Depends on D54768

Comment 14

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 13: Add fast path for BigInt exponentiation with uint64 magnitude. r=jwalden!

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

Comment 15

[Pulsebot]

Pushed by [e-mail]:
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

Comment 16

[Stefan Hindli [:stefan_hindli]]

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

[Jeff Walden [:Waldo]]

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

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/5600a9888163
Part 13: Add fast path for BigInt exponentiation with uint64 magnitude. r=jwalden

Comment 19

[André Bargull [:anba]]

Attachment: Bug 1599465 - Part 14: Addition and subtraction don't need to check if both operands fit in uint64. r=jwalden!

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.

Comment 20

[Andreea Pavel [:apavel]]

https://hg.mozilla.org/mozilla-central/rev/5600a9888163

Comment 21

[Pulsebot]

Pushed by [e-mail]:
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

[Narcis Beleuzu [:NarcisB]]

https://hg.mozilla.org/mozilla-central/rev/ee1fdd7df642