These are chat archives for libmir/public

27th
Apr 2016
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:07
Hi @wilzbach -- it stalled largely because I felt that it wasn't a viable way forward. Class-based functionality gives you very easy reference-type semantics, but it biases you heavily towards allocation on the heap, via the GC. This is maybe tolerable for RNG instances, where maybe you only have one per thread, but it's not readily tolerable for stuff like RandomCover or RandomSample, which you might create many instances of in the inner loops of an application.
Note, I'm not saying don't explore the possibility -- it might be there's a way of resolving the allocation-based issues that didn't occur to me
But that was the major reason why I didn't push further forward with hap.random
Ilya
@9il
Apr 27 2016 20:12
@WebDrake Have you seen offer from Craig to be a mentor?
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:14
No ... ? In which forum thread?
John Colvin
@John-Colvin
Apr 27 2016 20:15
@WebDrake are the downsides of using emplace too much? If there truly isn't a an optimal solution possible, then maybe that would be a slightly ugly solution that achieves what is necessary?
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:19
I don't think I ever did
I'm honestly not sure, and would encourage it to be tried :-)
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:23
Ah, nice
If you both would welcome that, I'd happily give that consideration
If so I'll try to follow up tomorrow
@John-Colvin regarding emplace-based solutions -- how would you see that working for, say, a RandomSample instantiated in a UFCS range chain? e.g.
iota(100).randomSample(10, rng).filter!(a => a%2 == 0).writeln;
Ilya
@9il
Apr 27 2016 20:27
Your are wellcome) Just note that I reserve the right about API decisions for me and engineers from dlang core team
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:27
Your library, your API ;-)
Anyway, I'll drop Craig an email and see what we can organize
Ilya
@9il
Apr 27 2016 20:33
Hope Mir would not be only my library :-)
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:34
Well, that's something we're here to ensure, right? ;-)
Anyway, I obviously do have a certain amount of accumulated opinion about what's required from random-number-related functionality, but the thing to remember is that I haven't yet found a solution that satisfies my requirements
Hence, I'm very open to everyone's ideas
The thing that's important is to recognize that it's not sufficient to just find a solution for RNGs themselves but also for the range algorithms that use RNGs in their popFront()
Ilya
@9il
Apr 27 2016 20:38
Why not to store pointer to a basic RNG?
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:41
That works to give the RNG reference semantics as far as the range algorithm is concerned
But the range algorithm itself also needs to present reference-type semantics to everything that uses it
Look at the range chain I posted above
the output of randomSample should ideally be a stack-allocated range, but should present reference-type semantics to filter
Ilya
@9il
Apr 27 2016 20:43
this can be done with pointer, can not it?
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:44
Hmm, how would you see it working, without breaking the range chain?
Ilya
@9il
Apr 27 2016 20:44
randomSample accepts rng by ref and store its pointer internally
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:45
I mean, you can do something like,
auto sample = iota(100).randomSample(10, rng);
(&sample).filter!(a => a%2).writeln;
But what if instead of passing the filtered stuff to writeln, you wanted to return it from whatever function you are in?
Ilya
@9il
Apr 27 2016 20:46

But what if instead of passing the filtered stuff to writeln, you wanted to return it from whatever function you are in?

