5 Jan 07:02
Re: 100218: BigInteger staticRandom field
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