[webkit-changes] [WebKit/WebKit] 85e669: [JSC] Add dragonbox for double-conversion

Wed Dec 6 09:09:06 PST 2023

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 85e669f3c3e8d80e43a55e4c1c669bb2dd63bf33
      https://github.com/WebKit/WebKit/commit/85e669f3c3e8d80e43a55e4c1c669bb2dd63bf33
  Author: Yijia Huang <yijia_huang at apple.com>
  Date:   2023-12-06 (Wed, 06 Dec 2023)

  Changed paths:
    M Source/JavaScriptCore/runtime/NumberPrototype.cpp
    A Source/WTF/LICENSE-dragonbox.txt
    M Source/WTF/WTF.xcodeproj/project.pbxproj
    M Source/WTF/wtf/CMakeLists.txt
    A Source/WTF/wtf/dragonbox/detail/bits.h
    A Source/WTF/wtf/dragonbox/detail/cache_holder.h
    A Source/WTF/wtf/dragonbox/detail/decimal_fp.h
    A Source/WTF/wtf/dragonbox/detail/div.h
    A Source/WTF/wtf/dragonbox/detail/log.h
    A Source/WTF/wtf/dragonbox/detail/policy.h
    A Source/WTF/wtf/dragonbox/detail/policy_holder.h
    A Source/WTF/wtf/dragonbox/detail/util.h
    A Source/WTF/wtf/dragonbox/detail/wuint.h
    A Source/WTF/wtf/dragonbox/dragonbox.h
    A Source/WTF/wtf/dragonbox/dragonbox_to_chars.cpp
    A Source/WTF/wtf/dragonbox/dragonbox_to_chars.h
    A Source/WTF/wtf/dragonbox/ieee754_format.h
    M Source/WTF/wtf/dtoa.cpp
    M Source/WTF/wtf/dtoa.h
    M Source/WTF/wtf/dtoa/double-conversion.cc
    M Source/WTF/wtf/dtoa/utils.h
    M Tools/TestWebKitAPI/CMakeLists.txt
    M Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
    A Tools/TestWebKitAPI/Tests/WTF/DragonBoxTest.cpp

  Log Message:
  -----------
  [JSC] Add dragonbox for double-conversion
https://bugs.webkit.org/show_bug.cgi?id=264284
rdar://118018415

Reviewed by Yusuke Suzuki.

Dragonbox[1] is a float-to-string conversion algorithm based on a
algorithm Schubfach and inspired by Grisu and Grisu-Exact. The new
conversion brings us JetStream progressions. Currently, the new
conversion only supports ToExponential and ToShortest. This is
because the precision specification is incompatible with finding
the shortest representation (Dragonbox), which requires a completely
different algorithm[2]. The author is working on another repository[3] with more
complete feature set including the precision mode, which seems profitable
and competitive to current double-conversion (tested locally and the results
are shown below).

FP Precision vs double-conversion Precision:

    fPToExponential               -> 0.001016 sec with precision 0
    doubleConversionToExponential -> 0.000950 sec with precision 0
    fPToExponential               -> 0.001358 sec with precision 1
    doubleConversionToExponential -> 0.001199 sec with precision 1
    fPToExponential               -> 0.001309 sec with precision 2
    doubleConversionToExponential -> 0.001226 sec with precision 2
    fPToExponential               -> 0.001135 sec with precision 3  (faster)
    doubleConversionToExponential -> 0.001310 sec with precision 3
    ...
    fPToExponential               -> 0.002514 sec with precision 48 (~15 times faster)
    doubleConversionToExponential -> 0.037997 sec with precision 48
    ...
    fPToExponential               -> 0.002511 sec with precision 99 (~18 times faster)
    doubleConversionToExponential -> 0.045865 sec with precision 99

The overhead for FP is due to the computation of the digits segments for
significand since each segment has fixed size of 9. For example, given a
double

    0.398735806489994737411564074136549606919288635253906250000000

FP's algorithm will compute and iterate each significand segment one by one
with fixed size 9.

    1st significand segment = 398735806
    2nd significand segment = 489994737
    ...

