Alan Eliasen - Re: Further BigInteger performance improvements (original) (raw)

This is the mail archive of the java@gcc.gnu.orgmailing list for the Java project.

• From: Alan Eliasen
• To: Florian Weimer , java at gcc dot gnu dot org, xiaobin dot lu at sun dot com, "Joseph D. Darcy"
• Date: Sat, 06 Jun 2009 17:42:32 -0600
• Subject: Re: Further BigInteger performance improvements
• References: 47A14D21.8020807@mindspring.com 47BB539B.8090901@mindspring.com 87skzo6l5r.fsf@mid.deneb.enyo.de 47BCAD9C.1030002@mindspring.com 47E89FE3.6080203@mindspring.com 4A27B7EA.8040809@mindspring.com 4A27BE5B.8070302@redhat.com 4A2851A8.4080208@mindspring.com 4A28559C.4010802@mindspring.com 87ab4l275a.fsf@mid.deneb.enyo.de

Florian Weimer wrote:

To provide some more background, most of us probably worry about BigInteger performance in the 512 to 2048 bit range because that's the range used for RSA cryptography (assuming that Java uses the Chinese Reminder Theorem optimization for private key operations).

I understand the importance of this range in cryptography, and I especially understand the greater importance of the even smaller range that actually makes up the bulk of CPU time spent in cryptography, down in the 128-256 bit sizes. Most practical crypto schemes tend to use those public-key algorithms with numbers of 512 to 4096 bits for the initial key exchange, but then use something like 256-bit AES for encrypting the actual data stream.

I intentionally avoided changing multiplication algorithms for the numbers in the 512-bit and below ranges for these reasons. There's an unavoidable conditional to decide which multiplication algorithm to dispatch to ("is it larger than the threshold?") but otherwise it's unchanged. The base case doesn't even dispatch to another function because I wanted to keep the case for small numbers just as fast.

If you or anyone else has some sort of cryptographic benchmark that you'd like to try, I've been providing my full implementation as a drop-in replacement for over a year now, (including my "future" patches for pow()) so you can compare performance in your environment. Please grab it and compare it against Java 1.6! It's located at:

http://futureboy.us/temp/BigInteger.java

Performance reports invited!

Note that there have been recent, extensive changes by Xiaobin Lu of Sun to BigInteger and BigDecimal, and associated classes MutableBigInteger and SignedMutableBigInteger and I would invite him to tell us more about his improvements and how they affect performance for BigInteger. I haven't seen any discussion of it on the list other than the automated check-in report (2009-05-24) http://hg.openjdk.java.net/jdk7/tl/jdk/rev/8d2efec31d78 . These changes were performed under RFE 6622432, and were apparently even put back into Java 1.6.0_14 according to the release notes. It would still be feasible for me to submit a patch for 1.6, but I'm still hoping for 1.7.

See:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6622432

Note that my changes will vastly improve performance for BigDecimal with a lot of digits, because BigDecimal uses BigInteger internally to do the heavy lifting!

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