Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: e2ffc55c56bd78ac2243d1e26c7844ef731df53c
https://github.com/WebKit/WebKit/commit/e2ffc55c56bd78ac2243d1e26c7844ef731df53c
Author: Sosuke Suzuki <[email protected]>
Date: 2026-10-09 (Fri, 09 Oct 2026)
Changed paths:
A JSTests/microbenchmarks/bigint-to-string-large.js
A JSTests/stress/bigint-to-string-divide-and-conquer.js
M Source/JavaScriptCore/runtime/JSBigInt.cpp
M Source/JavaScriptCore/runtime/JSBigInt.h
Log Message:
-----------
[JSC] Add divide-and-conquer `toString` to `JSBigInt`
https://bugs.webkit.org/show_bug.cgi?id=326633
Reviewed by Yusuke Suzuki.
JSBigInt::toStringGeneric divides the whole value by a one-digit divisor once
per digit of the value, so its cost is quadratic in the length. A value of
16384 digits, the longest that maxLengthBits allows, takes 664 ms.
Add the divide-and-conquer conversion, which brings that to 34 ms. This is a
port of V8's implementation [1]. It divides the value by a power of the radix
of about half its length, and does the same with the quotient and the
remainder. Each divisor is the square of the one below and is computed once.
It is used from 12 digits, and a chunk below 12 digits is converted with
one-digit divisions, which are faster there.
V8 divides with Barrett division. JSBigInt does not have it, so this uses
divideDigitsInto, which takes Burnikel-Ziegler division, added in 322437@main,
for long operands. A power of an even radix ends in zero digits, so only the
digits above them are divided, as GMP does. The divisors, quotients and
remainders of all levels share one buffer.
x.toString() in microseconds on x86-64. toString(3) and toString(36) of 4000
digits take 4930 and 4014 instead of 40280 and 40287.
digits Before After
8 1.097 1.097
12 1.764 1.580
16 2.505 2.252
24 4.293 3.508
32 6.451 5.229
64 18.166 12.759
128 56.003 31.456
256 191.966 81.817
1000 2561.212 514.362
4000 39616.585 3910.691
16384 663919.687 34177.542
Baseline Patched
bigint-to-string-large 194.1975+-0.3201 ^ 83.8116+-0.1203
^ definitely 2.3171x faster
[1]:
https://source.chromium.org/chromium/chromium/src/+/main:v8/src/bigint/tostring.cc
Tests: JSTests/microbenchmarks/bigint-to-string-large.js
JSTests/stress/bigint-to-string-divide-and-conquer.js
* JSTests/microbenchmarks/bigint-to-string-large.js: Added.
(test):
(next):
* JSTests/stress/bigint-to-string-divide-and-conquer.js: Added.
(shouldBe):
(makeOperand):
(36.2000.string_appeared_here.string_appeared_here.repeat):
(36.2000.const.low.of.exponents.string_appeared_here.string_appeared_here.repeat.high.low.1.string_appeared_here.string_appeared_here.repeat):
(36.2000.const.low.of.exponents.last.repeat.high.low.string_appeared_here.repeat):
(36.2000.const.low.of.exponents.last.repeat):
(last.repeat):
* Source/JavaScriptCore/runtime/JSBigInt.cpp:
(JSC::JSBigInt::ToStringFormatter::format):
(JSC::JSBigInt::ToStringFormatter::ToStringFormatter):
(JSC::JSBigInt::toStringGeneric):
* Source/JavaScriptCore/runtime/JSBigInt.h:
Canonical link: https://commits.webkit.org/323232@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
