From: Alan Eliasen <eliasen@mindspring.com>
To: Florian Weimer <fw@deneb.enyo.de>,
java@gcc.gnu.org, xiaobin.lu@sun.com,
"Joseph D. Darcy" <Joe.Darcy@Sun.COM>
Subject: Re: Further BigInteger performance improvements
Date: Sat, 06 Jun 2009 23:42:00 -0000 [thread overview]
Message-ID: <4A2AFEE8.1020304@mindspring.com> (raw)
In-Reply-To: <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/
parent reply other threads:[~2009-06-06 23:42 UTC|newest]
Thread overview: expand[flat|nested] mbox.gz Atom feed
[parent not found: <87ab4l275a.fsf@mid.deneb.enyo.de>]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4A2AFEE8.1020304@mindspring.com \
--to=eliasen@mindspring.com \
--cc=Joe.Darcy@Sun.COM \
--cc=fw@deneb.enyo.de \
--cc=java@gcc.gnu.org \
--cc=xiaobin.lu@sun.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).