Review: 7032154 - Performance tuning of sun.misc.FloatingDecimal/FormattedFloatingDecimal (original) (raw)

Alan Eliasen eliasen at mindspring.com
Fri Mar 8 10:01:38 UTC 2013

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/viewbug.do?bugid=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/

More information about the core-libs-dev mailing list