View mode: basic / threaded / horizontal-split · Log in · Help
September 21, 2012
Re: Reference semantic ranges and algorithms (and std.random)
On Thursday, 20 September 2012 at 11:10:43 UTC, Jonathan M Davis 
wrote:
> [SNIP]
>
> - Jonathan M Davis

#1
Hey, I've been working on this (locally): I've made all the PRNGs 
reference ranges. It actually works perfectly. I took the "ensure 
initialized" route, as you suggested. I was able to take an 
approach that moved little code, so there is a clean distinction 
between the old "Payload", which was not touched (much), and the 
wrappers. The advantage is that the diff is very clean.

I was able to do this without adding or removing any 
functionality. Great!

Regarding the cost of "is initialized", I think I found a very 
good work around. I'll show it in a pull.

#2
Johannes Pfau: When asking for a generator, by default you get a 
reference prng. This is the _safe_ approach.

If somebody *really* wants to, they can always declare a 
PRNGPayload on the stack, but I advise against that as:
*Passing it by value could generate duplicate sequences
*Passing it by value (for certain PRNGs) can be prohibitively 
expansive.

But the option is there.

#3
The only thing I'm having an issue with is "save". IMO, it is 
exceptionally dangerous to have a PRNG be a ForwardRange: It 
should only be saved if you have a damn good reason to do so. You 
can still "dup" if you want (manually) (if you think that is 
smart), but I don't think it should answer true to 
"isForwardRange".

You just don't know what an algorithm will do under the hood if 
it finds out the range is saveable. In particular, save can be 
non-trivial and expensive...

I think if somebody really wants to be able to access some random 
numbers more than once, they are just as well off doing:
Type[] randomNumbers = myPRNG.take(50).array();

