Use the new methods introduced in Java 1.8

[sebbASF]

[codecov-commenter]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Comparison is base (caa41d2) 99.23% compared to head (81b0f6e) 99.22%.

Additional details and impacted files

@@             Coverage Diff              @@
##             master     #139      +/-   ##
============================================
- Coverage     99.23%   99.22%   -0.01%     
+ Complexity     1828     1804      -24     
============================================
  Files            70       70              
  Lines          4808     4776      -32     
  Branches        896      884      -12     
============================================
- Hits           4771     4739      -32     
  Misses           10       10              
  Partials         27       27              

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[aherbert]

I would be wary of this simplification without a performance test.

In the Numbers class the int methods do not use long arithmetic. The long methods do not use BigInteger. This is unlike those methods in my JDK 8 source code which do and may be slower. A quick check in JDK 21 finds this is still not an intrinsic method [1].

Note that the Numbers methods are based on the Hacker's Delight book which is not free, thus it is not easy to check the implementation against the source.

However, there is frequent use of Hacker's Delight in the JDK source. So I wonder why they have not use this trick here.

I can create a quick JMH benchmark to test the Numbers methods against the JDK. The int method may not be faster as long divide should be supported on most hardware. But avoiding BigInteger divide may be noticeable.

Alex

[1] VM Intrinsics Explorer - HotSpot Intrinsics for OpenJDK21

[sebbASF]

If the reason we don't use the JDK methods is performance, this should be explicitly noted in the source so future maintainers are aware.

[aherbert]

I agree. ArithmeticUtils predates JDK 8. I imagine it was ported from Math to Numbers without knowing that JDK 8 had equivalent methods. I'll do a performance test, then we can either merge this PR, or update the code with comments on the performance vs the JDK methods.

[aherbert]

Here are some benchmark results. JDK variants are prefixed with the class that implements the method.

TLDR; the JDK is always faster for the int methods. It can be dramatically slower for the long methods. They fixed this in JDK 17.

Tested using a MacBook Pro using an Apple M2 Pro CPU.

JDK 1.8.0_392, OpenJDK 64-Bit Server VM, 25.392-b08
ArithmeticPerformance.intOp       1024     Integer.divideUnsigned  avgt    5    499.478 ±   14.720  ns/op
ArithmeticPerformance.intOp       1024             divideUnsigned  avgt    5    765.350 ±   47.075  ns/op
ArithmeticPerformance.intOp       1024  Integer.remainderUnsigned  avgt    5    500.030 ±    3.619  ns/op
ArithmeticPerformance.intOp       1024          remainderUnsigned  avgt    5    771.374 ±   33.150  ns/op
ArithmeticPerformance.longOp      1024        Long.divideUnsigned  avgt    5   9423.845 ± 2154.701  ns/op
ArithmeticPerformance.longOp      1024             divideUnsigned  avgt    5    766.622 ±   41.090  ns/op
ArithmeticPerformance.longOp      1024     Long.remainderUnsigned  avgt    5  15715.308 ± 3224.676  ns/op
ArithmeticPerformance.longOp      1024          remainderUnsigned  avgt    5    730.340 ±   65.106  ns/op

JDK 11.0.21, OpenJDK 64-Bit Server VM, 11.0.21+9
Benchmark                     (length)                     (name)  Mode  Cnt      Score       Error  Units
ArithmeticPerformance.intOp       1024     Integer.divideUnsigned  avgt    5    304.676 ±     1.188  ns/op
ArithmeticPerformance.intOp       1024             divideUnsigned  avgt    5    572.168 ±    42.582  ns/op
ArithmeticPerformance.intOp       1024  Integer.remainderUnsigned  avgt    5    315.873 ±     5.194  ns/op
ArithmeticPerformance.intOp       1024          remainderUnsigned  avgt    5    549.925 ±    29.060  ns/op
ArithmeticPerformance.longOp      1024        Long.divideUnsigned  avgt    5  26664.266 ± 13297.623  ns/op
ArithmeticPerformance.longOp      1024             divideUnsigned  avgt    5    572.840 ±    44.454  ns/op
ArithmeticPerformance.longOp      1024     Long.remainderUnsigned  avgt    5  10413.690 ±  1756.904  ns/op
ArithmeticPerformance.longOp      1024          remainderUnsigned  avgt    5    547.748 ±    34.804  ns/op

JDK 17.0.9, OpenJDK 64-Bit Server VM, 17.0.9+9
ArithmeticPerformance.intOp       1024     Integer.divideUnsigned  avgt    5  304.743 ±  2.939  ns/op
ArithmeticPerformance.intOp       1024             divideUnsigned  avgt    5  595.448 ± 26.346  ns/op
ArithmeticPerformance.intOp       1024  Integer.remainderUnsigned  avgt    5  312.449 ±  0.673  ns/op
ArithmeticPerformance.intOp       1024          remainderUnsigned  avgt    5  547.708 ± 22.514  ns/op
ArithmeticPerformance.longOp      1024        Long.divideUnsigned  avgt    5  418.294 ± 21.639  ns/op
ArithmeticPerformance.longOp      1024             divideUnsigned  avgt    5  595.529 ± 28.412  ns/op
ArithmeticPerformance.longOp      1024     Long.remainderUnsigned  avgt    5  438.290 ± 13.524  ns/op
ArithmeticPerformance.longOp      1024          remainderUnsigned  avgt    5  499.466 ± 27.701  ns/op

