Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 39b1bb9cfc85b74fa5ead850deee710547b2df71
https://github.com/WebKit/WebKit/commit/39b1bb9cfc85b74fa5ead850deee710547b2df71
Author: Yusuke Suzuki <[email protected]>
Date: 2026-07-30 (Thu, 30 Jul 2026)
Changed paths:
A JSTests/microbenchmarks/bigint-add-large.js
A JSTests/microbenchmarks/bigint-mod-cached-large.js
A JSTests/microbenchmarks/bigint-mod-cached.js
A JSTests/microbenchmarks/bigint-sub-large.js
A JSTests/stress/bigint-cached-mod-fixed-size.js
A JSTests/stress/bigint-multiply-comba.js
M Source/JavaScriptCore/runtime/JSBigInt.cpp
M Source/JavaScriptCore/runtime/JSBigInt.h
Log Message:
-----------
[JSC] Deploy Comba multiplication more broadly
https://bugs.webkit.org/show_bug.cgi?id=320676
rdar://183655373
Reviewed by Yijia Huang.
1. Introduce cachedModFixed, which is basically 1:1 version of cachedMod
but it uses fixed size for input so that it can streamline the
computation, making it significantly faster. We use N=4 threshold to
expand this code to handle small division incredibly faster.
2. Previously, we were using Comba multiplication only for NxN fixed
sized multiplication. But this patch extends and applies broadly. We
add multiplyComba. We rename old multiplyComba to multiplyCombaFixed.
multiplyComba can handle non NxN fixed sized cases.
3. Rename Textbook to Schoolbook.
4. multiplySpecialLow and multiplySpecialHigh are used for division
specially so far. And we made it using Comba multiplication as well.
Note that Comba multiplication is simple idea.
a6 a5 a4 a3 a2 a1 a0
x b6 b5 b4 b3 b2 b1 b0
--------------------------------------
a6b0 a5b0 a4b0 a3b0 a2b0 a1b0 a0b0
a6b1 a5b1 a4b1 a3b1 a2b1 a1b1 a0b1
a6b2 a5b2 a4b2 a3b2 a2b2 a1b2 a0b2
a6b3 a5b3 a4b3 a3b3 a2b3 a1b3 a0b3
a6b4 a5b4 a4b4 a3b4 a2b4 a1b4 a0b4
a6b5 a5b5 a4b5 a3b5 a2b5 a1b5 a0b5
a6b6 a5b6 a4b6 a3b6 a2b6 a1b6 a0b6
-----------------------------------------------------------------
Schoolbook approach is computing a0b0 -> a6b0, and then a0b1 -> a6b1 and
adding and offering a carry to the next digit. But this is slow due to
repeated load and store to the different sites. Comba multiplication is
computing column-based: a4b0 -> a0b4 for example, and adding them. And
accumulator is offering the carry to the next phase and adding all of them.
Tests: JSTests/microbenchmarks/bigint-add-large.js
JSTests/microbenchmarks/bigint-mod-cached-large.js
JSTests/microbenchmarks/bigint-mod-cached.js
JSTests/microbenchmarks/bigint-sub-large.js
JSTests/stress/bigint-cached-mod-fixed-size.js
* JSTests/microbenchmarks/bigint-add-large.js: Added.
(test):
(next):
* JSTests/microbenchmarks/bigint-mod-cached-large.js: Added.
(test):
* JSTests/microbenchmarks/bigint-mod-cached.js: Added.
(test):
* JSTests/microbenchmarks/bigint-sub-large.js: Added.
(test):
(next):
* JSTests/stress/bigint-cached-mod-fixed-size.js: Added.
(shouldBe):
(refMod):
(checkRepeated):
* JSTests/stress/bigint-multiply-comba.js: Added.
(shouldBe):
(refMul):
(makeOperand):
(check):
* Source/JavaScriptCore/runtime/JSBigInt.cpp:
(JSC::DigitColumnAccumulator::low const):
(JSC::DigitColumnAccumulator::fitsInLow const):
(JSC::CombaAccumulator::computeColumn):
(JSC::CombaAccumulator::pass):
(JSC::JSBigInt::multiplyCombaFixed):
(JSC::JSBigInt::multiplySchoolbook):
(JSC::JSBigInt::multiplySpecialLow):
(JSC::JSBigInt::multiplySpecialHigh):
(JSC::shouldUseComba):
(JSC::JSBigInt::multiplyComba):
(JSC::multiplySpecialColumn):
(JSC::JSBigInt::multiplySpecialHighFixed):
(JSC::JSBigInt::multiplySpecialLowFixed):
(JSC::JSBigInt::multiplyImpl):
(JSC::JSBigInt::divideSchoolbook):
(JSC::JSBigInt::remainderSameSize):
(JSC::JSBigInt::divideImpl):
(JSC::JSBigInt::addDigits):
(JSC::JSBigInt::multiplyDigits):
(JSC::JSBigInt::divideDigits):
(JSC::JSBigInt::cachedModMakeInverse):
(JSC::JSBigInt::cachedModFixed):
(JSC::JSBigInt::cachedMod):
(JSC::JSBigInt::remainderImpl):
(JSC::JSBigInt::digitAdd3):
(JSC::JSBigInt::digitSub2):
(JSC::JSBigInt::addSchoolbook):
(JSC::JSBigInt::absoluteAdd):
(JSC::JSBigInt::subSchoolbook):
(JSC::JSBigInt::absoluteSub):
(JSC::CombaAccumulator::mac): Deleted.
(JSC::CombaAccumulator::storeAndShift): Deleted.
(JSC::JSBigInt::multiplyTextbook): Deleted.
(JSC::JSBigInt::divideTextbook): Deleted.
(JSC::JSBigInt::addTextbook): Deleted.
(JSC::JSBigInt::subTextbook): Deleted.
* Source/JavaScriptCore/runtime/JSBigInt.h:
Canonical link: https://commits.webkit.org/318298@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
