Re: Further BigInteger performance improvements

Re: Further BigInteger performance improvements

[Alan Eliasen]

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/