Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: df94b6ccbb5363ad11e6a61a6741ddda0c119bd3
https://github.com/WebKit/WebKit/commit/df94b6ccbb5363ad11e6a61a6741ddda0c119bd3
Author: Sosuke Suzuki <[email protected]>
Date: 2026-09-13 (Sun, 13 Sep 2026)
Changed paths:
A JSTests/microbenchmarks/bigint-mul-very-large.js
A JSTests/stress/bigint-multiply-toom3.js
M Source/JavaScriptCore/runtime/JSBigInt.cpp
M Source/JavaScriptCore/runtime/JSBigInt.h
Log Message:
-----------
[JSC] Add Toom-3 multiplication to `JSBigInt`
https://bugs.webkit.org/show_bug.cgi?id=323587
Reviewed by Yusuke Suzuki.
Since 320495@main, JSBigInt multiplies large operands with Karatsuba, whose
O(n^1.58) cost still dominates at a few thousand digits: 4000 x 4000 digits
takes 1.08 ms. Add Toom-3 multiplication for products whose smaller operand has
at least 508 digits, which brings the growth to O(n^1.46). This is a port of
V8's implementation [1], which follows the description on Wikipedia [2].
Toom-3 replaces one product with five products of thirds, and Karatsuba
computes those. Karatsuba halves its operands until they are shorter than 44
digits, so the threshold follows from how often it halves a third. Up to 507
digits, a third has at most 169 digits and is halved twice. The five products
then take as many base-case digit products as Karatsuba does on the whole
operands, and the additions of Toom-3 make it slower. From 508 digits, a third
has at least 170 digits, which Karatsuba rounds up to 176 and halves three
times. That saves about a quarter of the digit products.
An x up to 5/3 the length of y goes to Toom-3 as is, and a longer x is
multiplied in y-sized chunks.
Time per product (us, 64-bit digits, Apple M4, best of 3 x 7 rounds):
digits Before After
480 x 480 34.519 34.486
507 x 507 39.201 39.058
508 x 508 39.174 37.668
600 x 600 51.274 48.453
700 x 700 62.320 62.429
1000 x 1000 117.663 111.336
2000 x 2000 355.545 294.577
4000 x 4000 1075.819 860.870
8000 x 8000 3236.771 2493.739
2000 x 508 156.399 152.821
2000 x 1000 235.766 222.031
10000 x 1000 1172.006 1105.562
12000 x 4000 3250.003 2548.486
Baseline Patched
bigint-mul-very-large 330.2722+-1.1206 ^ 263.5797+-1.2185
^ definitely 1.2530x faster
bigint-mul-large 131.8938+-1.9921 131.1108+-1.3070
bigint-mul-large-unequal 280.3015+-2.7116 279.0286+-1.7460
[1]:
https://source.chromium.org/chromium/chromium/src/+/main:v8/src/bigint/mul-toom.cc
[2]: https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication
Tests: JSTests/microbenchmarks/bigint-mul-very-large.js
JSTests/stress/bigint-multiply-toom.js
Canonical link: https://commits.webkit.org/321013@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
