Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 9a3812428186ab2724c5d609650d54bd46801403
https://github.com/WebKit/WebKit/commit/9a3812428186ab2724c5d609650d54bd46801403
Author: Sosuke Suzuki <[email protected]>
Date: 2026-09-19 (Sat, 19 Sep 2026)
Changed paths:
A JSTests/microbenchmarks/bigint-mul-huge.js
A JSTests/stress/bigint-multiply-fft.js
M Source/JavaScriptCore/runtime/JSBigInt.cpp
M Source/JavaScriptCore/runtime/JSBigInt.h
Log Message:
-----------
[JSC] Add Schönhage-Strassen FFT multiplication to `JSBigInt`
https://bugs.webkit.org/show_bug.cgi?id=324209
Reviewed by Yusuke Suzuki.
Since 321013@main, JSBigInt multiplies large operands with Toom-3, whose
O(n^1.46) cost still dominates near the length limit: 8000 x 8000 digits takes
2.46 ms. Add FFT-based multiplication after Schönhage and Strassen, which
brings that to 1.25 ms. This is a port of V8's implementation [1], which
follows Lüders [2].
It is used when the operands have at least 2177 digits combined and the
smaller one has at least 586. The cost of the transform depends only on the
combined length, and from 2177 digits it stays ahead of Toom-3 on operands of
equal length. Toom-3 multiplies a longer x in y-sized chunks, so it gets
cheaper per digit as y shrinks, and below 586 digits it still wins at the
longest products that maxLengthBits allows.
Residues of 200 digits or more are multiplied by a recursive FFT, which only
a product above the current maxLengthBits reaches. That path was exercised
locally by lowering the constant.
digits Before After
1000 x 1000 110.227 108.730
1089 x 1089 119.820 119.867
1500 x 1500 204.891 167.713
2000 x 2000 297.453 238.344
4000 x 4000 840.746 555.687
8000 x 8000 2458.245 1245.514
8000 squared 2444.357 1093.432
4000 x 585 345.252 346.329
4000 x 586 338.953 271.954
15798 x 586 1285.881 1266.003
10000 x 3000 2067.238 969.008
Baseline Patched
bigint-mul-very-large 264.4264+-0.8554 ^ 176.4463+-1.1920
^ definitely 1.4986x faster
bigint-mul-large 130.5051+-0.4806 ? 130.7593+-0.7347
?
bigint-mul-huge 261.4237+-1.2069 ^ 137.6654+-1.2630
^ definitely 1.8990x faster
bigint-mul-large-unequal 279.1744+-1.1593 ? 279.3819+-0.9790
?
* Source/JavaScriptCore/runtime/JSBigInt.cpp:
(JSC::shouldUseFFT):
(JSC::FFT::addDigitAndPropagate):
(JSC::FFT::subtractDigitAndPropagate):
(JSC::FFT::modFnHelper):
(JSC::FFT::modFn):
(JSC::FFT::modFnDoubleWidth):
(JSC::FFT::sumDiff):
(JSC::FFT::shiftModFnLarge):
(JSC::FFT::shiftModFn):
(JSC::FFT::computeParameters):
(JSC::FFT::computeParametersInner):
(JSC::FFT::shouldDecrementM):
(JSC::FFT::getParameters):
(JSC::FFT::copyAndZeroExtend):
(JSC::FFT::shouldBeNegative):
(JSC::JSBigInt::FFTContainer::FFTContainer):
(JSC::JSBigInt::FFTContainer::backwardFFT):
(JSC::JSBigInt::FFTContainer::part):
(JSC::JSBigInt::FFTContainer::part const):
(JSC::JSBigInt::FFTContainer::temp):
(JSC::JSBigInt::FFTContainer::doubleWidthTemp):
(JSC::JSBigInt::FFTContainer::startDefault):
(JSC::JSBigInt::FFTContainer::start):
(JSC::JSBigInt::FFTContainer::forwardFFT):
(JSC::JSBigInt::FFTContainer::forwardFFTRecurse):
(JSC::JSBigInt::FFTContainer::normalizeAndRecombine):
(JSC::JSBigInt::FFTContainer::counterWeightAndRecombine):
(JSC::JSBigInt::FFTContainer::pointwiseMultiply):
(JSC::JSBigInt::multiplyFFT):
(JSC::JSBigInt::multiplyDigitsInto):
* Source/JavaScriptCore/runtime/JSBigInt.h:
Canonical link: https://commits.webkit.org/321444@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
