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