In my book Java
Performance Tuning, I considered efficient ways to convert numbers
to strings, and I provided conversion algorithms that are faster than
those released with the Java SDK (up to and including version 1.3). In
this article, I'll consider how to format double
s using a
variation of that conversion algorithm, and show that the conversion
of numbers with formatting can be faster than the original unformatted
conversion.
First, let's look at how the SDK converts double
s to
strings and see why that procedure is slow. Calling
Double.toString(double)
to convert a double
value to a string immediately creates an instance of
java.lang.FloatingDecimal
, a class that is private to the
java.lang
package. FloatingDecimal
is the
internal SDK class that provides all the logic necessary to handle
floating point numbers. If you look at the source code for this class,
you will see that converting floating point numbers to strings appears
to be horrendously complicated. The algorithm needs to deal with
several special cases: infinity, infinity, notanumber, 0.0, as
well as digits before and after the decimal point, exponential values,
and rounding accuracy. In addition, the SDK conversion algorithm works
out the minumum number of digits necessary to identify uniquely the
underlying bitstorage value.
This last factor is a little subtle: I'll illustrate it with an
example. The number 5.39E322 is relatively close to the smallest
IEEE754 double
value. The underlying double
representation cannot actually hold the full accuracy of a number that
small (note that this representation is not Javaspecific: all
IEEE754 floating point numbers in all languages have the same
limitations). Instead the double
value is held as
5.4E322. The number 5.41E322 is also stored to the same accuracy,
resulting in the same number, i.e. the code
double d1 = 5.39E322D;
double d2 = 5.41E322D;
System.out.println(d1);
System.out.println(d2);
System.out.println(d2==d1);
produces the output
5.4E322
5.4E322
true
In fact, the underlying bitstored number is closer to
5.396039603960396E322. However, the SDK algorithm correctly
identifies that all these numbers are stored as the same underlying
value, and that there is no other close double
value that
can be stored which requires more than one digit of accuracy to be
shown, i.e. 5.4E322 uniquely identifies the underlying
double
value, while using the minimum number of
digits. (The next nearest double
value is 5.4455E322
which is represented by 5.43E322 using the SDK conversion algorithm,
and this double
would be assigned for all values between
5.42E322 and 5.45E322.)
As you can see, converting double
s to strings is a
nuanced affair requiring lots of work. That explains why the SDK is so
slow to convert them. In my book, I presented an alternative algorithm
to convert double
s to strings. The algorithm works by
determining the magnitude of the double
(there is a rapid
algorithm to do this using some of the bits of the
double
), then scaling the double
value into
a long
and converting the long
value using
another efficient algorithm. Essentially, the algorithm looks similar
to
double example = 3.14159D;
//magnitude is 0 for 3.14159
long magnitude = magnitude(example);
// scaling_factor could be 1.0E18 here
long scaled = example * scaling_factor;
//now print the long, inserting a decimal point
//after the (magnitude+1)th digit.
...
The long
tostring conversion algorithm I use is also
faster than the SDK version, as I use an algorithm which successively
strips off the highest digit, thus avoiding the use of an intermediate
char
array or StringBuffer
to hold a
partially built string. (The documented code for all algorithms is
included in the source code for this article.) The nth digit
of a particular long
can be obtained using a relatively
simple formula
//Input assumes l is positive. If negative, then pass l.
//Note that if negating, should treat Long.MAX_VALUE specially,
//as that would overflow when negated.
public static long getNthDigit(long l, int n)
{
//Obviously, if you are successively accessing digits, you should
//inline this code, and avoid repeatedly calling tenthpower(long)
//since you only need to determine the tenthpower(long) for the
//first digit, then each subsequent digit has a tenthpower(long)
//which is the previous tenthpower(long) divided by 10.
return (l/(tenthPower(l)/l_tenthPower[n1]))%10;
}
static long[] l_tenthPower = {1, 10L, 100L, 1000L, 10000L, 100000L,
1000000L, 10000000L, 100000000L, 1000000000L, 10000000000L,
100000000000L, 1000000000000L, 10000000000000L, 100000000000000L,
1000000000000000L, 10000000000000000L, 100000000000000000L,
1000000000000000000L,
};
private static long tenthPower(long l)
{
if (l < 10L) return 1;
else if (l < 100L) return 10L;
else if (l < 1000L) return 100L;
else if (l < 10000L) return 1000L;
else if (l < 100000L) return 10000L;
else if (l < 1000000L) return 100000L;
else if (l < 10000000L) return 1000000L;
else if (l < 100000000L) return 10000000L;
else if (l < 1000000000L) return 100000000L;
else if (l < 10000000000L) return 1000000000L;
else if (l < 100000000000L) return 10000000000L;
else if (l < 1000000000000L) return 100000000000L;
else if (l < 10000000000000L) return 1000000000000L;
else if (l < 100000000000000L) return 10000000000000L;
else if (l < 1000000000000000L) return 100000000000000L;
else if (l < 10000000000000000L) return 1000000000000000L;
else if (l < 100000000000000000L) return 10000000000000000L;
else if (l < 1000000000000000000L) return 100000000000000000L;
else return 1000000000000000000L;
}
Related Reading Java Performance Tuning 
By successively stripping off the highest digit, the numbers are printed or appended in order. This means that there is no need for any intermediate temporary structures when printing numbers using my method. This can be a great help when printing large amounts of data to streams. Avoiding the temporary objects that are generated during the normal SDK numbertostring conversions both speeds up the conversion and avoids garbage collection further down the line.
In my original double
tostring conversion algorithm,
I didn't bother with printing the shortest unique representation of
the double
. In fact the algorithm always prints out all
the digits available, up to about 15 decimal places. During the
conversion, however, rounding errors mean the last few decimal places
are not necessarily correct. Therefore, if you need full accuracy to
the 15th decimal place, then you should not be using my conversion
algorithm to print double
values. I'd also argue that you
shouldn't be using double
s at all if that is your
requirement: instead math manipulation packages and
BigDecimal
are probably more appropriate for your
problem.