So, even the precision arg is less than 9, the FP would compute the 1st
significand segment with size 9. And this is the major overhead cost
for current FP with small precision arg. On the other side, for double conversion
implemented in our codebase, it computes each significand digit one by one.
And that explains why current FP is slightly slower when precision arg is small
but much faster when precision arg is large.

[1] https://github.com/jk-jeon/dragonbox
[2] https://github.com/jk-jeon/dragonbox/issues/38
[3] https://github.com/jk-jeon/fp

* Source/JavaScriptCore/runtime/NumberPrototype.cpp:
(JSC::JSC_DEFINE_HOST_FUNCTION):
* Source/WTF/WTF.xcodeproj/project.pbxproj:
* Source/WTF/wtf/CMakeLists.txt:
* Source/WTF/wtf/dragonbox/detail/bits.h: Added.
* Source/WTF/wtf/dragonbox/detail/cache_holder.h: Added.
* Source/WTF/wtf/dragonbox/detail/decimal_fp.h: Added.
* Source/WTF/wtf/dragonbox/detail/div.h: Added.
* Source/WTF/wtf/dragonbox/detail/log.h: Added.
* Source/WTF/wtf/dragonbox/detail/policy.h: Added.
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::nearest_to_even::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::nearest_to_odd::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::nearest_toward_plus_infinity::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::nearest_toward_minus_infinity::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::nearest_toward_zero::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::nearest_away_from_zero::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::detail::nearest_always_closed::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::detail::nearest_always_open::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::nearest_to_even_static_boundary::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::nearest_to_odd_static_boundary::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::nearest_toward_plus_infinity_static_boundary::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::nearest_toward_minus_infinity_static_boundary::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::toward_plus_infinity::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::toward_minus_infinity::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::toward_zero::decltype):
(WTF::dragonbox::detail::policy_impl::decimal_to_binary_rounding::away_from_zero::decltype):
* Source/WTF/wtf/dragonbox/detail/policy_holder.h: Added.
(WTF::dragonbox::detail::policy_impl::check_policy_validity):
(WTF::dragonbox::detail::policy_impl::check_policy_list_validity):
(WTF::dragonbox::detail::policy_impl::make_policy_holder):
(WTF::dragonbox::detail::decltype):
* Source/WTF/wtf/dragonbox/detail/util.h: Added.
* Source/WTF/wtf/dragonbox/detail/wuint.h: Added.
* Source/WTF/wtf/dragonbox/dragonbox.h: Added.
(WTF::dragonbox::to_exponential_max_string_length):
(WTF::dragonbox::to_shortest_max_string_length):
(WTF::dragonbox::max_string_length):
(WTF::dragonbox::valid_shortest_representation):
(WTF::dragonbox::count_digits_base10_with_max_17):
(WTF::dragonbox::compute_power_with_max_16):
* Source/WTF/wtf/dragonbox/dragonbox_to_chars.cpp: Added.
* Source/WTF/wtf/dragonbox/dragonbox_to_chars.h: Added.
(WTF::dragonbox::ToExponential):
(WTF::dragonbox::ToShortest):
* Source/WTF/wtf/dragonbox/ieee754_format.h: Added.
* Source/WTF/wtf/dtoa.cpp:
(WTF::numberToString):
* Source/WTF/wtf/dtoa.h:
* Source/WTF/wtf/dtoa/double-conversion.cc:
* Source/WTF/wtf/dtoa/utils.h:
(WTF::double_conversion::validShortestRepresentation):
* Tools/TestWebKitAPI/CMakeLists.txt:
* Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* Tools/TestWebKitAPI/Tests/WTF/DragonBoxTest.cpp: Added.
(TestWebKitAPI::DragonBoxTest::DragonBoxTest):
(TestWebKitAPI::DragonBoxTest::randomFloat):
(TestWebKitAPI::DragonBoxTest::randomDouble):
(TestWebKitAPI::DragonBoxTest::dragonBoxToString):
(TestWebKitAPI::DragonBoxTest::dragonBoxToExponential):
(TestWebKitAPI::DragonBoxTest::doubleConversionToString):
(TestWebKitAPI::DragonBoxTest::doubleConversionToExponential):
(TestWebKitAPI::TEST):

Canonical link: https://commits.webkit.org/271612@main