The advantage here is that at no point to you ever risk having 
duplicate numbers. (Take advances the reference range generator.

QUESTION:
If I (were to) deprecate "save", how would that work with the 
range traits type? If a range has "save", but it is deprecated, 
does it answer true to isForwardRange?
September 21, 2012
Re: Reference semantic ranges and algorithms (and std.random)
On Friday, 21 September 2012 at 13:19:55 UTC, monarch_dodra wrote:
> QUESTION:
> If I (were to) deprecate "save", how would that work with the 
> range traits type? If a range has "save", but it is deprecated, 
> does it answer true to isForwardRange?

Never mind I found out the answer: Using something deprecated is 
a compile error, so traits correctly report the change.
September 21, 2012
Re: Reference semantic ranges and algorithms (and std.random)
On Friday, September 21, 2012 15:20:49 monarch_dodra wrote:
> #3
> The only thing I'm having an issue with is "save". IMO, it is
> exceptionally dangerous to have a PRNG be a ForwardRange: It
> should only be saved if you have a damn good reason to do so. You
> can still "dup" if you want (manually) (if you think that is
> smart), but I don't think it should answer true to
> "isForwardRange".

It is _very_ crippling to a range to not be a forward range. There's lots of 
stuff that requires it. And I really don't see what the problem is. _Maybe_ 
it's okay for them to be input ranges and not forward ranges, but in general, 
I think that we need to be _very_ careful about doing that. It can be really, 
really annoying when a range is not a forward range.

> You just don't know what an algorithm will do under the hood if
> it finds out the range is saveable. In particular, save can be
> non-trivial and expensive...

It shouldn't be. It's a copy, and copy's are not supposed to be expensive. 
We've discussed this before with regards to postlbit constructors. Certainly, 
beyond the extra cost of having to new things up in some cases, they should be 
relatively cheap.

> QUESTION:
> If I (were to) deprecate "save", how would that work with the
> range traits type? If a range has "save", but it is deprecated,
> does it answer true to isForwardRange?

You'd have to  test it. It might depend on whether -d is used, but it could 
easily be that it'll be true as long as save exists.

- Jonathan M Davis
September 21, 2012
Re: Reference semantic ranges and algorithms (and std.random)
I've ran into the problem with Random, there are some bugs 
entered by bearophile. Since then they added

http://dlang.org/phobos/std_range.html#RefRange

but I haven't used it to see how well it solves the problem.
September 21, 2012
Re: Reference semantic ranges and algorithms (and std.random)
On Friday, 21 September 2012 at 19:47:16 UTC, Jonathan M Davis 
wrote:
> On Friday, September 21, 2012 15:20:49 monarch_dodra wrote:
>> #3
>> The only thing I'm having an issue with is "save". IMO, it is
>> exceptionally dangerous to have a PRNG be a ForwardRange: It
>> should only be saved if you have a damn good reason to do so. 
>> You
>> can still "dup" if you want (manually) (if you think that is
>> smart), but I don't think it should answer true to
>> "isForwardRange".
>
> It is _very_ crippling to a range to not be a forward range. 
> There's lots of
> stuff that requires it. And I really don't see what the problem 
> is. _Maybe_
> it's okay for them to be input ranges and not forward ranges, 
> but in general,
> I think that we need to be _very_ careful about doing that. It 
> can be really,
> really annoying when a range is not a forward range.

I know it is crippling, but that is kind of the entire point: If 
somebody wants to read the same numbers trough twice, he'd better 
have a damn good reason. For example, *even* with reference 
ranges:

----
auto rng = SomeReferenceForwardRange();
auto a = new int[](10);
auto b = new int[](10);
a.fill(rng);
b.fill(rng);
----

This will fill a and b with the *same* numbers (!), even though 
rng is a reference range (!) Arguably, the bug is in fill (and 
has since been fixed), but the point is that by the time you 
notice it, who knows how long you've debugged? And who knows 
which *other* algorithms will break your prnd?

Had the rng been only InputRange, the compilation would have 
raised an error. And the work around is also easy. Safety first, 
right?

It might not be worth deprecating *now*, but I do think it is a 
latent danger.

PS: In all of random, there is not one single use case for having 
a ForwardPrng. Just saying.

>> You just don't know what an algorithm will do under the hood if
>> it finds out the range is saveable. In particular, save can be
>> non-trivial and expensive...
>
> It shouldn't be. It's a copy, and copy's are not supposed to be 
> expensive.
> We've discussed this before with regards to postlbit 
> constructors. Certainly,
> beyond the extra cost of having to new things up in some cases, 
> they should be
> relatively cheap.

The copy of the reference is designed to be cheap (and is), yes 
(we've discussed this).

However, when you save, you have to duplicate the payload, and 
even considering that there is no postblit cost, you have 
strictly no control over its size:

LCG: 1 Int
XORShift: 5 Ints
MersenneTwister: 397 Ints
LaggedFib: (607 to 44497) ulongs or doubles

Not the end of the world, but not trivially cheap either.

>> QUESTION:
>> If I (were to) deprecate "save", how would that work with the
>> range traits type? If a range has "save", but it is deprecated,
>> does it answer true to isForwardRange?
>
> You'd have to  test it. It might depend on whether -d is used, 
> but it could
> easily be that it'll be true as long as save exists.
>
> - Jonathan M Davis

I just tested it btw:
without -d: isForwardRange: false
with    -d: isForwardRange: true

It is kind of the logical behavior actually.
September 22, 2012
Re: Reference semantic ranges and algorithms (and std.random)
On Friday, 21 September 2012 at 19:47:16 UTC, Jonathan M Davis 
wrote:
> On Friday, September 21, 2012 15:20:49 monarch_dodra wrote:
>> #3
>> The only thing I'm having an issue with is "save". IMO, it is
>> exceptionally dangerous to have a PRNG be a ForwardRange: It
>> should only be saved if you have a damn good reason to do so. 
>> You
>> can still "dup" if you want (manually) (if you think that is
>> smart), but I don't think it should answer true to
>> "isForwardRange".
>
> It is _very_ crippling to a range to not be a forward range. 
> There's lots of
> stuff that requires it. And I really don't see what the problem 
> is. _Maybe_
> it's okay for them to be input ranges and not forward ranges, 
> but in general,
> I think that we need to be _very_ careful about doing that. It 
> can be really,
> really annoying when a range is not a forward range.

Reference type ranges could have a payload property which would 
return the underlying value type range which would be a forward 
range. If you need a forward range, you could just use that.
September 25, 2012
Re: Reference semantic ranges and algorithms (and std.random)
On 18/09/12 17:05, monarch_dodra wrote:
> As you can see from the ouput, that is not very random. That's just the "tip of
> the iceberg". *Anything* in phobos that iterates on a range, such a fill,
> filter, or whatever, will not advance the PRNG, arguably breaking it.
>
> At best, a "global" PRNG will work, provided it is never ever passed as an
> argument to a method.

Just to note, we already have an existing problem with this in Phobos, with the 
RandomSample functionality.  See:
http://d.puremagic.com/issues/show_bug.cgi?id=8247
September 25, 2012
Re: Reference semantic ranges and algorithms (and std.random)
On Tuesday, 25 September 2012 at 16:15:24 UTC, Joseph Rushton 
Wakeling wrote:
> On 18/09/12 17:05, monarch_dodra wrote:
>> As you can see from the ouput, that is not very random. That's 
>> just the "tip of
>> the iceberg". *Anything* in phobos that iterates on a range, 
>> such a fill,
>> filter, or whatever, will not advance the PRNG, arguably 
>> breaking it.
>>
>> At best, a "global" PRNG will work, provided it is never ever 
>> passed as an
>> argument to a method.
>
> Just to note, we already have an existing problem with this in 
> Phobos, with the RandomSample functionality.  See:
> http://d.puremagic.com/issues/show_bug.cgi?id=8247

Thank you for bringing it up. The problem is indeed as you said, 
and making the PRNGs references types fixes it.

I have a pretty well developed first iteration. I hope that by 
the end of next week, I'll have something to show.

Right now, I'm at a crossroad between:
*Inserting (requested) new features, (forced stack allocation, 
pre-initialized ranges for performance)
*Strictly no new features, for an eventual (easier) breaking 
change.

The problem with inserting "workaround 'features'", is that you 
have to keep supporting even if it is not required anymore :p
September 27, 2012
Re: Reference semantic ranges and algorithms (and std.random)
On 25/09/12 18:36, monarch_dodra wrote:
> Thank you for bringing it up. The problem is indeed as you said, and making the
> PRNGs references types fixes it.
>
> I have a pretty well developed first iteration. I hope that by the end of next
> week, I'll have something to show.

That would be fantastic.  I'm a bit compromised right now time-wise but do ping 
me if I can do anything to help you test stuff, particularly wrt RandomSample.
October 26, 2012
Re: Reference semantic ranges and algorithms (and std.random)
On Thursday, 27 September 2012 at 10:06:54 UTC, Joseph Rushton 
Wakeling wrote:
> On 25/09/12 18:36, monarch_dodra wrote:
>> Thank you for bringing it up. The problem is indeed as you 
>> said, and making the
>> PRNGs references types fixes it.
>>
>> I have a pretty well developed first iteration. I hope that by 
>> the end of next
>> week, I'll have something to show.
>
> That would be fantastic.  I'm a bit compromised right now 
> time-wise but do ping me if I can do anything to help you test 
> stuff, particularly wrt RandomSample.

Well, it took me a month (I was working on other things), but I 
have provided a change to make PRNGs reference ranges.

The pull request is here:
https://github.com/D-Programming-Language/phobos/pull/893

Please review or comment.
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home