This looks like bad architecture.

Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:47
@9il but RandomSample has its own internal state beyond the RNG it wraps, you need reference semantics for the lot
Ilya
@9il
Apr 27 2016 20:47
If sample has pointer to RNG it has ref semantics. Or I misunderstand you?
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:48
No, it doesn't have ref semantics, because it has state in addition to the RNG alone
Which as currently implemented in phobos is value-type state
Ilya
@9il
Apr 27 2016 20:49
@disable this(); @disable this(this); ?
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:49
Same condition applies if you want to implement (say) a random distribution (e.g. normal distribution) as a range wrapping a uniform RNG instance
@9il but then you've just broken your ability to put randomSample in the middle of a UFCS chain
Ilya
@9il
Apr 27 2016 20:50
This is just bad architecture. rng should be passed to the latest step of a chain before accomulataion or allocation
Phobos ranges has not ref sematics excepts Appender, but it is output range
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:53
When you say RNG do you mean the actual underlying uniform RNGs that are the source of randomness? Or are you meaning all ranges that have randomness somewhere in their behaviour?
Ilya
@9il
Apr 27 2016 20:53
actual underlying uniform RNGs that are the source of randomness
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:54
Hmm well
Ilya
@9il
Apr 27 2016 20:54
We should not have any variable/range with randomness.
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:54
Let's take my example above, of iota being sampled and then filtered and finally passed off to writeln
Ilya
@9il
Apr 27 2016 20:55
yes
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:55
How would you see that working, in your scenario? I mean, in terms of your idea about the RNG being passed only to the last step of the chain before accumulation/allocation
Ilya
@9il
Apr 27 2016 20:58
Does not matter how many range steps are in chain after randomSample. But result after randomSample should already execute any RNG computations
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:58
Can you give me a code example?
Ilya
@9il
Apr 27 2016 20:58
So first example is OK, second with variable is wrong
auto sample = iota(100).randomSample(10, rng);
(&sample).filter!(a => a%2).writeln;
this is wrong
this is ok - iota(100).randomSample(10, rng).filter!(a => a%2 == 0).writeln;
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 20:59
Talk me through what you see as the problems in the first case
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 21:05
I have some opinions of my own, but I want to make sure I understand your point of view correctly
Ilya
@9il
Apr 27 2016 21:29
The idea is do not have random ranges declared as variables . we should use them only as intermediate values
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 21:30
Well, 2 thoughts on that
First, how would you enforce it?
John Colvin
@John-Colvin
Apr 27 2016 21:30
1) Isn’t that a special case of uniqueness? 2) How does that apply to ranges further down the chain, seeing as they just see a normal range?
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 21:30
Second, that seems like it might be rather restrictive?
@John-Colvin from my point of view, any range further down the chain is inherently a random range
John Colvin
@John-Colvin
Apr 27 2016 21:32
it gets a bit difficult, doesn’t it. Because if you cache some random numbers in an array, can you get that as a RandomRange?
Ilya
@9il
Apr 27 2016 21:33
  1. We have not such restrictions
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 21:33
@John-Colvin interesting point. I think it's not so important because the key thing here is that the RNG and any intermediate ranges have been consumed
@9il I think you'll have to explain that point in more detail ;-)
Ilya
@9il
Apr 27 2016 21:35
Will do tomorrow ) bb
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 21:35
Sure, looking forward to it :-)
@John-Colvin obviously if you cache some randomly-distributed values in an array, you run the risk of accidental re-use (leading to unwanted correlations), but that's an unavoidable problem that you have to deal with
Unless I'm misunderstanding your use-case? I assume you're not thinking of a range that caches intermediate values (e.g. how some normal distribution algorithms work) ... ?
(BTW I'm also needing to head off for the night, so shall we resume tomorrow?)
John Colvin
@John-Colvin
Apr 27 2016 21:39
I was just considering how to get the same guarantees for a cached set of values, and whether it was actually a more general problem not necessarily specific to PRNGs.
Forgetting anything like cacheing in an array for now: If the source of pseudo-randomness is held as a reference-type input range, then everything is ok, yes? (perhaps an obvious question, but I want to be certain I understand correctly).
sure, I should probably stop for the night as well
I think what I need is an elaboration/explanation of what you were saying about ranges that use random number generators in their popFront.
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 21:46

If the source of pseudo-randomness is held as a reference-type input range, then everything is ok, yes? (perhaps an obvious question, but I want to be certain I understand correctly)

I believe no, because ranges that use RNGs in their popFront() can have other internal state besides the RNG itself

So, if that state gets accidentally copied by value, you can have potential correlations that result
Example:
consider a simple range-based implementation of a normal distribution (e.g. as done in hap.random)
This generates 2 normally-distributed variates at a time, and caches them
So you only actually call on the RNG every other popFront()
John Colvin
@John-Colvin
Apr 27 2016 21:47
ah, yes, I think I see the problem. The cached values should never be inadvertently used in more “output” values than intended.
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 21:48
Exactly
If there's an accidental copy-by-value as it's handed over to the place it's consumed, you might wind up getting the same number each time you read from the distribution
Now, I think @9il's proposal that such ranges can only exist as interim parts of ranges that are immediately consumed, might be a very interesting simplifying factor
Because here, I think it might be sufficient that only the RNG needs to be a reference type
& then in that case it might be sufficient to just @disable this(this); on the RNGs
John Colvin
@John-Colvin
Apr 27 2016 21:50
Essentially that implies it is unique.
I think? hmm I’m not sure
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 21:51
Well, not in the sense of a singleton style uniqueness
You can have multiple different instances of the same RNG type
John Colvin
@John-Colvin
Apr 27 2016 21:51
I mean in the sense of std.typecons.Unique
Joseph Rushton Wakeling
@WebDrake
Apr 27 2016 21:52
But yes, if we assume Ilya's proposal is the correct one, then probably it would be a good idea to enforce uniqueness of RNG instances in the sense you mean
My questions are (i) whether his proposed way of doing things is relying on programmer virtue to never assign random ranges to variables, and (ii) if it's too strong a constraint on program design
But we should probably pick up that thread tomorrow ;-)
John Colvin
@John-Colvin
Apr 27 2016 23:04

I'll jot down a few notes here while I think of them, feel free to ignore for now.

Providing tools to prevent these library types being directly misused is very important, so we want to be able to solve the problem for fundamental PRNGs and our derived distributions, but making sure that e.g. a users implementation of a distribution range doesn’t incorrectly cache results from our PRNGs is beyond our remit. I.e. we attempt to enforce correct usage of the range types we define, but not the returns of front on those ranges.

So there are two basic approaches available (could each be implemented in multiple ways):

1) a reference type, so all the owners of a given instance have effectively linearised, “no-repeats" access to an infinite stream of psuedo-random numbers.

2) a unique type, so at any given point there is only one owner, and therefore the access to the PRN stream is also linearised, but any interleaving is explicit in code (have to have passed the unique resource, the PRNG).

When dealing with the usual PRNGs and other simple situations I feel fairly confident that either can be made to work safely, but I’m a little concerned about the consequences when dealing with e.g. MCMC ranges where the samples are inherently correlated. For those I think you should never have a reference type, because it could be too easy to end up with patterns that are equivalent to this:

MyRandomSampler sampler;
foreach(d; someData)
{
    foreach(i; 0 .. nRuns)
    {
        res[i] ~= runOneSimulationIteration(d, sampler.front);
        sampler.popFront();
    }
}

The path followed in res[0][0 .. $] will be highly correlated with the path in res[1][0 .. $] and so on, because e.g. res[3][6] used the next sample after res[2][6] despite being in different runs. This is obviously awful, but I think it might be easy to do the same hidden and by accident in a more complicated range-chaining-combining situation.

Fundamentally, if you set up a 2d grid of nRuns x outputDataLength you have to be very sure that - from the perspective of the stream of MCMC samples - you are traversing it along each run at a time, not across runs. Possible to get wrong with reference types, I think more difficult with unique types.

tldr: My thinking at the moment: Uncorrelated sampling is safe with reference or unique, correlated sampling is much safer with unique.

Are unique types restrictive? yes. But I think in the context of samplers it’s probably a good restriction.