Fast and cheap (Double|Float)::toString Java algorithm
Raffaello Giulietti
raffaello.giulietti at gmail.com
Fri Feb 5 16:20:53 UTC 2021
Hello,
as a reminder, a Java implementation of Schubfach [1] intended to
replace the current slow and expensive OpenJDK (Double|Float)::toString
algorithm has been discussed, presented and contributed to this mailing
list in several posts. The last implementation is available in pre-Skara
webrev form, as referenced in [2]. On my laptop hardware, the speedup
factor is 17.7x wrt OpenJDK.
Recently, Alexander Bolz translated Schubfach to C++ for the purpose of
comparing the performance of several bin2dec floating-point numbers
algorithms [3].
In the meantime, Junekey Jeon implemented and perfected his own
Dragonbox in C++, a new algorithm based on Schubfach [4]. From [5]: "In
addition to the core idea of Schubfach, Dragonbox utilizes some
Grisu-like ideas to minimize the number of expensive 128-bit × 64-bit
multiplications, at the cost of having more branches and
divisions-by-constants."
In the C++ ecosystem, Schubfach has been the fastest known algorithm
before being gently pushed aside by Dragonbox, as can be seen in the
graphs in [3].
While developing Schubfach back in 2018, I experimented myself with
blending core Schubfach with my own earlier algorithm similar to Grisu.
However, probably due to uncontrollable JIT compilation behavior, I
could not observe any benefit. On the contrary, I measured performance
drops probably because of the added complexity, which is public enemy
nr. 1 for JIT compilers. Therefore, I opted for the simpler current
design that seemed more suitable for (the then 2018 version of) C2.
I hope this can somehow revive this community's interest and confidence
toward Schubfach to definitely supplant the current expensive
(Double|Float)::toString algorithm.
Greetings
Raffaello
----
[1] https://drive.google.com/open?id=1luHhyQF9zKlM8yJ1nebU0OgVYhfC6CBN
[2]
https://mail.openjdk.java.net/pipermail/core-libs-dev/2020-March/065297.html
[3] https://github.com/abolz/Drachennest
[4] https://github.com/jk-jeon/dragonbox
[5]
https://github.com/jk-jeon/dragonbox/blob/master/other_files/Dragonbox.pdf
More information about the core-libs-dev
mailing list