Hi Gilles,
You ask some good questions which I may have been vague about due to
familiarity with the possibilities. I hope to clarify a bit below.
On 08/04/2019 16:05, Gilles Sadowski wrote:
Hi Alex.
Le lun. 8 avr. 2019 à 14:36, Alex Herbert <alex.d.herb...@gmail.com> a écrit :
This is a starter for a discussion on the split and jump functionality
for a random generator.
Split:
To create a new instance of the generator that is deterministically
based on the state of the current instance but the probability that the
sequence generated by the new instance and the current instance overlap
is negligible.
I may well be mistaken but I seem to recall that a split is supposed
to create an instance with no overlap for a sequence below a certain
length.
From the implementations I have found in the XorShiRo family they have
both a split and a jump.
The split basically creates a new random generator. There are no
guarantees about sequence overlap. This is like seeding a new instance.
The difference is that it is deterministic based on the current state
and will return an instance of the same generator, that will be
different, and do it fast. It is very simple to do this. Just scramble
the current state using an algorithm different from how the state is
regularly updated. I see it as a "scrambled copy" type functionality.
The jump is more constrained. It advances the generator to a point that
would be reached after a large number of calls to next(). Here's how the
documentation from XorShiro256StarStar describes its use (c-code):
/* This is the jump function for the generator. It is equivalent
to 2^128 calls to next(); it can be used to generate 2^128
non-overlapping subsequences for parallel computations. */
void jump(void);
/* This is the long-jump function for the generator. It is equivalent to
2^192 calls to next(); it can be used to generate 2^64 starting points,
from each of which jump() will generate 2^64 non-overlapping
subsequences for parallel distributed computations. */
void long_jump(void);
So the idea is to seed an experiment once to get a single generator.
Then jump it for each parallel computation. Each computation will then
be guaranteed to run with a different sequence for at least as long as
the jump length.
This results in the following type of code using the API I suggested:
// If jump returns a new instance
JumpableUniformRandomProvider source = ...;
UniformRandomProvider[] rngs = new UniformRandomProvider[128];
for (int i = 0; i < rngs.length; i++) {
// Advance state
rngs[i] = source.jump();
source = rngs[i];
}
In my suggested API the jump returns a new instance. So calling jump
repeatedly on the same generator keeps returning the same fast-forward
state. This could lead to errors if not well documented how to use it.
The alternative is to advance the state of the same instance. So to get
the same effect for parallel computations you must have an ability to
copy a generator (which we do not have in the API).
// If jump updates the current instance
JumpableUniformRandomProvider source = ...;
UniformRandomProvider[] rngs = new UniformRandomProvider[128];
for (int i = 0; i < rngs.length; i++) {
// Advance state and copy
rngs[i] = source.jump().copy();
}
We previously discussed copy(). IIRC the conclusion was that copy()
could be misused for parallel computations; it basically allows a
parallel set of work all with a copy of the same generator and so
limited randomness across the set. Leaving it out of the API out forces
the use of new generators for parallel work.
So there are at least three options for jump:
1. jump returns a new instance with an advanced state. Current state is
the same (possible errors when using this repeatedly)
2. jump advances the current state (requires separate copy method to be
of use)
3. jump advances the current state and returns a new copy instance
(combined jump and copy is possibly a bit confusing)
I would opt maybe instead for option 2 over the original option 1. But
then that exposes the 'risks' of misuse of just copy().
Jump:
To create a new instance of the generator that is deterministically
based on the state of the current instance but advanced a set number of
iterations.
IOW, after a jump, the new state is equivalent to the state one would
have gotten to after a specified (large) number of calls to "next()".
Yes.
Split:
This is an alternative to simply creating a new instance of the same
generator using a different seed,
It's not my (limited/wrong ?) understanding. What prevents the new
seed from creating a state that would be reached (by the original
instance) after just a few numbers?
Nothing. There are no guarantees with split. However it should be noted
that for the generators with a large state space the probability of
collision will be low. Plus it would be no worse than creating a new
instance anyway, just faster.
or using the generator to create a
seed then creating a new instance.
What is gained from using the current instance, rather than any other
generator to create a new seed (like it's done with the "SeedFactory")?
Nothing. It was an example of an equivalent result to a split: get a new
instance seeded differently.
This circular argument does seem to indicate very little advantage to a
split operation other than speed to get another instance of the same type.
Perhaps a use case is parallel computations where you do not care if the
sequences overlap, only that they start from different points and have a
unique instance for the thread. This would work for instance where each
parallel task had different input to combine the randomness with anyway.
In effect a situation where a simple copy of the same generator would
also suffice.
In the later case this would advance
the current generator but a split does not have to (more on this later).
Assuming the state of a generator is a set of bits with no further
requirements then a split can be performed by a bit mixing algorithm. A
commonly used algorithm is the finalisation step of the MurmurHash3 of
Austin Appleby [1] which has variants to mix int and long values from
input int or long.
Most of the algorithms in Commons RNG should have a state applicable to
simple mixing.
Subject to my very partial knowledge, I assumed that "jump" was
the engine behind the "split" functionality (whose purpose is to
ensure a specified number of non-overlapping sequences).
No. The two are different. Split is faster and has less restrictions.
Notable exceptions are those that implement a controlled
seeding procedure: MersenneTwister; MersenneTwister64; ISAAC; and
TwoCmres. These have a state that is more controlled that just random
bits. In most cases the split could be implemented by mixing the state
to create a seed for a new instance, then running through the
initialisation procedure. There may not be much value in this (over just
forcing a user to create a new seeded instance) although making all the
generators Splittable makes an easier to use library.
I thought that the question was whether a "jump" function always exists.
IOW, for some generators, the only way to get from one state to another
would be by passing through all the intermediate states.
There may be no jump (which requires an exact update to the state) but
there can always be a split. So this may be a reason to add both
interfaces to the library. With split implemented by all generators they
can all be used in parallel computations via split() to get a generator
for each thread.
The lack of a jump is evident in the constructor for TwoCmres which
would benefit from a jump function but instead explicitly forwards the
state of each sub-cycle generator by calling it n times.
A notable exception is the SplitMix64 algorithm. This implements
generation of long values identically to Java 8's SplittableRandom. The
sequence is generated using a linear series of long values that is mixed
to output random long values. The linear series is produced using a
default increment that maximises the period of the sequence. A simple
split implementation would just mix the current point in the series.
However Java 8's SplittableRandom also mixes the increment constant
(using a MurmurHash3 mix step). The constant is then forced to be odd
and contain a high number of bit state transitions (i.e. 0s to 1s or 1s
to 0s, the maximum for a long is 32) [2]. So should the Commons RNG
class match the implementation of SplittableRandom? This may have
licensing issues. Note: A side-effect of requiring two numbers for the
split instance is the current instance is advanced.
Given there are no decisions to be made by the user when splitting a
suggestion for an API would be a new interface akin to
RestorableUniformRandomProvider:
package org.apache.commons.rng;
public interface SplittableUniformRandomProvider extends
UniformRandomProvider {
SplittableUniformRandomProvider split();
}
An implementation detail:
Q. Should a split advance the state of the current generator? This
allows successive split() calls from the same instance to create new
variants.
I cannot give a pertinent opinion given my questions above...
IIUC what you wrote earlier (i.e. "split" is akin to create a new
instance from a different seed), it does not need to be defined
"internally". And, actually, calling "RandomSource.create", without
specifying the seed, is indeed doing a "split" (?).]
If I'm correct (about "jump" ensuring non-overlapping sequences),
then "rng.split()" would just be equivalent to "rng.jump()".
Given the above split just scrambles the state into a new generator.
This allows:
// If split does not update the current instance
JumpableUniformRandomProvider source = ...;
UniformRandomProvider[] rngs = new UniformRandomProvider[128];
for (int i = 0; i < rngs.length; i++) {
// Advance state and split
source.nextLong();
rngs[i] = source.split();
}
// If split advances the current instance
JumpableUniformRandomProvider source = ...;
UniformRandomProvider[] rngs = new UniformRandomProvider[128];
for (int i = 0; i < rngs.length; i++) {
// Split advances (even only one step)
rngs[i] = source.split();
}
So perhaps the better implementation is to require that split will alter
the state of the current instance and return a new instance of the same
generator which will have a different output. This allows repeat calls
to split to create new generators.
Note that the split implementation for SplittableRandom will:
- Advance the current instance two calls to next()
- Create a new instance with a random seed and a different (random)
increment
This ensures each new generator has a different output. The Javadoc states:
* Constructs and returns a new SplittableRandom instance that
* shares no mutable state with this instance. However, with very
* high probability, the set of values collectively generated by
* the two objects has the same statistical properties as if the
* same quantity of values were generated by a single thread using
* a single SplittableRandom object. Either or both of the two
* objects may be further split using the {@code split()} method,
* and the same expected statistical properties apply to the
* entire set of generators constructed by such recursive
* splitting.
This is a bit more than a split to scramble the state (since the output
sequences will very unlikely overlap) but not quite a jump of a defined
length along the output sequence.
I would vote yes. It will prevent misuse where multiple threads are
created that each have an instance provided by a call to split() on the
same source generator that is not otherwise advanced.
A user can always save the state of any of the generators in the library
and restore it to the state before the call to split if they so desire.
Jump:
This requires a generator that has a predictable state at some point in
the future given the current state. The XorShiRo family have jump
functions computed by the original authors. The jump size in power of 2
is provided. The SplitMix is a simple linear series and so can be jumped
any distance. Jumps functions are available for:
XOR_SHIFT_1024_S & XOR_SHIFT_1024_S_PHI (512)
XO_SHI_RO_128_PLUS & XO_SHI_RO_128_SS (64)
XO_RO_SHI_RO_128_PLUS & XO_RO_SHI_RO_128_SS (64, 96)
XO_SHI_RO_256_PLUS & XO_SHI_RO_256_SS (128, 192)
XO_SHI_RO_512_PLUS & XO_SHI_RO_512_SS (256)
SPLIT_MIX_64 (1 - 63) [3]
*** The list may not be complete as I have not checkout the original
source for all generators. ***
The fact that the jump size can be different requires a more flexible
API. Currently all the jumps are powers of 2. But this may not always be
true. This allows the following specification to indicate the number of
jumps that are supported:
What is meant by supported?
I'd guess the number of jumps before the sequence wraps (?).
If so, does the newly created instance gets its number of supported
jumps reduced by one?
I meant 'Supported' as the number of different jump lengths that can be
done. So at least 1 but, as for the XorShiRo generators, this can be 2.
I did not think an alternative API returning how far you can jump was
useful. Just that it be flexible enough that short and long jumps can be
specified.
Tracking the number of jumps left before a collision would be up to the
user.
package org.apache.commons.rng;
public interface JumpableUniformRandomProvider extends
UniformRandomProvider {
int getNumberOfJumps();
JumpableUniformRandomProvider jump(int jump);
}
If jump sizes and number of "supported" jumps are implementation-dependent,
it's not clear to me that it should be part of the API here (e.g.
could the caller
obtain an instance for which "getNumberOfJumps()" would return zero?).
No. If you implement the JumpableUniformRandomProvider then you must be
able to jump. So perhaps just the version with jump(), longJump() and
isLongJumpSupported().
The implementation would then support any jump parameter up to the
supported number of jumps.
The definition of the meaning of the jump parameter is ambiguous. It
should be documented in the implementing class what the 'jump' refers to.
This would allow for example XO_SHI_RO_256_PLUS to return 2 for the two
supported jump sizes and document the actual size of the jumps. The
SplitMix algorithm would return some TBD number [4].
An alternative is to mandate only a single jump, or as shown below a
maximum of two jumps:
package org.apache.commons.rng;
public interface JumpableUniformRandomProvider extends
UniformRandomProvider {
boolean isLongJumpSupported();
JumpableUniformRandomProvider jump();
JumpableUniformRandomProvider longJump();
}
This may not be flexible enough going forward.
I'm missing many points, and this one too as a consequence.
My (simplistic?) idea was to have methods added to the
"UniformRandomProvider" interface:
public interface UniformRandomProvider {
// ...
boolean isJumpable();
UniformRandomProvider jump();
}
[Of course, it would be an incompatible change, unless we decide
to only target JDK versions that allow "default" methods.]
With comptability, we could have a "JumpableUniformRandomProvider"
interface with a single "jump" method (functional interface?), and define
"createJumpable" methods in "RandomSource" that would throw if the
"core" implementation does not support "jump".
A single jump function is better than nothing but missing the fact that
for half of the implementations for which we know a jump they have two
jump lengths. Since we are starting from scratch I think we should make
the API support this flexibility.
Discussion on this is requested.
Do any of these questions/comments make sense? :-)
Always.
Best,
Gilles
Alex
[1] https://github.com/aappleby/smhasher
[2] Using Long.bitCount(long ^ (long >>> 1)) to count transitions
[3] The SplitMix64 is a simple linear series and thus can be jumped in
any power of 2 up to the maximum for a long (which causes sequence
wrapping). It can actually be jumped any number of iterations using
BigInteger arithmetic but jumping in powers of 2 can be implemented
using long arithmetic where the rollover bits beyond 64 are naturally
discarded:
long jumps = 1234567;
long increment = 0x9e3779b97f4a7c15L;
state = BigInteger.valueOf(state)
.add(BigInteger.valueOf(increment).multiply(BigInteger.valueOf(jumps)))
.longValue(); // narrowing primitive conversion
int jumpPower = 32;
state = BigInteger.valueOf(state)
.add(BigInteger.valueOf(increment).shiftLeft(jumpPower))
.longValue(); // narrowing primitive conversion
// Same as above by discarding overflow bits
state = state + (increment << jumpPower);
This is based on my understanding of BigInteger and signed/unsigned
arithmetic and should be verified in tests.
[4] Given the period of the SplitMix is 2^64, and the period may be less
than this in practice it may be better to only support jumps of e.g.
2^32 in a manner similar to those provided for the XorShiRo generators
where the state can be advanced a factor of the period, or just not
supports jumps. I can see the utility in jumping more than
Integer.MAX_VALUE (guaranteed unique outputs for the maximum array size)
but less than 2^32 is tending towards not very many random numbers from
the original instance before sequence overlap with the jumped instance.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
