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

[Brian Burkhalter]

Hello Alan,

Thanks for the comments.

On Mar 8, 2013, at 2:01 AM, Alan Eliasen wrote:

>   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.

In point of fact there is no class introduced and the reason that it looks like there is is the result of the webrev being incomplete for which I apologize. There is a pre-existing class sun.misc.FDBigInt which would be replaced by FDBigInteger. FDBigInt used to be declared within FloatingDecimal.java but was broken out into a separate file by this changeset:

changeset:   5991:17384fc6b31f
user:        ohrstrom
date:        Mon Oct 29 14:12:37 2012 +0100
summary:     8000970: break out auxiliary classes that will prevent multi-core c

If the corrected current patch were applied, the class FDBigInt would be superseded by FDBigInteger. To be a bit more accurate however, FDBigInteger has approximately 792 lines of code (based on cloc) compared with about 330 for FDBigInt, i.e., a net increase of 462 lines.

>   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.
> 
>  Also, swearing and stuff in
> the comments should be filtered out, along with typos like "Chache" etc.

I concur that this should be cleaned up before final submission, if that happens. The version posted for review was intended to expose the code for examination but not expected to be the final version.

>   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.
> 
>   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.

Actually as it stands today the enhanced BigInteger patch for large numbers (4837946) is completely disjoint with the patch 
(7032154) under discussion here. The latter patch would improve the situation for the cases it attempts to address, viz., double/float <-> String conversion, as Dmitry pointed out. If there are better algorithms from the updated BigInteger class which could be applied to these cases, then great, but that could be done later. There should be adequate  time to get all these things done and the sooner this review is completed the sooner things can move along. That is not to say it should move along before it is sufficiently scrutinized and tested, however. The intervening three issues between this one and the BigInteger patch should be able to be dispatched relatively quickly, of course barring unforeseen problems.

>   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.)

If this is the case then there should be a follow on issue to track it. It is possible that any such issue could be addressed directly after the BigInteger patch but I would not want to promise that yet.

>   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.

Well you might be correct, but as mentioned, I have not been working in this area all that long and I am trying to address things in an order which my (hopefully increasing) competence best permits. Although I am sure that you have tested this rigorously I still have to deal with passing it over the usual hurdles and would like to do so with some degree of understanding.

Again, it's not a matter of either-or and not a matter of months. At this point I think we are well down into the order of magnitude of some weeks of delay provided there are no surprises which is a lot less time than this has languished to date.

Brian