JDK 8 RFC 7189139 version 2: BigInteger's staticRandom field can be a source of bottlenecks
Paul Sandoz
paul.sandoz at oracle.com
Wed Oct 9 12:33:57 UTC 2013
On Oct 8, 2013, at 10:05 PM, Brian Burkhalter <brian.burkhalter at oracle.com> wrote:
> On Oct 4, 2013, at 1:33 AM, Paul Sandoz wrote:
>
>> On Oct 4, 2013, at 9:18 AM, Aleksey Shipilev <aleksey.shipilev at oracle.com> wrote:
>>
>>> On 10/04/2013 03:34 AM, Brian Burkhalter wrote:
>>>> Here is an alternative solution:http://cr.openjdk.java.net/~bpb/7189139.2/.
>>>
>>> Seems OK with me,
>>
>> Same here.
>
> Based on previous comments by Aleksey and Paul I created this test
>
> http://cr.openjdk.java.net/~bpb/7189139/PrimeTest.java
>
> and ran it with the list of primes supplied by Aleksey, N=60000000, and certainty=100. This is the output:
>
> ---
> Primes: /Users/bpb/Desktop/primes-50M.txt
> N = 60000000
> certainty = 100
> 3562115 probable primes out of 3562115 candidates
> Prime test = true
> Not-prime test = true
> Test succeeded!
> ---
>
Nice!
Perhaps as a separate bug you could place that code in the JDK test area as a non-jtreg test?
Tip: you can use Files.lines().map(BigInteger::new) but we don't current have a limitWhen operation so need to limit to N primes and not the content.
And... a bonus we can now go parallel and since TLR is used there is no longer the contention point as with SR, which means we go faster!
I have added a modified version of the test code (see end of email) if you want to play. If you place this test in the JDK test area i strongly recommend using streams, it's a nice use-case we can point people to.
Here is the difference for the first 1000000 primes (with your patch applied) for parallel and sequential execution (which also includes the fixed cost of loading the primes from disk):
$ time java PrimeTest primes-50M.txt 1000000 100 true
Primes: primes-50M.txt
N = 1000000
certainty = 100
parallel = true
Loaded 1000000 primes
1000000 probable primes out of 1000000 candidates
Prime test = true
real 0m16.252s
user 1m59.065s
sys 0m0.649s
$ time java PrimeTest primes-50M.txt 1000000 100 false
Primes: primes-50M.txt
N = 1000000
certainty = 100
parallel = false
Loaded 1000000 primes
1000000 probable primes out of 1000000 candidates
Prime test = true
real 0m54.613s
user 1m0.278s
sys 0m0.343s
16s vs. 55s :-)
> An updated webrev which differs only in having a correct Hg header is here:
>
> http://cr.openjdk.java.net/~bpb/7189139/webrev.2/
>
> If this looks good to go, would a Reviewer please issue an approval?
>
+1
Paul.
/*
* Copyright (c) 2013, Oracle and/or its affiliates. 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
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.util.HashSet;
import java.util.List;
import java.util.concurrent.atomic.LongAdder;
import java.util.stream.Stream;
import static java.util.stream.Collectors.toList;
public class PrimeTest {
public static void main(String[] args) throws Throwable {
File primesFile = new File(args[0]);
int upperBound = Integer.valueOf(args[1]);
int certainty = Integer.valueOf(args[2]);
boolean parallel = Boolean.valueOf(args[3]);
System.out.println("Primes: " + primesFile + "\nN = " + upperBound +
"\ncertainty = " + certainty +
"\nparallel = " + parallel);
boolean primeTest = checkPrime(primesFile, upperBound, certainty, parallel);
System.out.println("Prime test = " + primeTest);
// boolean notPrimeTest = checkNotPrime(primesFile, upperBound, certainty);
// System.out.println("Not-prime test = " + notPrimeTest);
//
// if (!primeTest || !notPrimeTest) {
// throw new Exception("Test failed!");
// }
// System.out.println("Test succeeded!");
}
private static List<BigInteger> parsePrimes(File f, long n) throws IOException {
try (Stream<String> lines = Files.lines(f.toPath(), StandardCharsets.UTF_8)) {
return lines.limit(n).map(BigInteger::new).collect(toList());
}
}
/**
* Verifies whether the fraction of probable primes detected in the range
* [2,upperBound) is at least 1 - 1/2^certainty.
*
* @return true if and only if the test succeeds
*/
private static boolean checkPrime(File primesFile, int upperBound,
int certainty,
boolean parallel) throws FileNotFoundException, IOException {
BufferedReader reader = new BufferedReader(new FileReader(primesFile));
BigInteger bigBound = BigInteger.valueOf(upperBound);
List<BigInteger> primes = parsePrimes(primesFile, upperBound);
System.out.println(String.format("Loaded %d primes", primes.size()));
long probablePrimes = (parallel ? primes.parallelStream() : primes.stream())
.filter(bi -> bi.isProbablePrime(certainty))
.count();
System.out.println(probablePrimes + " probable primes out of " + primes.size() + " candidates");
// N = certainty / 2
// Success if p/t >= 1 - 1/4^N
// or (p/t)*4^N >= 4^N - 1
// or p*4^N >= t*(4^N - 1)
BigInteger p = BigInteger.valueOf(probablePrimes);
BigInteger t = BigInteger.valueOf(primes.size());
BigInteger fourToTheC = BigInteger.valueOf(4).pow(certainty / 2);
BigInteger fourToTheCMinusOne = fourToTheC.subtract(BigInteger.ONE);
BigInteger left = p.multiply(fourToTheC);
BigInteger right = t.multiply(fourToTheCMinusOne);
return left.compareTo(right) >= 0;
}
/**
* Verifies whether all {@code BigInteger}s in the range [2,upperBound) for
* which {@code isProbablePrime()} returns {@code false} are <i>not</i>
* prime numbers.
*
* @return true if and only if the test succeeds
*/
private static boolean checkNotPrime(File primesFile, int upperBound,
int certainty) throws FileNotFoundException, IOException {
BufferedReader reader = new BufferedReader(new FileReader(primesFile));
HashSet<Integer> primes = new HashSet<Integer>(upperBound);
String line;
while ((line = reader.readLine()) != null) {
Integer primeValue = Integer.valueOf(line);
if (primeValue >= upperBound) {
//System.out.println("Break at "+primeValue);
break;
}
primes.add(primeValue);
}
reader.close();
boolean result = true;
for (int i = 2; i < upperBound; i++) {
BigInteger bigInt = BigInteger.valueOf(i);
if (!bigInt.isProbablePrime(certainty) &&
primes.contains(Integer.valueOf(i))) {
result = false;
break;
}
}
return result;
}
}
More information about the core-libs-dev
mailing list