On 17/04/2019 16:43, Gilles Sadowski wrote:
Hello.
Le lun. 15 avr. 2019 à 01:03, Alex Herbert <alex.d.herb...@gmail.com> a écrit :
On 14 Apr 2019, at 01:31, Gilles Sadowski <gillese...@gmail.com> wrote:
Hello.
On 11/04/2019 13:22, Gilles Sadowski wrote:
[...]
Not adding a dedicated method would mean everyone has to do this:
JumpableUniformRandomProvider rng = (JumpableUniformRandomProvider)
RandomSource.create(…)
But adding a mirror methods:
JumpableUniformRandomProvider RandomSource::createJumpable(…)
LongJumpableUniformRandomProvider RandomSource::createLongJumpable(…)
Does seem to add clutter to RandomSource. If we leave it out for now it can be
added in the future.
+1 (for leaving out).
Is there scope for needing the Jumpable to be detected through the API? E.g.
add:
boolean RandomSource::isJumpable(RandomSource)
We would just need to maintain an EnumSet for Jumpable and likewise for
LongJumpable. Again more clutter to the RandomSource interface but perhaps less
so than a mirror create method that would throw IllegalArgumentException for
any RandomSource specified that is not Jumpable.
+1 (for leaving out for now).
[...]
I was hoping to avoid creating a duplicate class. But actually that
would be fine and easier for testing. The implementation is trivial anyway.
Why duplicate?
IIUC, shouldn't the existing "core" class define an additional constructor
that accepts the "K" argument. Then the current "SPLIT_MIX_64"
would use the default increment.
[Same as with "TWO_CMRES" and "TWO_CMRES_SELECT", no?.]
OK. That was where I should have gone to start with. I’ll do that.
I've just finished an initial implementation of the MSWS RNG that uses a
self-generated Weyl sequence. It works. So the idea for this can be
applied to SPLIT_MIX_64_K by using the same Weyl sequence generation in
both. Perhaps moving the code to create the Weyl sequence increment to
NumberFactory.
+1
OK. So I created a Jira ticket for the SPLIT_MIX_64_K. I’m not sure when I’ll
get around to doing this though. It seems less important than other tasks. It
may even be redundant if the only reason is to increase the state space for the
generator. Each generator would still only have a period of 2^64. You can just
create a lot of them with a weak assurance they will not overlap and that the
uniformity is statistically the same. Since there are of the order of 2^63
variants we are not going to be able to test this and would have to rely on the
theory behind it.
If we add Jumpable to SplitMix with jumps of 2^32 and 2^48 then you can create
either 2^32 rngs with no overlap for the first 2^32 output numbers or 2^16 rngs
that can each be jumped 2^16 times with no overlap for the first 2^32 output
numbers. That is a lot for a small parallel situation and does have the
assurance of no overlap. Any parallel usage where longer sequences are expected
to be used can use one of the XorShiRo generators.
I'm a bit lost here. I thought that "SplitMix64" did not provide
"jump",
The state it is a linear sum. So can be jumped very easily.
y = mx + c
c is the current Weyl state, m the number of transitions and x the Weyl
increment. So we can make SplitMix Jumpable. The maximum jump length is
2^64 which will wrap the state.
hence the
"Weyl way" to ensure no-overlap, with high probability (why "weak assurance"?)
I used the term "weak assurance" as opposed to "concrete assurance". The
wording used by the JDK is "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 object". It is a bit of semantics.
Anyways, I agree that SPLIT_MIX_64_K is low priority, but especially if we
cannot ensure that the added flexibility does not come with unsuspected
drawbacks (?). [IIRC, the article about "TwoCmres" reported experiments for
choosing the (hard-coded) values that do produce good sequences.]
The likelihood of overlap is 1/[the number of different Weyl sequences].
This is around 2^-63. So it is small. However the base implementation
for SplitMix uses a specific Weyl sequence increment based on the golden
ratio. I do not know the original of this. For example is it better that
any other irrational number converted to an integer, e.g. pi, Euler's
number (e), sqrt(2)? The irrational number comes from the origin of the
Weyl sequence which is based on irrationals. But there may be no reason
that the golden ratio was chosen rather than any other source irrational.
Does the non-overlap weak assurance take into account the fact that
there are no irrational numbers in a truncated representation (like the
one stored in a computer)?
I would say that the 'weak assurance'/'very unlikely' statements allude to the
fact that no-one has actually tested all the 2^63 different Weyl sequences
after they pass through the hash mixing function to see if they output the same
sequence as any other, or are weaker as random generators. It would be quite a
task. So you cannot say they will not overlap, just that it probably will not.
And you cannot say much about the quality of the generator beyond the results
of those you have tested. (But this is the same for any large state space
generator.)
Isn't it why those "internal" numbers are carefully selected (like in
"TwoCmres"), because they generate better sequences?
That uses a multiply, rotate and subtraction on a number. So the multiply and
rotate have been tested to maximise the period of the sequence, and/or the
quality of the output. With a Weyl sequence it is proven to have a period of
2^64 (for a long) if the increment is odd. However that sequence then has to be
mixed to a decent uniform output. I’ve not read the details on the mixing
functions and how they are derived or tested to so would not want to comment
too much. My guess would be that the mixing of bits in the long is more random
if the bits change a lot each step. So using the Golden ratio, that has a high
number of state changes across the 64-bit, to create the sequence works well.
Using 1, which would not change many bits at each step in the sequence, would
be bad.
I don't feel confident that "Commons RNG" should decide how to generate
the numbers to be used in place of the one hard-coded in the reference
algorithm (Golden ratio).
As discussed, we could provide
1. "customizable" implementations for which the "Weyl" number
can be passed at construction (cf. "SPLIT_MIX_63_K"), and
2. an *example* code of how good "K" numbers could be generated
(e.g. taking any number and boosting the number of transitions).
On the subject of splitting verses jumping:
Jumping seems to be a case where the limit of the multi-threaded
scenario is known beforehand, e.g. a simulation with 1024 parallel
tasks, each task with a known limit on the count of random numbers
required. So if your jump length is above the number of random numbers
required for each task you can jump to get a single generator for each
task and ensure no overlap.
Split is used when the multi-threaded scenario is not known. This is a
case for SplittableRandom which is used in parallel algorithms which use
forking. The point at which a fork will occur and the task size of the
fork are not known beforehand. The generator is able to create new
generators for each fork that will very unlikely overlap with any other
generator currently in use. For SplittableRandom the probability of the
same generator is about 2^-63. The probability of overlap is reduced
further as the start point of the sequence is variable too and the
length of the sequence that is consumed is not known. So if the number
of forks is much less than 2^63 (which it should be) then split will
suffice in this situation.
I'm not convinced that we should add complexity to the API without
a use-case that would require
* fork-join,
* a RNG that cannot be "SplittableRandom”.
I think that Splittable as we are discussing it is essentially a mix of
functionality:
UniformRandomProvider rng
Supplier<UniformRandomProvider> rngSupplier
The Splittable interface just nicely allows you to create an algorithm that
declares that it wants a random generator but may actually want more than one
because it may create multiple threads. The number of threads is unknown so it
needs to be able to create generators as it goes.
For now I am fine with not putting it into the library. I do not see it as
essential.
Thanks.
It is a nice to have.
As per the above, given the "SPLIT_MIX_64_K" version of an algorithm, I'd rather
let the user implement what he needs:
for (int i = 1; i < numThreads; i += 2) {
final long k = boostTransitions(i); // User-defined.
final UniformRandomProvider rng =
RandomSource.create(SPLIT_MIX_64_K, k); // Commons RNG.
startProcessingThread(rng); // User-defined.
}
But as you said it does raise the question of when (and justifying why) we
support if for each of the generators.
Given that SplittableRandom is designed to support the Java framework, is not
extensible (is a final class) and so seems to be a closed solution to fork-join
in Java leaving it out of the API until a concrete use case for it occurs seems
sensible.
I have an algorithm that uses a set number of tasks to do random
splitting of a dataset. The dataset is shuffled before the task so even
if the same generator was used the output would work. Currently I create
a new generator to allow parallel computation but I could split a master
one or use a jumpable. Splitting would be faster than jumping for this
scenario and perfectly acceptable.
Do you mean that most of the total computing time is taken
by instantiating the generator?
No. So speed of splitting verses instantiating the generator is mute. My point
was that I just need a new thread safe instance. A copy would be fine. A split
would be fine. A new instance would be fine. That algorithm was pre Java 8. I
could just update it to use SplittableRandom. It is not using any of the
sampling functionality that hands a UniformRandomProvider to another class. The
RNG is used for shuffling and subset sampling so just needs nextInt(int).
I’ve got a bit of homework to find a case where SplittableRandom comes into its own
beyond just offering Supplier<UniformRandomProvider> as part of it’s API.
This leans me back towards adding a Splittable interface. The conditions
for a split would be that the split creates a new instance based on the
current state of the generator and updates the state. This allows split
to be called repeatedly on the same generator to get new distinct
instances that will not coincide with very high probability. It would be
akin to non-synchronized self-construction. This would then be faster
than using RandomSource.create because that uses synchronized seed
generation.
If the seed auto-generation is the issue, why not bypass it (by providing
one's own seed)?
Using a generator's state as a seed for another instance seems but a
particular choice from the seed space.
I think the reason to use ones own mixed up state as the seed is to ensure that
the state of the new generator is different. The implementations I have seen do
not actually check this is true so it just a probability gamble anyway. No
different from creating a new seed and instance. So it is just for convenience.
IMO, less risk by leaving it out too.
This opens up more generators for use in recursive forking
algorithms that may not care if the two forks have the same generator
but require it to be created fast and thread local. So perhaps do not
support it for JDK (because it is a bad generator) and rule out those
with long initialisation routines TwoCmres, MT, etc. and perhaps also
ruling out those with large states (e.g. Well44497b).
Then we have to explain why "split" is not provided despite it could
be and could be requested by users with a different sense of what
is fast enough for some purpose.
On the subject of jumping we have three options:
1. jump advances the state and returns a copy with the advanced state.
2. jump advances the state and returns a copy with the old state.
3. jump advances the state. Add a copy method.
I think we ruled out number 3 as having a copy command is deemed to be
prone to misuse if using the same copy in multiple places.
Option 1 I think has an issue in that if you do 1 jump and believe you
have two non-overlapping generators you will be wrong. Take this case:
JumpableUniformRandomProvider rng1 = ...;
UniformRandomProvider rng2 = rng1.jump();
In option 1 rng1 and rng2 are actually the same.
In option 2 rng1 and rng2 are in different states where rng1 is far
ahead of rng2. So the returned state (rng2) can be documented to not
overlap the existing generator (rng1) until the jump length has consumed
by calls to generate numbers.
Note that neither option provides a loophole for a poor man's copy.
Option 1 would create a copy but it would be of a state far ahead
because it is after a jump. Option 2 creates a copy of the current state
but then the current state is changed by the jump so you don't have a copy.
I'm not sure my preferred option was mentioned. After this statement:
rng2 = rng1.jump();
the state of "rng1" is the same as before the call; the newly-created
"rng2" instance has its state far away.
This was mentioned. I’d ruled it out as jumping the same generator would not
move it anywhere and always return the same child. The user would have to:
JumpableURP rng1 = …
JumpableURP rng2 = rng1.jump();
JumpableURP rng3 = rng2.jump();
Rng1 is where it started.
Yes; my point was that "jump" could be considered a factory method.
OK so this results in:
/**
* Some summary.
*/
public interface JumpableUniformRandomProvider extends
UniformRandomProvider {
/**
* Creates a copy of the UniformRandomProvider and advances the
state of the copy.
* The state of the current instance is not altered. The state of
the copy will be
* advanced an equivalent of {@code n} sequential calls to a method
that updates the
* state of the provider.
*
* @return the copy with an advanced state
*/
JumpableUniformRandomProvider jump();
}
This can be documented in an implementation as:
public class MyJumpingRNG implements JumpableUniformRandomProvider {
/**
* {@inheritDoc}
*
* <p>The jump size {@code n} is the equivalent of {@code 2^64}
calls to
* {@link UniformRandomProvider#nextLong() nextLong()}.
*/
@Override
public JumpableUniformRandomProvider jump() {
// TODO Auto-generated method stub
return null;
}
}
Do we add a second interface for LongJumpableUniformRandomProvider?
So the options are (in all cases returning the copy):
1. createAndJumpCopy
2. copyAndJumpParent
3. jumpParentAndCopy
4. jump and copy separately
1. Your preferred option. A copy of the state is made. The state is advanced in
the copy and returned. But when called repeatedly it will get the same
generator and code must be organised appropriately.
We could provide a convenience method in "RandomSource":
public UniformRandomProvider[] jump(int n,
JumpableUniformRandomProvider parent) {
final UniformRandomProvider[] rngs = new UniformRandomProvider[n];
UniformRandomProvider tmp = parent;
for (int i = 0; i < n; i++) {
rngs[i] = restrict(tmp);
tmp = tmp.jump();
}
return rngs;
}
+1. Remove the need for the user to repeat boiler plate code.
Same sort of idea of longJump() too.
It is not actually possible to jump forward a single instance. Only children
are advanced.
A feature: There is only one way to alter the state of an instance
(i.e. a call to "next()").
OK.
2. My preferred option*. A copy of the state is made. The current state is
advanced and the old state that was left behind is returned. This can be called
repeatedly to create new generators that are periodically spaced behind the
current generator. Or you can ignore the return value and just use it to jump
forward.
Allows shooting oneself in the foot (e.g. when the return value is not ignored,
and then used to make another jump, whose sequence will overlap with the
original parent's).
3. The current state is advanced and a copy returned. After a single call to
this method you have two generators that are the same.
Challenge: Find a use-case that is not broken. ;-)
4. My other preferred option*. The most flexible API. Jump just advances the
state. It is left to the user to decide if they copy before or after the jump.
Since the jump will be a void method the user will have to think about what
copy they want to use. But it does expose copy functionality.
I still fail to see the need to be able to do that, if the purpose is to
allow instantiating RNGs that do not overlap for a definite number
of calls to "next()".
OK. With the factory method for jumping in RandomSource then it will be
easy to a priory set-up your RNGs for a parallel simulation.
*A bit of cheating to have two preferences.
I guess this is different from how it's usually provided in C implementations.
But it is more in line with the intended usage: create an instance that will
not overlap with its "parent". The semantics is "createAndJump()”.
In the c implementation you would have to decide when to copy the state, before
or after the jump. The jump just advances the state.
Yes, because it would be a waste of a costly system call to do a copy
if only a "jump" is needed. But in Java the copy is much cheaper: Doing
rng.jump(); // "jump" altered the state.
// Use "rng".
vs.
rng = rng.jump(); // "jump" did not alter the state.
// Use "rng".
Would not make any difference performance-wise in sensible use-cases (i.e.
where the sequence is long enough that "jump" was needed in the first place).
So perhaps adding a copy() to the JumpableUniformRandomProvider interface is
the least prone to having design challenges later from a user who wants
createAndJump rather than jumpAndCopy type functionality.
Am I missing something that actually requires "copy"?
No. It was just easy to split the functionality and allow the user to
choose. The above copy and jump will work fine.
To get a copy of the current state would require saving the state using
the RestoreableUniformRandomProvider, doing either of the jump options
to get an instance of the same class, then restoring the state to both.
With my proposed option, nothing happens to the "parent"; hence the
above is never necessary IIUC.
I feel that createAndJump makes writing in loops or forking less elegant since
the controller of the jumps is the one who should have the generator that will
be jumped repeatedly:
JumpableURP rng1 = …
for ( ;; ) {
JumpableURP advancedCopy = rng1.createAndJumpCopy();
forkSomething(rng1);
rng1 = advancedCopy; // To move control forward
}
JumpableURP rng1 = …
for ( ;; ) {
forkSomething(rng1.copyAndJumpParent());
}
With the convenience method proposed above, the difference becomes moot:
UPR[] rngs = RandomSource.jump(12, rng1);
for (i = 0 ; i < rngs.length; i++) {
forkSomething(rngs[i]);
}
JumpableURP rng1 = …
for ( ;; ) {
forkSomething(rng1.copy());
rng1.jump();
}
// This one liner is not the same effect as the first fork will have an
advanced (jumped) state.
JumpableURP rng1 = …
for ( ;; ) {
forkSomething(rng1.jump().copy());
}
Thoughts?
To rule out doing this via the RestoreableUniformRandomProvider
functionality would require a method in RandomSource to restrict the
implementation to just the defined interface like the unrestorable method:
UniformRandomProvider unrestorable(UniformRandomProvider delegate)
Becomes:
UniformRandomProvider restrict(UniformRandomProvider delegate)
RestorableUniformRandomProvider restrict(RestorableUniformRandomProvider
delegate)
JumpableUniformRandomProvider restrict(JumpableUniformRandomProvider
delegate)
LongJumpableUniformRandomProvider
restrict(LongJumpableUniformRandomProvider delegate)
The correct method would have to be selected by casting:
LongJumpableUniformRandomProvider delegate = ...
JumpableUniformRandomProvider restrict((JumpableUniformRandomProvider)
delegate)
Or do not use overloaded methods and (with A, B, C, D appropriately named):
UniformRandomProvider restrictA(UniformRandomProvider delegate)
RestorableUniformRandomProvider
restrictB(RestorableUniformRandomProvider delegate)
JumpableUniformRandomProvider restrictC(JumpableUniformRandomProvider
delegate)
LongJumpableUniformRandomProvider
restrictD(LongJumpableUniformRandomProvider delegate)
A move to Java 8 would allow the restrict method for the interface to be
added as a static method to the interface itself which would be neater.
I think that we could discuss "restrict" options separately.
OK. Let’s sort out exactly what the Jump interface will be. Adding a restrict
option is easy in practice but the choice not so obvious. A look through the
Java API for similar things would help.
For example I have found methods:
Executors.unconfigurableXYZ (Java 1.8)
Collections.synchronizedX
Collections.unmodifiableX
So ‘unconfigurable’ seems to match.
Not so sure. At this point, I prefer "restrict" (to the URP interface).
OK. As long as it is clear from the method name what happens.
It stops any configuration of the executor implementation and just exposes the
pure Executor interface. The Collections methods either add some function
(synchronized) or take away functionality (unmodifiable).
A further search through the Java API is for another day.
Best,
Gilles
---------------------------------------------------------------------
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
