Fast and cheap (Double|Float)::toString Java algorithm

[Raffaello Giulietti]

Hi Suminda,

as I explained back in February, I already experimented blending 
Schubfach with a variant of Grisu back in 2018. Contrary to my 
expectations, I observed noticeable performance drops wrt pure 
Schubfach. I didn't explore any further, but I think that the more 
complex control logic required by the blend makes it harder for a JIT 
compiler to optimize.

Thus, I prefer to wait until my own contribution has been reviewed and 
integrated (if at all) before adding complexity that might not be 
beneficial in Java.

(Junekey measured that a blend *is* beneficial in C++, though. But it's 
somehow hard to compare a static AOT compilation, as done in C++, and a 
JIT compilation, as done on the JVM.)


Greetings
Raffaello



On 2021-05-04 18:14, Suminda Sirinath Salpitikorala Dharmasena wrote:
> Hello,
> 
> I hope everything is well with you.
> 
> Due to other commitments this work has stalled.
> 
> I was planning to implement:
> - fast to string conversion
> - fast string parsing
> - fast formatting
> - fast search
> - fast sort
> - fast templating
> - fast buffers
> 
> The code I have done so far is here: https://github.com/sirinath/moby 
> <https://github.com/sirinath/moby>
> 
> Wondering if someone can take this forward until I have more time in my 
> hand.
> 
> Suminda
> 
> On Sat, 6 Feb 2021 at 09:50, Suminda Sirinath Salpitikorala Dharmasena 
> <sirinath1978m at gmail.com <mailto:sirinath1978m at gmail.com>> wrote:
> 
>     Hello,
> 
>     I am working on a port of DragonBox to Java. If there is interest in
>     contributing this is most welcome.
> 
>     Suminda
> 
>     On Fri, 5 Feb 2021 at 21:51, Raffaello Giulietti
>     <raffaello.giulietti at gmail.com
>     <mailto:raffaello.giulietti at gmail.com>> wrote:
> 
>         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
>         <https://drive.google.com/open?id=1luHhyQF9zKlM8yJ1nebU0OgVYhfC6CBN>
>         [2]
>         https://mail.openjdk.java.net/pipermail/core-libs-dev/2020-March/065297.html
>         <https://mail.openjdk.java.net/pipermail/core-libs-dev/2020-March/065297.html>
>         [3] https://github.com/abolz/Drachennest
>         <https://github.com/abolz/Drachennest>
>         [4] https://github.com/jk-jeon/dragonbox
>         <https://github.com/jk-jeon/dragonbox>
>         [5]
>         https://github.com/jk-jeon/dragonbox/blob/master/other_files/Dragonbox.pdf
>         <https://github.com/jk-jeon/dragonbox/blob/master/other_files/Dragonbox.pdf>
>