Re: 100218: BigInteger staticRandom field
Bill Pugh <
pugh@...>
2012-01-05 06:02:19 GMT
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
(Continue reading)
RSS Feed