2005652 - Reduce mozilla::Span overhead in BigInt

Status: RESOLVED FIXED

(Core :: JavaScript Engine, task, P1)

Description

[Iain Ireland [:iain]]

Our BigInt implementation uses mozilla::Span for bounds checking when accessing digits. Profiling the bigint-noble-ed25519 subtest in JS3, more than 25% of the total time is spent inside the two implementations of digits().

On my machine, V8 scores ~60 on this subtest. We score ~45. If I rewrite digits to index directly (without bounds checking) then our score increases to ~65. Adding MOZ_RELEASE_ASSERT(idx < digitLength()) decreases that to ~55.

I think part of the issue here may be these asserts in extent_type this assert in storage_type (deep in the implementation of Span; thanks to mccr8 for pointing out that my profile didn't match my link). At the very least, it seems reasonable to avoid that cost.

js-perf-next: Figure out how many release asserts we're comfortable removing here.

Comment 1

[Iain Ireland [:iain]]

It looks like V8 does not do bounds checking in release. So in the apples-to-apples comparison we're faster (at least on my machine).

Comment 2

[Andrew McCreight [:mccr8]]

For completeness, it looks like WebKit uses std::span<> for their digits representation (and like Chromium I think they ship hardened STL so it'll be bounds checked): https://github.com/WebKit/WebKit/blob/main/Source/JavaScriptCore/runtime/JSBigInt.h#L462

Comment 3

[Iain Ireland [:iain]]

It's probably not a coincidence, then, that I get similar results on my machine for jsc and sm-with-span (score of ~45).

Comment 4

[Andrew McCreight [:mccr8]]

I hadn't looked at Span before, but reading it now, it looks like that check is dealing with two specific weird internal representation cases for Spans (an empty span and one with size_t::max or whatever length) which do look like they'd be hard to elide. I think Span has to deal with that weirdness to support fixed and dynamic length spans, but BitInt only cares about dynamic length. Furthermore, digit() and set_digit() basically are array lookup and set, so there's not much going on, so it does feel like Span is not the right thing for those two methods.

Comment 5

[Andrew McCreight [:mccr8]]

I guess I'd recommend you add a new private method that does hasInlineDigits() ? inlineDigits_ : heapDigits_ and has a return type Digit* and then manually write digit() and set_digit() including the bounds checks. The methods are trivial enough it shouldn't be too bad. Then you could remove the "real" bounds checks later if it is a problem.

Comment 6

[Andrew McCreight [:mccr8]]

Attachment: Bug 2005652 - Eliminate mozilla::Span overhead for BigInt::digit() and set_digit().

The Span constructor does some release asserts to ensure that the constraints
of its internal representation are satisfied. If you are immediately throwing
out the Span, this can be expensive. This patch reimplements those two methods
to avoid that.

Comment 7

[Andrew McCreight [:mccr8]]

Nika said we might be able to just drop the release assert in the constructor.

Comment 8

[Iain Ireland [:iain]]

I tested a patch that does manual bounds checking (with MOZ_RELEASE_ASSERT) instead of using mozilla::Span. The numbers in CI are if anything better than what I was seeing locally: a 60%+ improvement in our score across multiple platforms.

Comment 9

[Andrew McCreight [:mccr8]]

It looks like a bug was already on file for eliminating this release assert. It doesn't seem to correspond to anything in std::span so I'll see if glandium is okay with getting rid of it.

Comment 10

[Andrew McCreight [:mccr8]]

From bug 1730080:

(In reply to Mayank Bansal from comment #7)

Also seems to have expectedly improved Jetstream3-bigint-noble-ed25519-Geometric
121% on Windows (!)
29% on Linux
28% on Android

On Windows, the score went from 30 to 66.

Do you want to close this now, or leave it open? I guess further improvements could be had by dropping the bounds check if that's really desired.

Comment 11

[Iain Ireland [:iain]]

The improvements from removing the assertion are good, but I was seeing even bigger improvements in try with my previous patch that stopped using Span and added MOZ_ALWAYS_INLINE to digit/setDigit. I ran a couple more patches through perfherder, and it looks like inlining gets another ~60-70% percent on Mac/Linux. (The bigger improvement on Windows from the initial patch might imply that we started inlining things there without hinting.) Indexing manually (with a release assert, but no Span) appears to get another ~10% on top of that.

At the very least, I think I'll put up the inlining patch.

Comment 12

[Iain Ireland [:iain]]

Attachment: Bug 2005652: Inline BigInt::digit/setDigit r=#spidermonkey-reviewers

This improves bigint-noble-ed25519 by 60-70% on Mac/Linux.

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/f72b853afcad
https://hg.mozilla.org/integration/autoland/rev/56ddf133bc8a
Inline BigInt::digit/setDigit r=spidermonkey-reviewers,mgaudet

Comment 14

[Serban Stanca [:SerbanS]]

https://hg.mozilla.org/mozilla-central/rev/56ddf133bc8a

Comment 15

[Mayank Bansal]

77% (!) improvement on Jetstream3-bigint on LINUX.
The total improvement in score from this series of patches is:
10 --> 23 (~120%). Which is inline with the improvements on Windows.

Comment 16

[Alex Finder]

(In reply to Pulsebot from comment #13)

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/f72b853afcad
https://hg.mozilla.org/integration/autoland/rev/56ddf133bc8a
Inline BigInt::digit/setDigit r=spidermonkey-reviewers,mgaudet

Perfherder has detected a browsertime performance change from push 56ddf133bc8abaaef013acc77971c651f8c24278.

No action is required from the author; this comment is provided for informational purposes only.

Improvements:

Ratio	Test	Platform	Options	Absolute values (old vs new)	Performance Profiles
70%	jetstream3 bigint-noble-ed25519-Geometric	linux1804-64-shippable-qr	fission webrender	13.26 -> 22.55	Before/After
43%	jetstream3 bigint-noble-ed25519-Average	linux1804-64-shippable-qr	fission webrender	361.36 -> 204.41	Before/After
43%	jetstream3 bigint-noble-ed25519-Worst	linux1804-64-shippable-qr	fission webrender	366.34 -> 209.83	Before/After
37%	jetstream3 bigint-noble-ed25519-First	linux1804-64-shippable-qr	fission webrender	405.22 -> 254.54	Before/After

Need Help or Information?

If you have any questions, please reach out to [e-mail]. Alternatively, you can find help on Slack by joining #perf-help, and on Matrix you can find help by joining #perftest.

Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests.