Review: 7032154 - Performance tuning of sun.misc.FloatingDecimal/FormattedFloatingDecimal

[Dmitry Nadezhin]

Alan,

I guess that one of the reasons for all these classes
(MutableBigInteger and SignedMutableBigInteger, FDBigInteger)
is that they are mutable. The immutable class java.math.BigInteger
will require more memory allocations.

The efficient conversion from string to double has some aspects that
are absent in conversion from string to BigInteger.
FDBigInteger class has some methods that are useful in string<->double
conversions:
cmpPow52(int p5, int p2);
addAndCmp(FDBigInteger x,FDBigInteger y);
Their behavior is equivalent tp
this.cmp(valueOfPow52(p5, p2))
this.cmp(x.add(y))
but they do their work without allocation of valueOfPow52(p5, p2) or x.add(y).
These methods speed up efficent string<->double conversion.
I'm not sure that these methods should be in common BigInteger API, as
they make it more complicated.

Alan, I'm sorry that this patch delays your patch.
Nevertheless, the queue of math patches moves now. Thanks to Brian.
I hope that your patch will be considered soon.

Best Regards,
  -Dima

On Fri, Mar 8, 2013 at 2:01 PM, Alan Eliasen <eliasen at mindspring.com> wrote:
> On 03/06/2013 11:55 AM, Brian Burkhalter wrote:
>> The link below has been updated with a few minor changes, notably to
>> use constants from {Double,Float}Consts and to include the link to
>> the OpenJDK issue report. A formatting issue resulting from an awk
>> failure during webrev script execution was also fixed.
>>
>> B.
>>
>> On Feb 28, 2013, at 1:34 PM, Brian Burkhalter wrote:
>>
>>> I forgot that the attachment is not redistributed and that I can
>>> now post on cr.openjdk.java.net so here's the webrev:
>>>
>>> http://cr.openjdk.java.net/~bpb/7032154/
>>>
>>> Begin forwarded message:
>>>
>>>> This concerns the issue
>>>> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7032154.
>
>    I notice that the solution introduces yet another version of
> BigInteger to add to BigInteger, MutableBigInteger,
> SignedMutableBigInteger, and whatever other proprietary classes are
> lurking.  That should give The Fear to anyone who has to maintain this
> code.  The comments for the new class don't contain a justification for
> yet another class other than "A really, really simple bigint package
> tailored to the needs of floating base conversion."  I'm not quite sure
> what that means.  The algorithms are drastically inefficient for large
> numbers.
>
>    (To give an order of magnitude estimate, a BigInteger calculation
> that takes more than 18 hours (that's 64800 seconds) in JDK 1.7 takes
> less than 200 seconds with the BigInteger patches that we've posted.)
>
>    I would posit that all of the work that has been done improving the
> algorithms in BigInteger by several orders of magnitude are vastly more
> significant than introducing yet another BigInteger class with only
> small percentage increases in speed for some small arguments with
> another sun-namespace, non-supported class.
>
>    The comments don't even describe the point of methods.  For example,
> what does multByPow52 do?  Comments like "hope it fits!" don't exactly
> inspire confidence either.
>
>    It should be noted that the multiplication algorithms are O(n^2) and
> will certainly be orders of magnitude slower than the new BigInteger
> algorithms for large numbers.  (Which are stunningly faster than this
> class could ever be.)  This class is unnecessary, and adds huge
> maintenance costs, and is demonstrably orders of magnitude slower for
> large numbers.  If it contains faster algorithms for some small number
> sizes, they should be carefully merged with the pending patches for
> BigInteger that have been posted by Timothy Buktu and myself, otherwise
> they will just make things much slower, harder to maintain, non-portable
> to open projects, and decidedly inferior.  Also, swearing and stuff in
> the comments should be filtered out, along with typos like "Chache" etc.
>
>    The algorithms for base conversions that I have developed, along with
> the drastically faster multiplication and division and exponentiation
> routines that Timothy Buktu and I have developed and posted, will blow
> these timings out of the water for perhaps all but small number sizes.
> If the new class contains algorithms are more efficient for small number
> sizes, that code should be merged into BigInteger, rather than
> introducing yet another limited BigInteger class and all of its
> liabilities and bugs and maintenance effort.
>
>    MutableBigInteger and SignedMutableBigInteger should probably also be
> eliminated.  There is little that they do that couldn't be done
> approximately as efficiently in BigInteger for small numbers, and vastly
> faster for large numbers.  This would also improve the performance of
> BigDecimal by orders of magnitude for large numbers.  (BigDecimal uses
> O(n^2) algorithms from MutableBigInteger which makes division of large
> numbers very slow.)
>
>    This new class is 1252 lines of new code, compared to, say 400 lines
> of well-tested code for my multiplication improvements to BigInteger
> which are orders of magnitude faster for large numbers.  Timothy Buktu's
> stunning FFT multiplication algorithms (added to the existing BigInteger
> class) could add more lines that would turn Java into a best-of-class
> language for large integer work.  That work should be done first.
>
>    Summary:  It would be a drastic mistake to add yet another BigInteger
> class with demonstrably inefficient algorithms for large numbers.  The
> new proprietary and inefficient class sun.misc.FDBigInteger should be
> rejected summarily until the BigInteger algorithm improvements have been
> accepted.  All reviewers should reject a patch that includes this class.
>  After that point, any improvements in the algorithms of FDBigInteger
> should be merged into the existing BigInteger class, and tested against
> the vastly faster algorithms that would then exist, not against the slow
> code in JDK 1.7.  If my code isn't 100 times faster for large numbers,
> (not 100 percent, 100 *times*,) I'll eat my head.  (My tests on big
> numbers are 330 *times* faster easily.  And that's without Timothy
> Buktu's magic FFT routines.)
>
> --
>   Alan Eliasen
>   eliasen at mindspring.com
>   http://futureboy.us/