class SplittableRandom

[Martin Buchholz]

Thoughts:

I was sad when ThreadLocalRandom reused the lousy pseudorandom
implementation from Random.  I continue to think we can do better.  The
algorithm in SplittableRandom is much better, although even here I'm not
sure we have enough bits of state to satisfy all non-cryptographic uses.

SplittableRandom has 64 bits of state for each generator, and a period of
2^64, and that is hinted at by the API because the constructor takes only a
single long seed.  Although I suppose we could add some other constructor
in the future that provided more seed bits.  One way that users might care
is that currently nextLong cannot possibly return the same value twice in a
row.

It would be nice if we could guarantee a minimum period of 2^64.

Doug, you say "SplittableRandoms will tend to be short-lived." but I'm not
sure why.  I imagine the Monte Carlo folks will want to run simulations
that use a single SplittableRandoms to generate events for hours.

Random provides the useful "nextBoolean" and I think SplittableRandom
should too.




On Sat, Jul 13, 2013 at 6:22 AM, Doug Lea <dl at cs.oswego.edu> wrote:

> (Sorry to postpone answering this one while tied up in logistics...)
>
>
> On 07/11/13 08:23, Aleksey Shipilev wrote:
>
>> On 07/11/2013 04:16 PM, Doug Lea wrote:
>>
>>> (I've been contemplating re-exploring alternatives in TLR,
>>> but the options are more limited because it is a subclass
>>> of Random. Which made sense at the time I did it, but ...)
>>>
>>
>> What exactly limits us to adopt the PRNG from SR into TLR, thus gaining
>> the same good statistical properties? Does extending Random actually
>> forces us to match the PRNG j.u.Random has? It does not seem likely if
>> we don't control the seed for TLR anyway.
>>
>>
> There are two different questions here:
>
> 1. Why a new API / class?
>
> SplittableRandom takes a form that we are likely to see more
> of as we improve support for structured parallelism:
>
>   pseudo-interface SplittableGenerator<T> {
>     T generate();
>     SplittableGenerator<T> split();
>   }
>
> As opposed to ThreadLocalRandom's form:
>
>   pseudo-interface PerThreadGenerator<T> {
>     T generate() {
>        // lazily construct and use a thread-local instance
>     }
>   }
>
> As I've mentioned, each form is useful, but there's
> little overlap in the contexts in which they are useful.
> While you can emulate the effects of one with the other,
> it's not at all pretty or efficient. Without an explicit call
> to split(), the thread-local form would need some side-channel to
> construct an instance of known form (rather than default-initialize).
> Conversely, without automated thread-local-ness, you'd need
> some other means of sharing use of the same instance
> in different parts of a program running in the same thread,
> and may encounter variants of memory locality/contention
> we've seen.
>
> One underlying motivation for introducing SplittableRandom
> in JDK8 is to establish and get some usage experience with
> generators of this form, while at the same time addressing a
> known gap in java.util.stream support for using random streams.
>
> 2. Can/should we improve ThreadLocalRandom?
>
> Probably yes. The ThreadLocalRandom javadocs/specs don't
> themselves promise that they use the same base generator
> algorithm as java.util.Random. When TLR was introduced
> in JDK7, it was a judgement call to make it identical
> to java.util.Random except for the the thread-local-ness,
> maintaining the same speed/quality tradeoffs.
> java.util.Random's algorithm does have known weaknesses,
> but it is far from the worst choice. So it is not all
> that terrible that java.util.Random specs mandate use
> of this algorithm. But for TLR, we should re-explore
> options. The algorithm underlying SplittableRandom
> (minus everything surrounding splits) is one possible
> candidate.
>
> Since nothing else depends on these internals, so long as
> they don't lose RNG quality or noticeably impact
> performance, we can look into this during the
> performance/functionality improvement phase of OpenJDK8.
>
> -Doug
>
>
>