From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 5629 invoked by alias); 6 Jun 2009 23:42:48 -0000 Received: (qmail 5618 invoked by uid 22791); 6 Jun 2009 23:42:46 -0000 X-SWARE-Spam-Status: No, hits=0.0 required=5.0 tests=BAYES_50 X-Spam-Check-By: sourceware.org Received: from elasmtp-curtail.atl.sa.earthlink.net (HELO elasmtp-curtail.atl.sa.earthlink.net) (209.86.89.64) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 06 Jun 2009 23:42:36 +0000 Received: from [70.59.37.201] (helo=[192.168.1.13]) by elasmtp-curtail.atl.sa.earthlink.net with esmtpa (Exim 4.67) (envelope-from ) id 1MD5Wz-0003SM-Ne; Sat, 06 Jun 2009 19:42:33 -0400 Message-ID: <4A2AFEE8.1020304@mindspring.com> Date: Sat, 06 Jun 2009 23:42:00 -0000 From: Alan Eliasen User-Agent: Thunderbird 2.0.0.21 (X11/20090320) MIME-Version: 1.0 To: Florian Weimer , java@gcc.gnu.org, xiaobin.lu@sun.com, "Joseph D. Darcy" 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> In-Reply-To: <87ab4l275a.fsf@mid.deneb.enyo.de> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-ELNK-Trace: b37d7a0c977428ea9649176a89d694c0f43c108795ac4507eed83d39f12237f985de1393104ab590350badd9bab72f9c350badd9bab72f9c350badd9bab72f9c X-IsSubscribed: yes Mailing-List: contact java-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: java-owner@gcc.gnu.org X-SW-Source: 2009-06/txt/msg00019.txt.bz2 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/