Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: cbd15fc88bdeffb4618a464681e03ef1f25bc5b6
https://github.com/WebKit/WebKit/commit/cbd15fc88bdeffb4618a464681e03ef1f25bc5b6
Author: Sosuke Suzuki <[email protected]>
Date: 2026-09-04 (Fri, 04 Sep 2026)
Changed paths:
A JSTests/microbenchmarks/bigint-mul-large-unequal.js
A JSTests/microbenchmarks/bigint-mul-large.js
A JSTests/stress/bigint-multiply-karatsuba.js
M Source/JavaScriptCore/runtime/JSBigInt.cpp
M Source/JavaScriptCore/runtime/JSBigInt.h
Log Message:
-----------
[JSC] Add Karatsuba multiplication to `JSBigInt`
https://bugs.webkit.org/show_bug.cgi?id=323244
Reviewed by Yusuke Suzuki.
JSBigInt multiplies with O(n^2) schoolbook / Comba loops only, so the time per
product grows quadratically with the operand size: 1000 x 1000 digits takes
336 us and 4000 x 4000 takes 5.3 ms. Add Karatsuba multiplication for products
whose smaller operand has at least 44 digits, which brings the growth to
O(n^1.58). This is a port of V8's implementation [1], itself based on Go's
math/big [2].
The threshold is 44 rather than V8's 34 because JSC's Comba base case is faster
than V8's schoolbook: balanced shapes win from 40 digits, but for a long x the
length rounding pads an odd smaller operand by a digit, and at 41 or 43 digits
that padding costs the 2-3% Karatsuba would gain. At 44 no measured shape
regresses. Sizes below the threshold keep the existing paths, and allocation,
sign and normalization in multiplyImpl are unchanged.
Time per product (us, 64-bit digits, Apple M4, best of 3 x 7 rounds):
digits Before After
40 x 40 0.647 0.652
43 x 43 0.738 0.738
44 x 44 0.762 0.714
64 x 64 1.658 1.406
100 x 100 3.987 2.872
256 x 256 23.901 13.113
1000 x 1000 335.548 122.562
4000 x 4000 5337.000 1110.688
1000 x 43 16.089 16.447
1000 x 45 16.870 16.677
10000 x 45 163.054 164.321
10000 x 100 352.316 276.342
Baseline Patched
bigint-mul-large 249.7296+-0.6119 ^ 140.1950+-0.4092
^ definitely 1.7813x faster
bigint-mul-large-unequal 371.3519+-0.7129 ^ 299.9962+-0.7217
^ definitely 1.2379x faster
[1]:
https://source.chromium.org/chromium/chromium/src/+/main:v8/src/bigint/mul-karatsuba.cc
[2]: https://go.dev/src/math/big/nat.go
Tests: JSTests/microbenchmarks/bigint-mul-large-unequal.js
JSTests/microbenchmarks/bigint-mul-large.js
JSTests/stress/bigint-multiply-karatsuba.js
* JSTests/microbenchmarks/bigint-mul-large-unequal.js: Added.
(test):
(next):
* JSTests/microbenchmarks/bigint-mul-large.js: Added.
(test):
(next):
* JSTests/stress/bigint-multiply-karatsuba.js: Added.
(shouldBe):
(refMul):
(makeOperand):
(makeSparseOperand):
(check):
* Source/JavaScriptCore/runtime/JSBigInt.cpp:
(JSC::karatsubaRoundUpLength):
(JSC::karatsubaLength):
(JSC::clampedSubspan):
(JSC::JSBigInt::inplaceAddAndPropagate):
(JSC::JSBigInt::inplaceSubAndPropagate):
(JSC::JSBigInt::karatsubaAbsoluteDifference):
(JSC::JSBigInt::multiplyZeroPadded):
(JSC::JSBigInt::karatsubaMain):
(JSC::JSBigInt::karatsubaChunk):
(JSC::JSBigInt::karatsubaStart):
(JSC::JSBigInt::multiplyKaratsuba):
(JSC::JSBigInt::multiplyDigitsInto):
* Source/JavaScriptCore/runtime/JSBigInt.h:
Canonical link: https://commits.webkit.org/320495@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
