Implementing a high performance Money class

by Mikhail Vorontsov

This article will discuss how to efficiently implement a Money class in Java. This article follows Using double/long vs BigDecimal for monetary calculations article published earlier in this blog.

Introduction

As I have written before, we should not use any floating point types for storing monetary values. We should use long instead, keeping the number of smallest currency units in it. Unfortunately, there is a couple of problems:

  • We may still have to communicate with a software storing monetary values in double variables.
  • We may want to multiply it by a non-integer number, like 0.015, or divide it by any type of number, thus getting the non-integer result.

The easy way to deal with arithmetic operations is to use the BigDecimal class for all of them. Unfortunately, BigDecimal will not help you to deal with already incorrect double calculations results. For example, the following code will print 0.7999999999999999:

1
System.out.println( new BigDecimal( 0.7 + 0.1, MathContext.DECIMAL64 ) );
System.out.println( new BigDecimal( 0.7 + 0.1, MathContext.DECIMAL64 ) );

So, we may say that BigDecimal operations will produce the correct result if it had the correct arguments. We can not say the same about double operations.

double operations may end up with the exact result or a result which is one bit off the exact result. This is most likely caused by executing double operations using higher precision on CPU and then rounding the result. All we need to do to get the exact result is to look at these 3 values (result; result plus one bit value, which is also known as ulp; and result minus ulp). One of them would be the correct one. Easy to say, difficult to efficiently implement 🙂

Money-conversion library

MoneyFactory

I have developed the money-conversion library, which is available for download here. It defines a Money interface and a MoneyFactory class, which allows you to convert from various popular formats into the most efficient Money implementation. The following source formats are supported:

  • BigDecimal
  • double with specified precision (see below)
  • long with specified precision
  • String (see format below)
  • CharSequence (see format below)
  • part of char[] (see format below)
  • part of byte[] (see format below)

Precision in terms of this library is the number of digits after decimal point. It can not be negative. For example, a value=1234 and precision=2 will represent 12.34.

String/CharSequence/char[]/byte[] support the same input data format: optional plus or minus sign, followed by ASCII digits (codes 48-57) with optional decimal point “.” separator. Example: -12.34.

Money

There are 2 Money implementations (though none of which are public):

  • long-based MoneyLong, which represents a number of smallest possible currency units (long) and precision of a current instance. This implementation is expected to run as fast as possible.
  • BigDecimal-based MoneyBigDecimal, which acts as a safety net in case when the operation result does not fit in the required precision (or the precision is more than 15, which is the maximal supported precision for MoneyLong). This class operations are slow (due to BigDecimal performance), but we always try to convert the operation result into MoneyLong.

Both implementations are immutable.

Money supports the following operations:

  • Add another Money instance
  • Subtract another Money instance
  • Negate Money instance
  • Multiply by double / long
  • Divide by double / long (you need to specify the required result precision for division)
  • Truncate to the specified precision
  • Convert to double / BigDecimal / String

Implementation details

Here are the most important conversion rules and tricks implemented in the library:

1. We can check that a double variable contains an integer value if we will cast it to long and then back to double and get the original value. Both casts are cheap operations.

2. If we have a double value, which is possibly one ulp off the actual result, we may try to multiply this value by a sufficiently large power of 10 and check if the result is an integer value (see rule 1). If not, try to add or subtract ulp from the original value and multiply it by a power of 10 again (use Math.nextAfter to add/subtract ulp).

3. We have to normalize our MoneyLong objects – while its value is divisible by 10 without remainder and the precision is greater than 0, we should divide the value by 10 and decrease the precision by 1. It helps us to deal with the results of operations like 0.5 + 0.5.

4. Multiplication by long is pretty simple – if A*B=C, then A should be equal to C/B. If not – we have an overflow and should use BigDecimal operations.

5. Multiplication by double is slightly worse: first we should check if the result is an integer value (see rule 1). After that we should use the fact that we precision of the result is not greater than the precision of the multiplier. Unfortunately, we don’t know what’s the precision of a multiplier and finding it out is as equally complex as finding out the result precision. So the library makes a speculative assumption that the result precision is not greater than 4 and tries to apply rule 2. In case of failure it falls back to BigDecimal calculations (but we may still end up with MoneyLong at the end).

