Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 0270fd0a8d77d6e96aa6bfed787cc0ce199e4287
https://github.com/WebKit/WebKit/commit/0270fd0a8d77d6e96aa6bfed787cc0ce199e4287
Author: Yusuke Suzuki <[email protected]>
Date: 2026-08-03 (Mon, 03 Aug 2026)
Changed paths:
M Source/JavaScriptCore/runtime/JSBigInt.cpp
M Source/JavaScriptCore/runtime/JSBigInt.h
Log Message:
-----------
[JSC] Make the first corrective subtract in JSBigInt Crandall reduction
branch-free
https://bugs.webkit.org/show_bug.cgi?id=320860
rdar://183888656
Reviewed by Yijia Huang.
Crandall reduction does correction loop at the end. Typically it runs
factor q times. But it turned out that this is really costly, and branch miss
of taking this loop or not becomes huge cost so far.
This patch adds reduceOnce. This *attempts* to perform r - b without
asking actually necessary. And the subtract result says whether we
needed to do it at all: if r is smaller than b, then we didn't need to
do it. So basically it is doing greaterThanOrEqual and inplaceSub at the
same time like what CPU's cmp operation does (in fact it is sub). And
based on this subtract result, we select
r[i] = subtract ? difference[i] : r[i];
without a branch (csel will be used).
So ultimately whether this peeling loop is effective relies on how many
times we need to run the correction loop. This is bound by q, and when q
= 1, then we do not need this loop at all. This is when the divisor exceeds
half of 2^(n * digitBits), which can be checked with `b.back() >> (digitBits -
1)`.
So otherwise, running this is worth doing.
* Source/JavaScriptCore/runtime/JSBigInt.cpp:
(JSC::JSBigInt::reduceOnce):
(JSC::JSBigInt::cachedModFoldImpl):
* Source/JavaScriptCore/runtime/JSBigInt.h:
Canonical link: https://commits.webkit.org/318506@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
