Can Java optimize "mutating" BigInteger operations in loops?

Question

I need to deal with a lot of big numbers much larger than a long (>10^200), so I'm using BigIntegers. The most common operation I perform is adding them to an accumulator, ex:

BigInteger A = new BigInteger("0");
for(BigInteger n : nums) {
    A = A.add(n);
}

Of course making copies for destructive actions is quite a waste (well, as long as there's a large enough buffer available), so I was wondering if Java can optimize this somehow (I heard there was a MutableBigInteger class not exposed by math.java) or whether I should just write my own BigInteger class.

Answer 1

Yes, there is a java.math.MutableBigInteger class that is used by BigInteger for compute-intensive operations. Unfortunately, it is declared as package private, so you cannot use it. There is also a "MutableBigInteger" class in the Apache Commons library, but it is just a mutable wrapper for BigInteger and that is no help for you.

I was wondering if Java can optimize this somehow ...

No ... not withstanding the above.

or whether I should just write my own BigInteger class.

That's one approach.

Another is to to download the OpenJDK sources, find the source code for java.math.MutableBigInteger, change its package name and access, and incorporate it into your code-base. The only snag is that OpenJDK is licensed under the GPL (GPL-2 I think), and that has implications if you ever distribute code using the modified class.

See also:

• What is the purpose of java.math.MutableBigInteger?

Answer 2

A quicker solution is to circumvent the java package visibility. You can do that by creating a package named java.math in your own project and creating a public class that exposes the package private MutableBigInteger like so:

package java.math;

public class PublicMutableBigInteger extends MutableBigInteger {

}

Then you can just import java.math.PublicMutableBigInteger; and use it as any other class. This solution is quick and doesn't impose upon you any particular licence.

Answer 3

There's not a lot the compiler can do, because it can't know what the add method does. Here is the generated code for the loop's body. As you can see, it simply calls add and stores the result.

   25:  iload   5
   27:  iload   4
   29:  if_icmpge       51
   32:  aload_3
   33:  iload   5
   35:  aaload
   36:  astore  6
   38:  aload_1
   39:  aload   6
   41:  invokevirtual   #5; //Method java/math/BigInteger.add:(Ljava/math/BigInteger;)Ljava/math/BigInteger;
   44:  astore_1
   45:  iinc    5, 1
   48:  goto    25

In theory, the Java virtual machine run time system could be more clever. For instance, it could detect that one object continuously overwrites another just allocated, and just swap two allocation buffers for them. However, as we can see by running the following program with garbage collection logging enabled, this is sadly not the case

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Random;

class Test {
    public static void main(String[] args) {
    ArrayList <BigInteger> nums = new ArrayList<BigInteger>();
    final int NBITS = 100;
    final int NVALS = 1000000;

    System.out.println("Filling ArrayList");
    Random r = new Random();
    for (int i = 0; i < NVALS; i++)
        nums.add(new BigInteger(NBITS, r));

    System.out.println("Adding ArrayList values");
    BigInteger A = new BigInteger("0");
    for(BigInteger n : nums) {
        A = A.add(n);
    }

    System.gc();
    }
}

See the garbage collection calls during the addition process.

C:\tmp>java -verbose:gc Test
Filling ArrayList
[GC 16256K->10471K(62336K), 0.0257655 secs]
[GC 26727K->21107K(78592K), 0.0304749 secs]
[GC 53619K->42090K(78592K), 0.0567912 secs]
[Full GC 42090K->42090K(122304K), 0.1019642 secs]
[GC 74602K->65857K(141760K), 0.0601406 secs]
[Full GC 65857K->65853K(182144K), 0.1485418 secs]
Adding ArrayList values
[GC 117821K->77213K(195200K), 0.0381312 secs]
[GC 112746K->77245K(228288K), 0.0111372 secs]
[Full GC 77245K->137K(228288K), 0.0327287 secs]

C:\tmp>java -version
java version "1.6.0_25"
Java(TM) SE Runtime Environment (build 1.6.0_25-b06)
Java HotSpot(TM) 64-Bit Server VM (build 20.0-b11, mixed mode)

Answer 4

Java won't do any special optimisations for this case. BigInteger is generally treated as a normal class like any other (unlike String, for example, which sometimes gets some special optimisations when you are concatenating many strings).

But in most cases, BigInteger is fast enough that it won't matter anyway. If you really think it might be a problem, I'd suggest profiling you code and working out what is taking the time.

If adding BigIntegers is really your bottleneck, then it might make sense to use a custom mutable big-integer class to act as an accumulator. But I wouldn't do this before you've proved that this is genuinely the main bottleneck.