6. Both long and double division are implemented as double division. Seemingly obvious assumption to try to check if A mod B = 0 means that we have to execute the most expensive integer operation without major chances of success (it will be a waste of time in most of cases).

7. double division turned out to be quite efficient due to the requirement to specify the required result precision: we divide the value by divisor, adjust the precision and use Math.round to get the result. Similar logic is used for truncation.

8. If we will divide a long value by a double non-negative power of 10 (1, 10, 100, 1000, …) – the result will never contain an error. Same applies to the case of division of a double containing long value by a long non-negative power of 10. At the same time we can not replace division by 10N by multiplication by 10-N: the result will be off by ulp in many cases. That’s a pity, because multiplication is still significantly faster than division on modern CPUs. At the same time, we can safely use multiplication by 10-N if we will round the result using Math.round.

9. If we have to check if a number is divisible by 10, the only cheap check we can make (without making div or mod operations) is to check if a number is odd ( (val & 1) == 1 ).

Other pretty interesting observations

  • BigDecimal valueOf(long unscaledVal, int scale) is an extremely fast static factory and it matches the MoneyLong representation.
  • Integer/Long.toString (getChars actually) have rather interesting implementations – code which deals with 16 bit numbers is especially curious and reminds me about the tricks I have read in the “Hacker’s Delight” book.

Test results

Here are the test results I have obtained on my Xeon E5-2650 workstation:

FromConversionTests

Test name Result (Kops/sec)
From double 79365
From string 1 decimal digit 40000
From string 4 decimal digits 32154
From BigDecimal 1 decimal digit 21505
From BigDecimal 4 decimal digits 13106

ToConversionTests

Test name MoneyLong (Kops/sec) MoneyBigDecimal (Kops/sec)
toDouble 763358 30303
toString 25188 13440
toBigDecimal 294117 direct BigDecimal field access
  • MoneyLong to double conversion requires just one floating point division, so it is very fast.
  • MoneyLong to BigDecimal conversion requires a few conditional instructions, so it is also very fast.
  • It does not make sense to measure the speed of MoneyBigDecimal to BigDecimal conversion, because it just returns the immutable BigDecimal field.

OperationTests

Test name MoneyLong (Kops/sec) MoneyBigDecimal (Kops/sec)
MoneyLong+MoneyLong 84033 0
MoneyLong+MoneyBigDecimal 6849 0
MoneyBigDecimal+MoneyBigDecimal 4330 0
multiply(long) 181818 6939
multiply(double) 46296 3141
divide(long) 74626 5574
divide(double) 74074 2849
truncate 106382 13175
  • Division by double is faster than multiplication by double because we are allowed to round the division result instead of trying to pick the correct result as in case of multiplication.
  • On the other hand, multiplication by long is the fastest operation because it requires just an integer multiplication and 2 integer bit operations on the most probable path.
  • MoneyLong+MoneyLong is quite fast, but it requires a few conditional operations which make it not the fastest MoneyLong method.

Summary

  • You should avoid using BigDecimal for monetary calculations – its operations run 10+ times slower than the equivalent long/double operations.
  • Three following observations will help you to efficiently implement your long <-> double conversion layer:
  • 1. We can check that a double variable contains an integer value if we will cast it to long and then back to double and get the original value. Both casts are cheap operations.
  • 2. If we have a double value, which is possibly one ulp off the actual result, we may try to multiply this value by a sufficiently large power of 10 and check if the result is an integer value (see rule 1). If not, try to add or subtract ulp from the original value and multiply it by a power of 10 again (use Math.nextAfter to add/subtract ulp).
  • 3. If we will divide a long value by a double non-negative power of 10 (1, 10, 100, 1000, …) – the result will never contain an error. Same applies to the case of division of a double containing long value by a long non-negative power of 10. At the same time we can not replace division by 10N by multiplication by 10-N: the result will be off by ulp in many cases. That’s a pity, because multiplication is still significantly faster than division on modern CPUs. At the same time, we can safely use multiplication by 10-N if we are allowed to round the result using Math.round.

Source code

https://github.com/mikvor/money-conversion


One thought on “Implementing a high performance Money class

  1. Pingback: Using double/long vs BigDecimal for monetary calculations

Leave a Reply

Your email address will not be published. Required fields are marked *