Further BigInteger performance improvements (original) (raw)

Alan Eliasen eliasen at mindspring.com
Thu Jun 4 12:02:50 UTC 2009

16 months ago, I posted the first of several patches to vastly improve the performance of the BigInteger class. These included implementation of Karatsuba and 3-way Toom-Cook multiplication and Karatsuba and Toom-Cook squaring. The particular algorithm used for multiplication or squaring is chosen according to the size of the numbers, and are these algorithms are asymptotically faster than the O(n^2) algorithms in previous versions of Java. (Karatsuba is O(n^1.585), 3-way Toom Cook is O(n^1.465)).

Unfortunately, none of these patches has yet been applied or reviewed in any way by Sun. (Although they have been reviewed by some of the top researchers in the field of high-performance multiplication.) Nor have I received answers to my questions about how long Sun wants regression tests to run, size of output, etc., nor have I been provided with promised existing regression tests for BigInteger to see if they need improvement. (If I can find these somewhere, please let me know. They're not apparently in my checkout.)

I'm still hoping to get these changes into Java 1.7, because the performance increase is so significant, and because this is necessary to make Java a feasible platform for number theory and numerics.

Recently, Xiaobin Lu submitted patches to improve the performance of BigDecimal, and also improved BigInteger's performance in the process. Great job!

Luckily, the overlap between our patches was negligible. Xiaobin may now be the person most suited to look over my patches, as he has worked intimately in the class recently. My fixes are further improved by his fixes to give some truly spectacular improvements in performance for big numbers, which should also help large BigDecimals. I was disappointed, though, that Sun knew about my larger performance improvements for a long time and didn't use this opportunity to evaluate and apply them, nor communicate with me, despite my repeated attempts and my frankly hard work on this.

Below, interspersed among my previous statements, are some updated performance numbers with my patches and Xiaobin's.

For multiplying the numbers 3^1000000 * 3^1000001, (with my fixes to do the exponentiation hundreds of thousands of times faster factored out; without these, JDK 1.6 would be thousands of times slower,) the times for 20 iterations are:

JDK 1.6 292987 ms OpenJDK1.7 + my Karatsuba 28650 ms OpenJDK1.7 + my Toom/Cook 18054 ms Plus Xiaobin's improvements 12880 ms

*** Performance improvement over Java 1.6: 22.7x

For multiplying numbers 3^14000000 * 3^14000001, the time for 1 iteration is:

JDK 1.6 3499115 ms OpenJDK1.7 + my Karatsuba 89505 ms OpenJDK1.7 + my Toom/Cook 43636 ms Plus Xiaobin's improvements 29813 ms

*** Performance improvement over Java 1.6: 117.3x

You can see that operations that weren't even feasible to consider in JDK 1.6 are now possible in Java. Operations that used to take almost an hour can be done in less than 30 seconds.

This encompasses a lot of different bug reports:

4228681: Some BigInteger operations are slow with very large numbers http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4228681

(This was closed but never fixed.)

4837946: Implement Karatsuba multiplication algorithm in BigInteger http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

This is done, along with Toom-Cook multiplication.  My

implementation is intended to be easy to read, understand, and check. It significantly improves multiplication performance for large numbers.

4646474: BigInteger.pow() algorithm slow in 1.4.0 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474

This is improved in many ways:

4641897: BigInteger.toString() algorithm slow for large numbers http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897

This algorithm uses a very inefficient algorithm for large numbers. I plan to replace it with a recursive divide-and-conquer algorithm devised by Schoenhage and Strassen. I have developed and tested this in my own software. This operates hundreds or thousands of times faster than the current version for large numbers. What takes a day in Java 1.6, I can do in 5 minutes. It will also benefit from faster multiplication and exponentiation. This is likely to be the most controversial algorithm because it has potential threading and synchronization and caching and memory-vs-speed tradeoffs, so I'm going to submit it separately, if I can get Sun to review the multiply and pow patches first.

My patches are designed to be as readable and simple as possible. They all build on existing functions, and eschew lots of low-level bit-fiddling, as those types of changes are harder to understand and debug. I think it's best to get working algorithms with better asymptotic efficiency, as those will vastly improve performance for large numbers, and tune them by doing more low-level bit fiddling later if necessary. Even without being tuned to the nth degree, the new algorithms are vastly faster for large numbers, and identical for small numbers.

I've been asked by Sun to submit my patches in small chunks, so I plan to submit just the multiplication and squaring patch, and leave the patches for pow() for later unless I hear otherwise. I'd rather they had it all and got it tested and integrated as soon as possible, after all this waiting, and the work it takes to separate out working code to make a smaller patch.

I will be submitting a patch in the next day or two. I'm running my huge regression tests which produce about 250 GB of output and take at least a day to run. (And you have to run it twice against a known good platform to have something to compare to... luckily I've done that.)

For those who'd just like to replace their file with my improved version (includes Xiaobin's patches), it's available at: http://futureboy.us/temp/BigInteger.java

From the queries I get, this is important to a lot of people. The performance of BigInteger can be improved by tens or hundreds or thousands of times (or even more in the case of certain arguments of pow()), and should be done to make Java a more viable platform for numerics.

This work has been in Sun's hands for a long time, and really needs to get into 1.7.

-- Alan Eliasen eliasen at mindspring.com http://futureboy.us/

More information about the core-libs-dev mailing list