It seems that performing the int divide using conversion to a long is faster than the method to avoid long arithmetic. But the BigInteger divide was only fixed in JDK 17.

I would recommend: dropping the int divide variants and delegating to the JDK methods; and keeping the long divide variants. A note can be added to the javadoc that the equivalent method in the JDK changed from JDK 11 to 17 to avoid BigInteger arithmetic. I do not think we should add a deprecated notice to the method until all supported versions of the JDK are comparable in speed.

Note: The int results would be more interesting on a CPU that does not support native long division.

[aherbert]

Just browsed the JDK 17 source code for the long methods. These use a method from Hacker's Delight (2nd ed).

So the Hacker's Delight (presumed 1st ed) method in ArithmeticUtils has been improved. Without access to the book, and a license compatibility check, we cannot use the updated version. But the original is still 15-25x faster than the JDK 8/11 version using BigInteger.

[aherbert]

Added the benchmark to master. Run using:

cd commons-numbers-examples/examples-jmh
mvn package -Pexamples-jmh
java -jar target/examples-jmh.jar ArithmeticPerformance

[aherbert]

I've obtained a copy of Hacker's Delight 2.0. Section 9.3 contains details of how to implement unsigned divide. The unsigned modulus is not provided but I have reworked the current code based on the divide code and the old remainder code.

JDK 17

Benchmark                     (length)                  (name)  Mode  Cnt    Score    Error  Units
ArithmeticPerformance.longOp      1024     Long.divideUnsigned  avgt    5  400.189 ±  8.950  ns/op
ArithmeticPerformance.longOp      1024      divideUnsigned_1.0  avgt    5  583.359 ± 41.198  ns/op
ArithmeticPerformance.longOp      1024      divideUnsigned_1.1  avgt    5  402.176 ± 14.229  ns/op
ArithmeticPerformance.longOp      1024  Long.remainderUnsigned  avgt    5  442.659 ±  6.195  ns/op
ArithmeticPerformance.longOp      1024   remainderUnsigned_1.0  avgt    5  547.328 ± 69.341  ns/op
ArithmeticPerformance.longOp      1024   remainderUnsigned_1.1  avgt    5  438.215 ± 16.554  ns/op

So the new long version is approximately 25-30% faster and matches the JDK.

JDK 21 (Long.remainderUnsigned and Long.divideUnsigned are intrinsic methods from JDK 19)

Benchmark                     (length)                  (name)  Mode  Cnt    Score    Error  Units
ArithmeticPerformance.longOp      1024     Long.divideUnsigned  avgt    5  297.357 ±  3.524  ns/op
ArithmeticPerformance.longOp      1024      divideUnsigned_1.0  avgt    5  600.204 ± 37.312  ns/op
ArithmeticPerformance.longOp      1024      divideUnsigned_1.1  avgt    5  428.529 ± 22.745  ns/op
ArithmeticPerformance.longOp      1024  Long.remainderUnsigned  avgt    5  296.415 ±  1.678  ns/op
ArithmeticPerformance.longOp      1024   remainderUnsigned_1.0  avgt    5  511.435 ± 18.497  ns/op
ArithmeticPerformance.longOp      1024   remainderUnsigned_1.1  avgt    5  433.988 ± 34.247  ns/op

Here the JDK is faster due to the intrinsic methods (or some other optimisation - I didn't check the source code).

I have updated the int version to delegate to Integer.remainderUnsigned/divideUnsigned with the rather obvious result that it is now as fast as the JDK (which uses long arithmetic):

Benchmark                    (length)                     (name)  Mode  Cnt    Score    Error  Units
ArithmeticPerformance.intOp      1024     Integer.divideUnsigned  avgt    5  297.178 ±  1.721  ns/op
ArithmeticPerformance.intOp      1024         divideUnsigned_1.0  avgt    5  588.749 ± 45.638  ns/op
ArithmeticPerformance.intOp      1024         divideUnsigned_1.1  avgt    5  296.653 ±  1.402  ns/op
ArithmeticPerformance.intOp      1024  Integer.remainderUnsigned  avgt    5  296.926 ±  3.817  ns/op
ArithmeticPerformance.intOp      1024      remainderUnsigned_1.0  avgt    5  518.333 ± 19.581  ns/op
ArithmeticPerformance.intOp      1024      remainderUnsigned_1.1  avgt    5  297.276 ±  4.458  ns/op

Changes added to master.