RFR 4641897: Faster string conversion of large integers

[Brian Burkhalter]

On Jun 21, 2013, at 9:56 AM, Alan Eliasen wrote:

>   Yes, as noted in the code comments and in my comments on this list,
> it would be possible to do something fancier, perhaps using Future.
> This code was intended to be as simple and understandable as possible,
> to rapidly give an asymptotically much faster algorithm that would have
> minimal review impact but significant performance improvement. […]

Indeed it was important to simplify the review effort to get things moving.

>   […] However, it became clear that keeping a cache significantly
> improved performance at the cost of holding on to some memory with the
> idea that if you print one big number, you're likely going to print
> another big number at some time during the life of the VM.

This seems like an eminently reasonable assumption.

>   […]
> 
>   If profiling shows that this is a bottleneck, we can revise it, but I
> didn't see evidence of that.  It was suggested to make some of these
> algorithms multi-threaded, but that was soundly rejected on this list
> for this phase.  Perhaps in a later phase when the algorithms become
> multi-threaded, the cache can be revised.

As these patches had been stalled for so long it was my intent to streamline their being integrated in the Java 8 source base with the idea that once in place further refinements could be made. I think the main open problem for this patch and the Karatsuba one just integrated this week is to determine algorithm crossover thresholds which are not going to provoke performance degradations for certain intermediate bit lengths on the platforms of interest. Any suggestions on this topic would also be appreciated.

>   The Schoenhage recursive base conversion code is not triggered unless
> numbers are already significantly largish, so it won't affect
> performance of smaller numbers, but the algorithm's much-improved
> efficiency will make it faster for the larger numbers that trigger it.

This is an excellent point: improving the radix cache handling only affects the large number cases which will already be vastly faster that what would obtain without this patch.

Brian