One interesting point is that for printing formatted
numbers, my algorithm could run even quicker. Normally you want to
print fewer than 15 decimal places, and my algorithm runs faster the
fewer digits it needs to output. This contrasts with the SDK number
formatting which always takes longer to format double
s.
The SDK uses the java.text.DecimalFormat
class to print
formatted floating point numbers, and the conversion algorithm first
uses the default SDK double
tostring conversion, then
parses and formats the resulting string characters to create the
formatted string. For example, to format a double
with
four digits after the decimal point and thousands separators, you
could use the following SDK code:
DecimalFormat format = new DecimalFormat("#,##0.0000");
FieldPosition f = new FieldPosition(0);
StringBuffer s = new StringBuffer();
format.format(myDouble, s, f);
java.text.DecimalFormat
also supports
internationalized formatting. But this internationalized support turns
out to be remarkably easy to manage for the most frequently used
formatting, which needs internationalization of only a few
elements:
Accessing these values for a particular locale can be managed
through the DecimalFormat
class. For the conversion
algorithm, changing the decimal character and the prefix and suffix
characters is obviously strightforward. Adding in the thousands
separator is slightly more challenging. You need to know the distance
from the decimal point of the current digit as you are printing, but
this distance is given by the magnitude of the current digit being
printed, and it is simple to keep track of the magnitude: you
determine the magnitude of the full double
as part of the
printing algorithm, and you can simply decrement the magnitude by one
for each digit printed. The decision to print a thousandsseparator
character is then straightforward.
if (d_magnitude % numDigitsSeparated == (numDigitsSeparated1))
s.append(thousandsSeparator);
To avoid having any thousands separator at all you could write
another identical method without the above logic, or you could simply
use a large value for numDigitsSeparated
, e.g
Integer.MAX_VALUE
.
The proof of the pudding is in the eating, so let's test out this effort. In the following table, I've used several Sun VMs on four tests:
StringBuffer.append(double)
method
(which calls Double.toString()
)java.text.DecimalFormat.format()
methodI've normalized all measured times to the SDK 1.2 VM with Java Implementation Testing (JIT), running test 1. (That is, all measured times are divided by the measured time for the 1.2 VM running test 1.) Times are the averages over several test runs. HotSpot times are shown for a second run of tests without exiting the VM, so that the servertuned VM has time for its optimizations to kick in.
Table 1: Times for converting doubles to strings using various methods and VMs. 

 1.2 VM  1.2 noJIT VM  1.3 VM  HotSpot 2.0 VM (2nd run) 
test 1: proprietary printing  100.0%  420.1%  114.2%  82.0% 
test 2: proprietary with formatting  115.1%  414.4%  85.4%  93.8% 
test 3: StringBuffer.append(double)  282.2%  926.1%  265.1%  199.8% 
test 4: java.text.DecimalFormat.format()  456.1%  1690.2%  409.6%  303.7% 
The test results show several interesting things. Firstly, the two tests using my algorithms produced relatively close timings in each VM, but which test was the faster depended on the VM being used. Even the two HotSpot VMs (the standard clienttuned 1.3 VM and the servertuned HotSpot 2.0) produced a different order for the test timings. To me, this indicates that there are further possible optimizations in both sets of code (test1 and test2), and that the two HotSpot VMs are managing to apply two different (overlapping) sets of optimizations. Looking at the code, I would not be at all surprised to be able to tease out a 10% improvement by some refactoring of nested tests. The time taken to format numbers depends on the number of digits being printed. I have used a format with four decimal places, but a separate test formatting to two decimal places showed test2 always running faster than test1 for all VMs.
Secondly, all the tests clearly show my algorithms outperforming the SDK conversion methods by a factor of two to four. Although the tests did not show the proprietary formatting algorithm to be consistently faster than the proprietary nonformatting algorithm, which I had actually expected, nevertheless the tests do show that both the proprietary algorithms are always significantly faster than the SDK provided algorithms.
Related Files: 
Finally, it is worth noting that to convert float
s to
strings, you should not simply use the double
methods. Although that is technically possible, the smaller
float
data structure is sufficiently different from
double
that the methods should be reimplemented for
float
s, and the smaller range taken account of by using
int
s to hold the scaled values.
Jack Shirazi is the author of Java Performance Tuning. He was an early adopter of Java, and for the last few years has consulted mainly for the financial sector, focusing on Java performance.
Return to ONJava.com.
Copyright © 2009 O'Reilly Media, Inc.