100218: BigInteger staticRandom field

[Bill Pugh]

OK, I actually starting this bug report when developing a course project (Paul is a student in my class).
I got bit by this using Doug Lea's ParallelArray infrastructure. My code was checking which elements in an array of 300,000 long values were prime, by checking for divisibility by small primes and then constructing a BigInteger and calling  isProbablePrime.  But I found that using more than one thread only gave me slowdowns.

After about a half day of thinking I was using the ParallelArray code incorrectly, I eventually tracked it down to a bottleneck in the SecureRandom. At first, I figured it was just a problem with the shared SecureRandom being used in the  private method passesMillerRabin when no Random object is provided. Since the method is private, I couldn't provide my own Random.

I wound up using reflection to bypass access control and call passesMillerRabin with a Random object stored in a thread local.

In replicating my benchmarks for this email, I noticed that I was using regular old Random objects rather than SecureRandom objects (using regular Random objects was good enough for my testing). I found that if I used a ThreadLocal<SecureRandom>, I was also getting a slow down when doing parallel primality testing.

I spent some time looking at the implementation of SecureRandom and of sun.security.provider.NativePRNG. The implementation of NativePRNG uses a static singleton to perform all of the work, so that looked like the concurrency bottleneck. But when I rewrote that class, it turns out that even removing all of the Java level concurrency bottlenecks, we still can't generate concurrent secure random numbers, because the NativePRNG reads /dev/urandom for each byte, and that is inherently sequential and is the bottleneck to the entire process of generating secure random numbers.

So I think the right thing to do is to abandon the original patch, and instead make the following changes:
add the following method to BigInteger public boolean isProbablePrime(int certainty, Random end) , which allows primality testing with arbitrary Random objects. In many cases, using a well seeded normal Random object will work just fine, and this will give users the ability to provide their own Random objects
Document SecureRandom to note that all instances of SecureRandom depend on a common shared source of randomness, and thus it can be a concurrency bottlenck. 
Document that BigInteger.isProbablePrime(int certainty) is a concurrency bottleneck.
Add java.util.concurrent.MostlySecureRandom which uses /dev/random for seeding, and uses only the SHA1PRNG implementation provided by sun.security.provider.SecureRandom to generate subsequent randomness. Feel free to pick a name other than MostlySecureRandom. After the initial seeding, calls to generate randomness using a MostlySecureRandom should not use any shared values. 

If this sounds reasonable, we can work out a strategy for who will do what to make this happen.

Bill


> 
> -------- Original Message --------
> Subject: Re: 100218: BigInteger staticRandom field
> Date: Wed, 04 Jan 2012 10:15:10 +1000
> From: 
> Organization: Oracle Corporation
> To: Paul Ciprich <paul.ciprich at gmail.com>
> CC: core-libs-dev at openjdk.java.net
> 
> On 4/01/2012 10:08 AM, David Holmes wrote:
>> Hi Paul,
>> 
>> For some reason this email, despite being dated Dec 14, only just
>> appeared in my inbox on Jan 3!
> 
> Oops! I missed the fact a copy of this email also turned up on Dec 15
> and that I already replied to it.
> 
> Comments still apply. Need to understand the context in which this
> becomes a bottleneck and the performance implications for non-concurrent
> use.
> 
> David
> 
>> On 14/12/2011 12:44 AM, Paul Ciprich wrote:
>>> All,
>>> 
>>> I've created a bug report to address a scalability problem with
>>> BigInteger's staticRandom field. The problem is that the shared
>>> staticRandom field causes bottlenecks with parallel code. The proposed
>>> solution is to change the staticRandom field to a ThreadLocal and
>>> eliminate
>>> the bottleneck by giving each thread its own copy of the SecureRandom
>>> object. Bug 100218 contains a patch with the proposed change if it is
>>> deemed acceptable.
>> 
>> As I mention in the bug report we have to ensure that we don't add
>> unacceptable overhead to the non-concurrent case. Also I'm wondering if
>> anyone might be relying on the existing SecureRandom instance being shared?
>> 
>> Can you clarify the context for the proposed fix: what code is the
>> bottleneck (isProbablePrime?), under what conditions - is it a
>> microbenchmark or real code?
>> 
>> Thanks,
>> David Holmes