Java 8 RFC 7189139: BigInteger's staticRandom field can be a source of bottlenecks
paul.sandoz at oracle.com
Thu Aug 29 10:00:27 UTC 2013
On Aug 26, 2013, at 3:15 PM, Paul Sandoz <Paul.Sandoz at oracle.com> wrote:
>> As discussed in the relevant threads in the original bug report, the
>> actual fix should be a very accurate replacement of SR with some other
>> faster and reliable RNG to avoid the inherent scalability bottlenecks.
> I don't know about the PRNG requirements for Miller-Rabin but the changes to TLR in review might be a possible substitute for SR in this case, since TLR will be updated to use the same PRNG algorithm as SplittableRandom, which passes DieHarder tests. Otherwise, i think we may just be stuck with SR.
FYI the updates to ThreadLocalRandom are now in tl, so it is possible to more easily investigate whether this can substitute SecureRandom.
IIUC the Miller-Rabin algorithm seems almost embarrassingly parallel.
One could write a Spliterator in combination with SplittableRandom to generate an appropriate source of BigInteger instances hooked up to a stream:
Stream<BigInteger> s = BigInteger.randomStream(pp.bitLength(), n);
return s.filter(b -> b.compareTo(ONE) > 0 && b.compareTo(pp) < 0).map(b -> test(b, pp)).allMatch(r -> r == true);
I suppose in some respects it is unfortunate to have to write a Spliterator instead of piggybacking off IntStream.range(0, n) and associating with functions to create a SplittableRandom and split based on how the range is split.
Another way could be to write a Spliterator for a source of depth and SplittablleRandom, then hook that up to flatMap:
Stream<Pair<Integer, SplittableRandom>> s = ...;
return s.flatMap((d, sr) -> bigInts(sr, pp.bitLength(), n / (1 << d)).map(b -> test(b, pp)).allMatch(r -> r == true);
More information about the core-libs-dev