JDK-6832035 : BigInteger and MutableBigInteger should use Integer bit-twiddling methods
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.math
  • Affected Version: 7
  • Priority: P5
  • Status: Closed
  • Resolution: Duplicate
  • OS: generic
  • CPU: generic
  • Submitted: 2009-04-20
  • Updated: 2010-07-29
  • Resolved: 2009-10-21
Related Reports
Duplicate :  
JDK-6622432 - RFE: Performance improvements to java.math.BigDecimal
Relates :  
JDK-6823354 - Add intrinsics for {Integer,Long}.{numberOfLeadingZeros,numberOfTrailingZeros}()
Description
BigInteger and MutableBigInteger implement and use some of the bit-twiddling methods themselves.  From a maintainability and performance point-of-view these classes should use the provided Integer methods, like bitCount, numberOfLeadingZeros, etc.
Comments
EVALUATION The suggested usage of Integer bit-twiddling methods was included as part of 6622432.
21-10-2009
EVALUATION I forgot to mention that CR 6823354 should speedup the changes even more.
20-04-2009
EVALUATION That first suggested fix should definitely go in. I'm still looking into another change for BigInteger.trailingZeroCnt being replaced by Integer.numberOfTrailingZeros, but it's not faster on all architectures.
20-04-2009
SUGGESTED FIX diff -Nupr jdk.22b6e09960c1/src/share/classes/java/math/BigInteger.java jdk/src/share/classes/java/math/BigInteger.java --- jdk.22b6e09960c1/src/share/classes/java/math/BigInteger.java 2009-04-20 15:44:03.695435095 +0200 +++ jdk/src/share/classes/java/math/BigInteger.java 2009-04-20 15:44:03.698204215 +0200 @@ -1,5 +1,5 @@ /* - * Portions Copyright 1996-2007 Sun Microsystems, Inc. All Rights Reserved. + * Portions Copyright 1996-2009 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -2371,7 +2371,7 @@ public class BigInteger extends Number i if (signum < 0) { // Check if magnitude is a power of two - boolean pow2 = (bitCnt(mag[0]) == 1); + boolean pow2 = (Integer.bitCount(mag[0]) == 1); for(int i=1; i<mag.length && pow2; i++) pow2 = (mag[i]==0); @@ -2388,23 +2388,7 @@ public class BigInteger extends Number i * bitLen(val) is the number of bits in val. */ static int bitLen(int w) { - // Binary search - decision tree (5 tests, rarely 6) - return - (w < 1<<15 ? - (w < 1<<7 ? - (w < 1<<3 ? - (w < 1<<1 ? (w < 1<<0 ? (w<0 ? 32 : 0) : 1) : (w < 1<<2 ? 2 : 3)) : - (w < 1<<5 ? (w < 1<<4 ? 4 : 5) : (w < 1<<6 ? 6 : 7))) : - (w < 1<<11 ? - (w < 1<<9 ? (w < 1<<8 ? 8 : 9) : (w < 1<<10 ? 10 : 11)) : - (w < 1<<13 ? (w < 1<<12 ? 12 : 13) : (w < 1<<14 ? 14 : 15)))) : - (w < 1<<23 ? - (w < 1<<19 ? - (w < 1<<17 ? (w < 1<<16 ? 16 : 17) : (w < 1<<18 ? 18 : 19)) : - (w < 1<<21 ? (w < 1<<20 ? 20 : 21) : (w < 1<<22 ? 22 : 23))) : - (w < 1<<27 ? - (w < 1<<25 ? (w < 1<<24 ? 24 : 25) : (w < 1<<26 ? 26 : 27)) : - (w < 1<<29 ? (w < 1<<28 ? 28 : 29) : (w < 1<<30 ? 30 : 31))))); + return Integer.SIZE - Integer.numberOfLeadingZeros(w); } /* @@ -2447,7 +2431,7 @@ public class BigInteger extends Number i // Count the bits in the magnitude int magBitCount = 0; for (int i=0; i<mag.length; i++) - magBitCount += bitCnt(mag[i]); + magBitCount += Integer.bitCount(mag[i]); if (signum < 0) { // Count the trailing zeros in the magnitude @@ -2465,15 +2449,6 @@ public class BigInteger extends Number i return bitCount; } - static int bitCnt(int val) { - val -= (0xaaaaaaaa & val) >>> 1; - val = (val & 0x33333333) + ((val >>> 2) & 0x33333333); - val = val + (val >>> 4) & 0x0f0f0f0f; - val += val >>> 8; - val += val >>> 16; - return val & 0xff; - } - static int trailingZeroCnt(int val) { // Loop unrolled for performance int byteVal = val & 0xff; diff -Nupr jdk.22b6e09960c1/src/share/classes/java/math/MutableBigInteger.java jdk/src/share/classes/java/math/MutableBigInteger.java --- jdk.22b6e09960c1/src/share/classes/java/math/MutableBigInteger.java 2009-04-20 15:07:15.706875106 +0200 +++ jdk/src/share/classes/java/math/MutableBigInteger.java 2009-04-20 15:07:15.709160647 +0200 @@ -1,5 +1,5 @@ /* - * Copyright 1999-2007 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 1999-2009 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -739,7 +739,7 @@ class MutableBigInteger { quotient.intLen = intLen; // Normalize the divisor - int shift = 32 - BigInteger.bitLen(divisor); + int shift = Integer.numberOfLeadingZeros(divisor); int rem = value[offset]; long remLong = rem & LONG_MASK; @@ -851,7 +851,7 @@ class MutableBigInteger { int[] q = quotient.value; // D1 normalize the divisor - int shift = 32 - BigInteger.bitLen(d[0]); + int shift = Integer.numberOfLeadingZeros(d[0]); if (shift > 0) { // First shift will not grow array BigInteger.primitiveLeftShift(d, dlen, shift);
20-04-2009