> 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.
>
>>
>> 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. It is a nice to have. 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.
>
>> 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.
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. It is not actually possible
to jump forward a single instance. Only children are advanced.
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.
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.
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.
*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.
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.
>
>> 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());
}
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. 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.
>
> Regards,
> Gilles
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> <mailto:dev-unsubscr...@commons.apache.org>
> For additional commands, e-mail: dev-h...@commons.apache.org
> <mailto:dev-h...@commons.apache.org>
