www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - hap.random: a new random number library for D

reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
Hello all,

Some of you may remember my earlier draft of a class-based 
std.random successor:
http://forum.dlang.org/thread/cyytvhixkqlbwkmiugex forum.dlang.org

Following revisions made in response to feedback, and some 
further development, I decided that it would be best to release 
the results as a dub package with a new library name:
http://code.dlang.org/packages/hap

Source code and documentation is available here:
https://github.com/WebDrake/hap
http://code.braingam.es/hap/random/

I've also written a blog post describing new features and the 
motivations behind this library:
http://braingam.es/2014/06/hap-random-a-new-random-number-library-for-d/

I think that hap.random fixes certain fundamental design issues 
with std.random.  However, this needs to be put to the test "in 
the wild", so I'd really appreciate it if as many people as 
possible could try it out with their code, and report on the 
experience:

    * Does it run faster, slower, etc?

    * Do any undesirable memory allocation issues arise?

    * Is the API (broadly similar but not identical to std.random)
      pleasant to use?

If it proves to be effective for everyone, then I will begin the 
process of submission as a new Phobos module.

Thanks in advance for all testing and feedback.

Best wishes,

     -- Joe
Jun 09 2014
next sibling parent reply "Ryan Voots" <simcop2387 simcop2387.info> writes:
On Monday, 9 June 2014 at 18:09:21 UTC, Joseph Rushton Wakeling 
wrote:

 I've also written a blog post describing new features and the 
 motivations behind this library:
 http://braingam.es/2014/06/hap-random-a-new-random-number-library-for-d/

 I think that hap.random fixes certain fundamental design issues 
 with std.random.  However, this needs to be put to the test "in 
 the wild", so I'd really appreciate it if as many people as 
 possible could try it out with their code, and report on the 
 experience:

    * Does it run faster, slower, etc?

    * Do any undesirable memory allocation issues arise?

    * Is the API (broadly similar but not identical to 
 std.random)
      pleasant to use?


It definitely looks interesting.  The 64bit MT is definitely 
something I'm after.  I have a particularly strange need with 
PRNGs though.  I need to easily make a bunch of child RNGs based 
off a master RNG.  Nothing cryptographic about it but solely to 
make reasoning about generating random maps and worlds easier.  
That way changing one part of the algorithm (say city placement) 
doesn't affect how the map itself is generated, or vice-versa.  
It sounds like the reference types here would actually make my 
life much easier since I'd need to pass in RNGs into each section 
of the generation and would let me be a bit looser with how 
carefully i have to control access to them which is a good thing.
Jun 09 2014
parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Monday, 9 June 2014 at 18:51:53 UTC, Ryan Voots wrote:

 It definitely looks interesting.  The 64bit MT is definitely 
 something I'm after.  I have a particularly strange need with 
 PRNGs though.  I need to easily make a bunch of child RNGs 
 based off a master RNG.  Nothing cryptographic about it but 
 solely to make reasoning about generating random maps and 
 worlds easier.  That way changing one part of the algorithm 
 (say city placement) doesn't affect how the map itself is 
 generated, or vice-versa.  It sounds like the reference types 
 here would actually make my life much easier since I'd need to 
 pass in RNGs into each section of the generation and would let 
 me be a bit looser with how carefully i have to control access 
 to them which is a good thing.


Sounds interesting -- I seem to recall we had some discussion
about this a while back ... ?  Anyway, glad to hear that the
library may be useful for you.  Let me know how you get on! :-)
Jun 09 2014
prev sibling next sibling parent reply "Chris Cain" <zshazz gmail.com> writes:
Awesome! I'll definitely check this out :)

Would there be any chance of additional contributions, such as an 
ISAAC RNG implementation, being accepted? I wouldn't go as far as 
to guarantee it for crypto purposes, but I've been messing around 
with an implementation recently and wouldn't mind porting it over 
to D (it's based on the public domain implementation found on 
this website: http://burtleburtle.net/bob/rand/isaacafa.html )

So far the numbers it puts out appear to be pretty good from my 
observations, PLUS it's really fast for a large number of outputs 
(it costs a lot up-front, however).

I also have a variation of "ISAAC+" as described by the paper 
here: http://eprint.iacr.org/2006/438.pdf

The problem I have with "ISAAC+", though, is that the paper 
incorrectly describes the original ISAAC algorithm (Algorithm 1.1 
fails to `xor a` at line 6) so it's unclear whether the paper 
actually solves a problem. Furthermore, I'd really prefer to keep 
that xor regardless (because it may have simply been an oversight 
but intended) so it's hard (I don't want to) to really call it 
"ISAAC+" since it is notably different than the paper's 
description.

That said, it's a paper that comes up often enough in discussions 
about ISAAC that people suggest a desire for it.
Jun 09 2014
parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 10 June 2014 at 06:53:46 UTC, Chris Cain wrote:

 Awesome! I'll definitely check this out :)


Thanks, that would be great!


 Would there be any chance of additional contributions, such as 
 an ISAAC RNG implementation, being accepted? I wouldn't go as 
 far as to guarantee it for crypto purposes, but I've been 
 messing around with an implementation recently and wouldn't 
 mind porting it over to D (it's based on the public domain 
 implementation found on this website: 
 http://burtleburtle.net/bob/rand/isaacafa.html )


Yea, it'd be great to have submissions like this.  I plan on
having a hap.random.crypto as another experimental module (i.e.
not included if you do "import hap.random", copiously labelled as
experimental until it's had a security review, etc.) so
guaranteeing crypto possibilities straight away is not a problem.
   Part of the point of hap is that it gives us a place where we
can get things wrong and correct them. ;-)

I think I'll create a 1.x.x branch for the current release
process and add a crypto module shortly in the ~master branch,
I'll ping you when that's done.


 So far the numbers it puts out appear to be pretty good from my 
 observations, PLUS it's really fast for a large number of 
 outputs (it costs a lot up-front, however).

 I also have a variation of "ISAAC+" as described by the paper 
 here: http://eprint.iacr.org/2006/438.pdf

 The problem I have with "ISAAC+", though, is that the paper 
 incorrectly describes the original ISAAC algorithm (Algorithm 
 1.1 fails to `xor a` at line 6) so it's unclear whether the 
 paper actually solves a problem. Furthermore, I'd really prefer 
 to keep that xor regardless (because it may have simply been an 
 oversight but intended) so it's hard (I don't want to) to 
 really call it "ISAAC+" since it is notably different than the 
 paper's description.

 That said, it's a paper that comes up often enough in 
 discussions about ISAAC that people suggest a desire for it.


Why not write to the paper's author and ask about it?  It may
seem like a small thing, but they'll probably be grateful for the
interest and feedback.
Jun 10 2014
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 Thanks in advance for all testing and feedback.


I have appreciated to use this generator (but I am not yet sure 
how much good it is. I have seen it's fast and sufficiently good 
for some of my simpler purposes):
http://en.literateprograms.org/R250/521_%28C%29

------

Is it worth having a fully pure generator that takes a constant 
state and returns the modified state? (The state should be small, 
so Mersenne Twister is not fit for this). Writing such generator 
is easy, but then how do you use it with the API of the functions 
of the random module?

Bye,
bearophile
Jun 10 2014
next sibling parent reply "Kagamin" <spam here.lot> writes:
Pass it by reference, I see no reason why MT can't be pure.
Jun 10 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Kagamin:


 Pass it by reference, I see no reason why MT can't be pure.


I meant strongly pure :-)

Bye,
bearophile
Jun 10 2014
parent "Kagamin" <spam here.lot> writes:
On Tuesday, 10 June 2014 at 10:57:32 UTC, bearophile wrote:

 Kagamin:


 Pass it by reference, I see no reason why MT can't be pure.


 I meant strongly pure :-)


I'm afraid, this pure rng pattern precludes all pure 
optimizations, so it's effectively weakly pure.
Jun 11 2014
prev sibling parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 10 June 2014 at 10:37:17 UTC, Kagamin wrote:

 Pass it by reference, I see no reason why MT can't be pure.


For what it's worth, the Mersenne Twister in hap.random is 
already weakly pure (.front and .popFront are both pure methods).
Jun 10 2014
prev sibling parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 10 June 2014 at 10:21:39 UTC, bearophile wrote:

 I have appreciated to use this generator (but I am not yet sure 
 how much good it is. I have seen it's fast and sufficiently 
 good for some of my simpler purposes):
 http://en.literateprograms.org/R250/521_%28C%29


Should be straightforward enough to implement. :-)


 Is it worth having a fully pure generator that takes a constant 
 state and returns the modified state? (The state should be 
 small, so Mersenne Twister is not fit for this). Writing such 
 generator is easy, but then how do you use it with the API of 
 the functions of the random module?


The API as given is of course designed to create ranges of random 
variates, and that in turn means that you're dealing with weakly 
pure class methods.

However, I don't see any reason why one couldn't have a strongly 
pure function that purely transforms state, which could be 
wrapped by an RNG class or otherwise used as needed.
Jun 10 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 However, I don't see any reason why one couldn't have a 
 strongly pure function that purely transforms state, which 
 could be wrapped by an RNG class


So can you can generate random values in strongly pure functions 
with this? You can allocate the RNG class inside the function... 
If that's right, then is this simple strongly pure random 
generator worth adding to std.random2?

Bye,
bearophile
Jun 10 2014
parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 10 June 2014 at 11:32:54 UTC, bearophile wrote:

 So can you can generate random values in strongly pure 
 functions with this? You can allocate the RNG class inside the 
 function... If that's right, then is this simple strongly pure 
 random generator worth adding to std.random2?


Forgive me if I'm missing something obvious, but as it stands I 
don't see how the R250/521 algorithm you pointed me to can be 
strongly pure.  As it's defined in the link you pointed me to, 
it's accessing (and updating) global mutable state.

It would surely be possible to define it to take as input 
constant buffers, and to return constant buffers, which ought to 
allow purity -- but wouldn't that be a memory allocation 
nightmare?

Can you clarify what you're thinking of here it terms of D's 
strong purity?
Jun 10 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 Forgive me if I'm missing something obvious, but as it stands I 
 don't see how the R250/521 algorithm you pointed me to can be 
 strongly pure.


Sorry, the R250/521 idea and the strongly pure idea are unrelated 
to each other.



 but wouldn't that be a memory allocation nightmare?


For the strongly pure random generator we should choose a 
generator with a small internal state (let's say less than 5 CPU 
words, they get passed by immutable value).

Bye,
bearophile
Jun 10 2014
parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 10 June 2014 at 21:02:54 UTC, bearophile wrote:

 Sorry, the R250/521 idea and the strongly pure idea are 
 unrelated to each other.


Ah, good.  That makes things simpler.  I'll implement R250/521 
for you, though.


 For the strongly pure random generator we should choose a 
 generator with a small internal state (let's say less than 5 
 CPU words, they get passed by immutable value).


We might be able to rework the Xorshift generators in this way -- 
they all rely on a very small internal state.  It'd be 
interesting to see if this has any speed implications.
Jun 10 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 I'll implement R250/521 for you, though.


Please stop, I am not worth that, and I don't even know how much 
good that generator is. So for you it's better to focus on more 
important matters of the new random module. Extra generators can 
be added later if needed.



It'd be interesting to see if this has any speed implications.


Passing several cpu words by value for each generated value seems 
not very efficient. But this generator is for special situations, 
so a certain performance loss could be acceptable. And if the 
compiler is able to inline the functions, the data transfer 
overhead is removed, and most of the performance loss is restored 
(but I don't know if non-templated Phobos functions get inlined).

Bye,
bearophile
Jun 10 2014
parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 10 June 2014 at 23:48:09 UTC, bearophile wrote:

 Please stop, I am not worth that, and I don't even know how 
 much good that generator is. So for you it's better to focus on 
 more important matters of the new random module. Extra 
 generators can be added later if needed.


After all the advice and help you've given me (and the rest of 
this community) over the course of years, it's really a pleasure 
to be able to offer you a small favour like this.  But of course 
it could be fun to first run things through e.g. the TestU01 
suite ...


 Passing several cpu words by value for each generated value 
 seems not very efficient. But this generator is for special 
 situations, so a certain performance loss could be acceptable. 
 And if the compiler is able to inline the functions, the data 
 transfer overhead is removed, and most of the performance loss 
 is restored (but I don't know if non-templated Phobos functions 
 get inlined).


Well, I think it's worth experimenting with.  For clarity, I 
wasn't suggesting modifying the existing Xorshift code, but 
creating a separate implementation in strongly pure style, and 
seeing how that differs performance-wise from what already exists.

I guess I might also consider finally getting my head round 
monads, and relating that to RNG design ... :-)
Jun 10 2014
prev sibling next sibling parent reply "Chris Cain" <zshazz gmail.com> writes:
Hey again Joe,

I had an opportunity to give the entire code a good once over 
read and I have a few comments.

1. Biggest thing about the new hap.random is how much nicer it is 
to actually READ. The first few times I went through the current 
std.random, I remember basically running out of breath. 
hap.random was almost a refreshing read, in contrast. I'm 
guessing it has a lot to do with breaking it down into smaller, 
more manageable pieces. Regardless, good work on that. I suspect 
it'll make it easier to contribute to in the future.
2. Something I'd really like to see is for the seed-by-range 
functions to take the range by reference instead of by value to 
ensure that the seed values used are less likely to be used in 
another RNG inadvertently later. Basically, I envision a similar 
problem with seedRanges as we currently have with RNGs where we 
have to make sure people are careful with what they do with the 
ranges in the end. This should cover use cases where users do 
things like `blah.seed(myEntropyRange.take(3))` as well, so that 
might take some investigation to figure out how realistic it 
would be to support.
3. I'd also REALLY like to see seed support ranges/values giving 
ANY type of integer and guarantee that few bytes are wasted (so, 
if it supplies 64-bit ints and the generator's internal state 
array only accepts 32-bit ints, it should spread the 64-bit int 
across two cells in the array). I have working code in another 
language that does this, and I wouldn't mind porting it to D for 
the standard library. I think this would greatly simplify the 
seeding process in user code (since they wouldn't have to care 
what the internal representation of the Random state is, then).
4. I'd just like to say the idea of using ranges for seeds gets 
me giddy because I could totally see a range that queries 
https://random.org for true random bits to seed with, wrapped by 
a range that zeroes out the memory on popFront. Convenient and 
safe (possibly? Needs review before I get excited, obviously) for 
crypto purposes!
5. Another possible improvement would be something akin to a 
"remix" function. It should work identically to reseeding, but 
instead of setting the internal state to match the seed (as I see 
in 
https://github.com/WebDrake/hap/blob/master/source/hap/rando
/generator.d#L485), 
remixing should probably be XOR'd into the current state. That 
way if you have a state based on some real entropy, you can 
slowly, over time, drip in more entropy into the state.
6. I'd like to see about supporting xorshift1024 as well 
(described here: http://xorshift.di.unimi.it/ and it's public 
domain code, so very convenient to port ... I'd do it too, of 
course, if that seems like an okay idea). This is a really small 
thing because xorshift1024 isn't really much better than 
xorshift128 (but some people might like the idea of it having 
significantly longer period).


 Why not write to the paper's author and ask about it?


Done :) ... if I get a response, I'll make sure to incorporate 
everything said.
Jun 10 2014
next sibling parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 10 June 2014 at 23:08:33 UTC, Chris Cain wrote:

 I had an opportunity to give the entire code a good once over 
 read and I have a few comments.


Thanks! :-)


 1. Biggest thing about the new hap.random is how much nicer it 
 is to actually READ. The first few times I went through the 
 current std.random, I remember basically running out of breath. 
 hap.random was almost a refreshing read, in contrast. I'm 
 guessing it has a lot to do with breaking it down into smaller, 
 more manageable pieces. Regardless, good work on that. I 
 suspect it'll make it easier to contribute to in the future.


That's great to hear, as it was a design goal.  I think there 
will probably at some point be a need to separate things further 
(e.g. std.random.generator will probably have to be separated as 
will std.random.distribution) but always keeping the principle of 
implementing packages to make it possible to just "import 
hap.random" (or "import hap.random.generator", or whatever).


 2. Something I'd really like to see is for the seed-by-range 
 functions to take the range by reference instead of by value to 
 ensure that the seed values used are less likely to be used in 
 another RNG inadvertently later. Basically, I envision a 
 similar problem with seedRanges as we currently have with RNGs 
 where we have to make sure people are careful with what they do 
 with the ranges in the end. This should cover use cases where 
 users do things like `blah.seed(myEntropyRange.take(3))` as 
 well, so that might take some investigation to figure out how 
 realistic it would be to support.


Yea, that's an interesting point.  I mean, you'd hope that 
myEntropyRange would be a reference type anyway, but every little 
helps :-)


 3. I'd also REALLY like to see seed support ranges/values 
 giving ANY type of integer and guarantee that few bytes are 
 wasted (so, if it supplies 64-bit ints and the generator's 
 internal state array only accepts 32-bit ints, it should spread 
 the 64-bit int across two cells in the array). I have working 
 code in another language that does this, and I wouldn't mind 
 porting it to D for the standard library. I think this would 
 greatly simplify the seeding process in user code (since they 
 wouldn't have to care what the internal representation of the 
 Random state is, then).


That would be very cool.  Can you point me at your code examples?


 4. I'd just like to say the idea of using ranges for seeds gets 
 me giddy because I could totally see a range that queries 
 https://random.org for true random bits to seed with, wrapped 
 by a range that zeroes out the memory on popFront. Convenient 
 and safe (possibly? Needs review before I get excited, 
 obviously) for crypto purposes!


The paranoiac in me feels that anything that involves getting 
random data via HTTPS is probably insecure crypto-wise :-)  
However, I think sourcing random.org is a perfect case for an 
entry in hap.random.device.  I think the best thing to do would 
probably be to offer a RandomOrgClient (which offers a very thin 
API around the random.org HTTP API) and then to wrap that in a 
range type that uses the client internally to generate random 
numbers with particular properties.


 5. Another possible improvement would be something akin to a 
 "remix" function. It should work identically to reseeding, but 
 instead of setting the internal state to match the seed (as I 
 see in 
 https://github.com/WebDrake/hap/blob/master/source/hap/rando
/generator.d#L485), 
 remixing should probably be XOR'd into the current state. That 
 way if you have a state based on some real entropy, you can 
 slowly, over time, drip in more entropy into the state.


Also a very interesting suggestion.  Is there a standard name for 
this kind of procedure?


 6. I'd like to see about supporting xorshift1024 as well 
 (described here: http://xorshift.di.unimi.it/ and it's public 
 domain code, so very convenient to port ... I'd do it too, of 
 course, if that seems like an okay idea). This is a really 
 small thing because xorshift1024 isn't really much better than 
 xorshift128 (but some people might like the idea of it having 
 significantly longer period).


Fantastic, I will see about implementing those.  I wasn't 
previously aware of that work, but I _was_ aware that the 
standard Xorshift generators have some statistical flaws, so it's 
great to have some alternatives.  It should be straightforward to 
implement things like XorshiftP128 or XorshiftS1024 and 
XorshiftS4096 (using P and S in place of + and *).

With these in place we might even be able to deprecate the old 
Xorshift generators.

Just for clarity, here's how I see things rolling out for the 
future:

   * First goal is to ensure the existing codebase "plays nice" 
with
     people's programs and that it works OK with dub, rdmd, etc. 
and
     doesn't have any serious architectural or other bugs.  The 
1.0.0
     release will not have any new functionality compared to what 
is
     in place now.

   * Once it seems to be reasonably stable then work can begin on a
     1.x release series that brings in successive pieces of new
     functionality.


 Done :) ... if I get a response, I'll make sure to incorporate 
 everything said.


Great, let me know how that goes. :-)
Jun 10 2014
next sibling parent Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On 6/11/2014 2:41 AM, Joseph Rushton Wakeling wrote:

 5. Another possible improvement would be something akin to a "remix"
 function. It should work identically to reseeding, but instead of
 setting the internal state to match the seed (as I see in
 https://github.com/WebDrake/hap/blob/master/source/hap/random/generator.d#L485),
 remixing should probably be XOR'd into the current state. That way if
 you have a state based on some real entropy, you can slowly, over
 time, drip in more entropy into the state.


 Also a very interesting suggestion.  Is there a standard name for this
 kind of procedure?


NIST's crypto-RNG papers just refer to it as "reseeding", so there might 
not be a standard name for it. FWIW, I've taken to calling it 
"accumulating entropy".
Jun 11 2014
prev sibling next sibling parent "Chris Cain" <zshazz gmail.com> writes:
On Wednesday, 11 June 2014 at 06:41:34 UTC, Joseph Rushton 
Wakeling wrote:

 That would be very cool.  Can you point me at your code 
 examples?


It's written in Nimrod (in a way that someone who learned Nimrod 
the day before would write them, because I learned Nimrod the day 
before and worked on it for something like 17 hours straight to 
produce everything):

https://github.com/Zshazz/Ramrod/blob/master/util.nim

I'd like to make this concept a range in D. Not sure what exactly 
to call it but it's an "adaptor." Honestly, I wouldn't be 
surprised if something like this didn't already exist in D in 
some form, but it didn't seem like Nimrod had anything like it.


 The paranoiac in me feels that anything that involves getting 
 random data via HTTPS is probably insecure crypto-wise :-)


Paranoia is good in this case. I appreciate the caution.


 However, I think sourcing random.org is a perfect case for an 
 entry in hap.random.device.  I think the best thing to do would 
 probably be to offer a RandomOrgClient (which offers a very 
 thin API around the random.org HTTP API) and then to wrap that 
 in a range type that uses the client internally to generate 
 random numbers with particular properties.


This sounds like it would be beautiful. As a note, if we expose 
this via a part of the standard library, we would have to make 
certain that we follow the guidelines outlined on random.org (in 
particular, I'm concerned about having an internal locking 
mechanism to prevent multiple threads from asking for bits at the 
same time because that will cause clients to be banned ... global 
state, impurity, and all the nasty things will likely have to be 
a natural part of such a thing).


 Also a very interesting suggestion.  Is there a standard name 
 for this kind of procedure?


I'm not really aware if there is. I remember hearing about the 
concept when talking with my cryptography professor awhile back 
(it may have even been in a lecture). IIRC, the description used 
was "mixing" in entropy, so my first thought is to call it a 
mix/remix function.


 Just for clarity, here's how I see things rolling out for the 
 future:

   * First goal is to ensure the existing codebase "plays nice" 
 with
     people's programs and that it works OK with dub, rdmd, etc. 
 and
     doesn't have any serious architectural or other bugs.  The 
 1.0.0
     release will not have any new functionality compared to 
 what is
     in place now.

   * Once it seems to be reasonably stable then work can begin 
 on a
     1.x release series that brings in successive pieces of new
     functionality.


I like this procedure. Definitely confidence inspiring.
Jun 11 2014
prev sibling parent reply "Chris Cain" <zshazz gmail.com> writes:
On Wednesday, 11 June 2014 at 06:41:34 UTC, Joseph Rushton 
Wakeling wrote:

 Done :) ... if I get a response, I'll make sure to incorporate 
 everything said.


 Great, let me know how that goes. :-)


Well, the ultimate conclusion of the conversation with the guy is 
that:
1. ISAAC probably isn't cryptographically secure. Despite not 
having found any attacks, it just isn't proof of security. It's 
not been looked at enough to really approve of its usage for that 
purpose (I'm kind of agreeing with this)

2. ISAAC in his opinion probably isn't appropriate for non secure 
uses for much the same reason.

I don't agree with that because everything I've seen for ISAAC 
shows that it has some really good statistical properties. Even 
if it's not cryptographically secure, it appears to produce 
"better" pseudorandom numbers to me than something like MT19937 
or Well* (and ISAAC is really fast after the initial cost has 
been paid back)

Ultimately, I think ISAAC (and ISAAC-64) _will_ get more scrutiny 
in the future as it's a PRNG used in Rust, for instance. I would 
not suggest it for default purposes, but I think having it as a 
non-crypto RNG in D wouldn't be a bad idea for those who want to 
choose to use it.

3. Better ideas for crypto PRNGs are AES-CTR or Salsa20.

I agree with this approach for the crypto section of std.random. 
I'd also suggest Blum Blum Shub as another thing to add. It's 
awfully slow, but it's probably one of the few PRNGs that is 
"provably strong" (that is, it's been reduced to a known hard 
problem).

Also, he suggested me to refer to a presentation he made last 
year: http://aumasson.jp/data/talks/randomness_hackepfl13.pdf

I've gone through it and it looks like excellent reference 
material. Note slide 76 saying: "Don't use RaaS (things like 
random.org) -> random bits may be shared or reused". Also, it has 
suggestions for entropy on Windows (CryptGenRandom) which is 
something that will be necessary as well.

Overall, very enlightening.
Jun 12 2014
next sibling parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Thursday, 12 June 2014 at 08:49:45 UTC, Chris Cain wrote:

 Well, the ultimate conclusion of the conversation with the guy 
 is that:
 1. ISAAC probably isn't cryptographically secure. Despite not 
 having found any attacks, it just isn't proof of security. It's 
 not been looked at enough to really approve of its usage for 
 that purpose (I'm kind of agreeing with this)

 2. ISAAC in his opinion probably isn't appropriate for non 
 secure uses for much the same reason.

 I don't agree with that because everything I've seen for ISAAC 
 shows that it has some really good statistical properties. Even 
 if it's not cryptographically secure, it appears to produce 
 "better" pseudorandom numbers to me than something like MT19937 
 or Well* (and ISAAC is really fast after the initial cost has 
 been paid back)


This comes back to another necessary project -- there needs to be 
a decent suite of tests of randomness for D.  I think in this 
case it's probably best to try and wrap TestU01 etc.

In the circumstances, it sounds like ISAAC would be better placed 
in hap.random.generator than hap.random.crypto, though.


 Ultimately, I think ISAAC (and ISAAC-64) _will_ get more 
 scrutiny in the future as it's a PRNG used in Rust, for 
 instance. I would not suggest it for default purposes, but I 
 think having it as a non-crypto RNG in D wouldn't be a bad idea 
 for those who want to choose to use it.


Yea, this would be great.


 3. Better ideas for crypto PRNGs are AES-CTR or Salsa20.

 I agree with this approach for the crypto section of 
 std.random. I'd also suggest Blum Blum Shub as another thing to 
 add. It's awfully slow, but it's probably one of the few PRNGs 
 that is "provably strong" (that is, it's been reduced to a 
 known hard problem).


Sounds good.


 Also, he suggested me to refer to a presentation he made last 
 year: http://aumasson.jp/data/talks/randomness_hackepfl13.pdf


I'll give this a glance when I get home -- one thing I should 
probably do is collate a reference list for future hap.random 
development.


 I've gone through it and it looks like excellent reference 
 material. Note slide 76 saying: "Don't use RaaS (things like 
 random.org) -> random bits may be shared or reused". Also, it 
 has suggestions for entropy on Windows (CryptGenRandom) which 
 is something that will be necessary as well.


Sounds excellent.  I agree entirely about random.org, although I 
still think we should provide access to it via hap.random.device 
-- we should just surround it with necessary caveats.


 Overall, very enlightening.


Thanks for the research! :-)
Jun 12 2014
prev sibling parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On 6/12/2014 4:49 AM, Chris Cain wrote:

 Also, it has suggestions for entropy on
 Windows (CryptGenRandom) which is something that will be necessary as well.


It should be RtlGenRandom: It's used by CryptGenRandom, it 
loads/requires/involves far less unnecessary cruft, and it's 
well-established as *not* being something MS even *could* change/remove 
even if they wanted to (due to some of they ways MS themselves already 
rely on it):

http://blogs.msdn.com/b/michael_howard/archive/2005/01/14/353379.aspx

But this updated system entropy generator you suggest already exists:

https://github.com/D-Programming-Language/phobos/pull/2208/files#diff-713ce153554afc99a07767cc8ba940aeR1189
https://github.com/D-Programming-Language/phobos/pull/2208/files#diff-713ce153554afc99a07767cc8ba940aeR1106

It's also ready-to-use as part of DAuth (which I admit might need a new 
name to avoid confusion with the totally unrelated OAuth):

https://github.com/Abscissa/DAuth/blob/master/src/dauth/hashdrbg.d#L51
https://github.com/Abscissa/DAuth/blob/master/src/dauth/hashdrbg.d#L201

Naturally, it doesn't yet exist in hap.random because, as Joseph said, 
hap.random's "step one" is to match the current std.random as closely as 
possible. I'd be happy to put together a PR to adapt my RNG stuff above 
to hap.random whenever it would be desired.
Jun 12 2014
parent "Chris Cain" <zshazz gmail.com> writes:
On Thursday, 12 June 2014 at 17:35:39 UTC, Nick Sabalausky wrote:

 Naturally, it doesn't yet exist in hap.random because, as 
 Joseph said, hap.random's "step one" is to match the current 
 std.random as closely as possible. I'd be happy to put together 
 a PR to adapt my RNG stuff above to hap.random whenever it 
 would be desired.


Wow! Looks great :)

Thanks for all the work on that.
Jun 12 2014
prev sibling next sibling parent Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On 6/10/2014 7:08 PM, Chris Cain wrote:

 3. I'd also REALLY like to see seed support ranges/values giving ANY
 type of integer and guarantee that few bytes are wasted (so, if it
 supplies 64-bit ints and the generator's internal state array only
 accepts 32-bit ints, it should spread the 64-bit int across two cells in
 the array). I have working code in another language that does this, and
 I wouldn't mind porting it to D for the standard library. I think this
 would greatly simplify the seeding process in user code (since they
 wouldn't have to care what the internal representation of the Random
 state is, then).


Joseph and I have recently had some discussion on the idea of random 
streams which could work as you describe (The full discussion was in the 
digitalmars.D thread titled "isUniformRNG"). A finalized design would be 
dependent on Phobos's redesign of streams. But an unofficial design does 
exist, as it was needed for a crypto RNG I wrote[1][2]. An "RNG -> RNG 
stream" adapter could easily be written.

[1] Original version:
https://github.com/Abscissa/DAuth/blob/master/src/dauth/hashdrbg.d

[2] Phobos submission:
https://github.com/D-Programming-Language/phobos/pull/2208


 4. I'd just like to say the idea of using ranges for seeds gets me giddy
 because I could totally see a range that queries https://random.org for
 true random bits to seed with, wrapped by a range that zeroes out the
 memory on popFront. Convenient and safe (possibly? Needs review before I
 get excited, obviously) for crypto purposes!


Personally, I wouldn't trust an internet-hosted RNG for crypto purposes 
as there's too many ways it could go wrong on either end. However, 
*mixing* it in as an additional source of entropy (together with a local 
source of non-determinism and a proper crypto-grade PRNG such as 
Hash_DRBG) sounds promising to me. Although I'm not a cryptography expert.


 5. Another possible improvement would be something akin to a "remix"
 function. It should work identically to reseeding, but instead of
 setting the internal state to match the seed (as I see in
 https://github.com/WebDrake/hap/blob/master/source/hap/random/generator.d#L485),
 remixing should probably be XOR'd into the current state. That way if
 you have a state based on some real entropy, you can slowly, over time,
 drip in more entropy into the state.


Interesting that you mention that. Hash_DRBG does pretty much that 
(although it's a little more complicated than an simple XOR). While I'm 
not particularly familiar with any others, I'd imagine that's probably a 
typical behavior among cryptographic PRNGs in general.
Jun 10 2014
prev sibling parent reply "Kagamin" <spam here.lot> writes:
On Tuesday, 10 June 2014 at 23:08:33 UTC, Chris Cain wrote:

 4. I'd just like to say the idea of using ranges for seeds gets 
 me giddy because I could totally see a range that queries 
 https://random.org for true random bits to seed with, wrapped 
 by a range that zeroes out the memory on popFront. Convenient 
 and safe (possibly? Needs review before I get excited, 
 obviously) for crypto purposes!


In some scenarios impredictability is not enough. For example, 
when you generate a session id, an attacker doesn't have to 
predict it ahead of time, he can guess it at any time later. And 
if they listen to radio waves - that's an "open protocol", an 
attacker can setup antenna near their antenna and get the same 
readings. Cryptographic PRNG and quantum TRNG are better 
isolated, so it's harder to read them.
Jun 11 2014
next sibling parent Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On 6/11/2014 12:35 PM, Kagamin wrote:

 In some scenarios impredictability is not enough. For example, when you
 generate a session id, an attacker doesn't have to predict it ahead of
 time, he can guess it at any time later. And if they listen to radio
 waves - that's an "open protocol", an attacker can setup antenna near
 their antenna and get the same readings.


An interesting point.


 Cryptographic PRNG and quantum
 TRNG are better isolated, so it's harder to read them.


FWIW, a cryptographic PRNG isn't necessarily well-isolated. Being a 
PRNG, the isolation of a cryptographic PRNG is primarily limited to two 
main things:

- The isolation of its entropy source(s) (which are not normally part of 
a crypto-PRNG's specification - it's just left as "choose a good one"), and

- The patterns of how data is drawn from the PRNG.

If the entropy source is poorly isolated (via poor choice of entropy 
source, or a failure within the entropy source), and the requests being 
made to the PRNG are relatively predictable or even guessable (quite 
likely given the nature of software), then a cryptographic PRNG won't be 
any better isolated than, say, the digits of PI.

TL;DR: The isolation of a cryptographic PRNG is that of its external 
entropy source, not the cryptographic PRNG algorithm itself.
Jun 11 2014
prev sibling parent "Chris Cain" <zshazz gmail.com> writes:
On Wednesday, 11 June 2014 at 16:35:31 UTC, Kagamin wrote:

 In some scenarios impredictability is not enough. For example, 
 when you generate a session id, an attacker doesn't have to 
 predict it ahead of time, he can guess it at any time later. 
 And if they listen to radio waves - that's an "open protocol", 
 an attacker can setup antenna near their antenna and get the 
 same readings. Cryptographic PRNG and quantum TRNG are better 
 isolated, so it's harder to read them.


That's an interesting thought on a potential attack. I wouldn't 
say "same readings" but similar readings is possible and might 
make attacks easier.

It might not be a bad idea as part of a solution though, since it 
can be used to supplement other sources of local-machine 
crypto-grade entropy (since often such sources are exhaustible). 
But yes, just straight up using it alone appears to have a few 
critical problems.
Jun 12 2014
prev sibling next sibling parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Monday, 9 June 2014 at 18:09:21 UTC, Joseph Rushton Wakeling 
wrote:

 Hello all,


Incidentally, would it be a good idea to post a link to the blog 
post on r/programming?  Haven't done so yet, as generally I 
prefer to leave decisions about D publicity to others, but can do 
so if people would like.
Jun 10 2014
parent reply "Chris Cain" <zshazz gmail.com> writes:
On Wednesday, 11 June 2014 at 06:48:24 UTC, Joseph Rushton 
Wakeling wrote:

 Incidentally, would it be a good idea to post a link to the 
 blog post on r/programming?  Haven't done so yet, as generally 
 I prefer to leave decisions about D publicity to others, but 
 can do so if people would like.


I almost always like all the D posts I see on r/programming, but 
in general if any language highlighted the efforts in the RNG 
part of the standard library, I would like it. Too many languages 
get it wrong or don't care enough about it. (My most basic litmus 
test is to check a language's shuffle function... Too many fail, 
even if they claim to do the Knuth shuffle, often they make the 
small mistakes that matter)

It definitely gets my vote for publicizing.
Jun 11 2014
parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Wednesday, 11 June 2014 at 07:24:11 UTC, Chris Cain wrote:

 I almost always like all the D posts I see on r/programming, 
 but in general if any language highlighted the efforts in the 
 RNG part of the standard library, I would like it. Too many 
 languages get it wrong or don't care enough about it. (My most 
 basic litmus test is to check a language's shuffle function... 
 Too many fail, even if they claim to do the Knuth shuffle, 
 often they make the small mistakes that matter)

 It definitely gets my vote for publicizing.


http://www.reddit.com/r/programming/comments/27wohj/haprandom_a_new_random_number_library_for_the_d/

:-)
Jun 11 2014
prev sibling next sibling parent reply "Andrea Fontana" <nospam example.com> writes:
Have you any plan to implement CMWC?

http://en.wikipedia.org/wiki/Multiply-with-carry#Complementary-multiply-with-carry_generators

On Monday, 9 June 2014 at 18:09:21 UTC, Joseph Rushton Wakeling 
wrote:

 Hello all,

 Some of you may remember my earlier draft of a class-based 
 std.random successor:
 http://forum.dlang.org/thread/cyytvhixkqlbwkmiugex forum.dlang.org

 Following revisions made in response to feedback, and some 
 further development, I decided that it would be best to release 
 the results as a dub package with a new library name:
 http://code.dlang.org/packages/hap

 Source code and documentation is available here:
 https://github.com/WebDrake/hap
 http://code.braingam.es/hap/random/

 I've also written a blog post describing new features and the 
 motivations behind this library:
 http://braingam.es/2014/06/hap-random-a-new-random-number-library-for-d/

 I think that hap.random fixes certain fundamental design issues 
 with std.random.  However, this needs to be put to the test "in 
 the wild", so I'd really appreciate it if as many people as 
 possible could try it out with their code, and report on the 
 experience:

    * Does it run faster, slower, etc?

    * Do any undesirable memory allocation issues arise?

    * Is the API (broadly similar but not identical to 
 std.random)
      pleasant to use?

 If it proves to be effective for everyone, then I will begin 
 the process of submission as a new Phobos module.

 Thanks in advance for all testing and feedback.

 Best wishes,

     -- Joe
Jun 11 2014
parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Wednesday, 11 June 2014 at 07:42:10 UTC, Andrea Fontana wrote:

 Have you any plan to implement CMWC?

 http://en.wikipedia.org/wiki/Multiply-with-carry#Complementary-multiply-with-carry_generators


I hadn't made any concrete plans about that particular family of 
generators (my impression was that Xorshift and its successors 
are superior), but I'll happily take patches or a feature request 
:-)
Jun 11 2014
prev sibling next sibling parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Monday, 9 June 2014 at 18:09:21 UTC, Joseph Rushton Wakeling 
wrote:

 I think that hap.random fixes certain fundamental design issues 
 with std.random.  However, this needs to be put to the test "in 
 the wild", so I'd really appreciate it if as many people as 
 possible could try it out with their code, and report on the 
 experience:


A few things I'd really like to hear back on, if anyone can give 
them a go:

   * try using hap.random via rdmd -- does it work?

   * try making a dub package dependent on hap.random --
     does it work?

   * try importing only some, not all, of the hap.random
     modules (e.g. import hap.random.generator) -- does
     this still work?

   * how does it work for people on non-Linux OS's?

Thanks!

     -- Joe
Jun 12 2014
parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Thursday, 12 June 2014 at 21:51:28 UTC, Joseph Rushton
Wakeling wrote:

 A few things I'd really like to hear back on, if anyone can 
 give them a go:


... obviously I have tested the above myself, but "Works for me"
is not a valid quality control strategy ;-)

The other thing I'd really like to know about is how the
effectiveness of stuff like sample and cover is affected by the
transition to classes.  For RNGs I doubt it will be much, because
one tends to allocate and initialize the RNG quite high-up in the
application and then pass it to the internals.

By contrast something like sample() might well be called
extensively in various inner loops of the program, and the fact
that each call involves a class being allocated could be
problematic in terms of triggering the GC.
Jun 12 2014
prev sibling parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Monday, 9 June 2014 at 18:09:21 UTC, Joseph Rushton Wakeling 
wrote:

 I think that hap.random fixes certain fundamental design issues 
 with std.random.  However, this needs to be put to the test "in 
 the wild", so I'd really appreciate it if as many people as 
 possible could try it out with their code, and report on the 
 experience:

    * Does it run faster, slower, etc?

    * Do any undesirable memory allocation issues arise?

    * Is the API (broadly similar but not identical to 
 std.random)
      pleasant to use?


I realized that it ought to be possible to allow a more direct 
drop-in replacement for std.random by adding static opCalls to 
the classes which were previously structs.

Thoughts on this, in favour, against ... ?
Jun 19 2014
next sibling parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On 6/19/2014 5:27 PM, Joseph Rushton Wakeling wrote:

 I realized that it ought to be possible to allow a more direct drop-in
 replacement for std.random by adding static opCalls to the classes which
 were previously structs.

 Thoughts on this, in favour, against ... ?


I'm on the fence:

Pro: Upgrade paths and backwards compatibility are great, especially for 
Phobos.

Con: If any semantics are changed (default ref/value passing is the only 
one that comes to mind), then maybe it would mask potential upgrade 
issues. Breakage would force users to notice the change and (hopefully) 
deal with it appropriately.

I don't personally see it as a big deal either way, though.
Jun 20 2014
parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Friday, 20 June 2014 at 18:15:49 UTC, Nick Sabalausky wrote:

 I'm on the fence:

 Pro: Upgrade paths and backwards compatibility are great, 
 especially for Phobos.

 Con: If any semantics are changed (default ref/value passing is 
 the only one that comes to mind), then maybe it would mask 
 potential upgrade issues. Breakage would force users to notice 
 the change and (hopefully) deal with it appropriately.

 I don't personally see it as a big deal either way, though.


Sorry for taking so long to follow up on this, it's been a busy 
period ...

Anyway, here's my thinking behind the opCall idea.  One of the 
major shifts of the move to classes is that, suddenly, all of 
these entities have to be explicitly allocated.  That means that 
there's some measure of responsibility on the library to offer a 
sane default style of allocation, as appropriate for the expected 
use-cases and performance requirements.

Now, apart from the random number generators, all of the 
remaining library functionality already has helper functions 
which can handle this.  Currently they just "new" stuff, but 
there's no reason this can't be adapted as needed, possibly with 
the option for some kind of templating around different 
allocation strategies.

However, RNGs themselves don't have any corresponding helper 
functions, and manually writing them out would fast become 
annoying (imagine having to create, say, xorshift, xorshift32, 
xorshift64, ... etc. as helper functions to create Xorshift, 
Xorshift32, Xorshift64, etc., instances).

opCall provides a natural way of implementing such construction 
helper functions that is likely very general purpose, and 
encouraging it as the default use-case has a further benefit of 
encouraging the user to always seed their RNGs, if opCall has a 
form like this:

     static typeof(this) opCall(Seed)(Seed seed)
     {
         return new typeof(this)(seed);
     }

It _could_ be done as a temporary measure, deprecated from the 
start, to allow drop-in replacement but encourage appropriate 
adaptation.  But it could also be a way to serve the user with 
sensible default allocation strategies that minimize the 
potential performance impacts of the switch to classes.
Jul 13 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 Anyway, here's my thinking behind the opCall idea.  One of the 
 major shifts of the move to classes is that, suddenly, all of 
 these entities have to be explicitly allocated.


So creating a random number generator can't be  nogc?

Bye,
bearophile
Jul 13 2014
next sibling parent reply "Dicebot" <public dicebot.lv> writes:
On Sunday, 13 July 2014 at 15:31:51 UTC, bearophile wrote:

 Joseph Rushton Wakeling:


 Anyway, here's my thinking behind the opCall idea.  One of the 
 major shifts of the move to classes is that, suddenly, all of 
 these entities have to be explicitly allocated.


 So creating a random number generator can't be  nogc?

 Bye,
 bearophile


std.typecons.scoped _should_ still work - I actually suggest 
adding unit tests for this as it is quite an important use case.
Jul 13 2014
next sibling parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Sunday, 13 July 2014 at 15:34:31 UTC, Dicebot wrote:

 std.typecons.scoped _should_ still work - I actually suggest 
 adding unit tests for this as it is quite an important use case.


std.typecons.scoped works per se (I'm adding unittests as we 
speak) but using my current dmd, this:

     // confirm scoped allocation is  nogc
     void scopedRNG(T)(T seed)  nogc
     {
         auto gen = scoped!UniformRNG(seed);
     }

     scopedRNG(unpredictableSeed);

... fails to compile with the error,

     Error:  nogc function 
'hap.random.generator.__unittestL91_27.scopedRNG!uint.scopedRNG' 
cannot call non- nogc function 
'std.typecons.scoped!(LinearCongruentialEngine!(uint, 16807u, 0u, 
2147483647u)).scoped!(uint).scoped'

... even if the constructor of the RNG in question is marked 
 nogc together with all that it calls.

Is this possibly an issue with 'scoped'?  Was it only quite 
recently patched to support  nogc?  I'll update my installed 
compiler if so.
Jul 13 2014
parent reply "Dicebot" <public dicebot.lv> writes:
On Sunday, 13 July 2014 at 16:01:11 UTC, Joseph Rushton Wakeling 
wrote:

 Is this possibly an issue with 'scoped'?  Was it only quite 
 recently patched to support  nogc?  I'll update my installed 
 compiler if so.


Quite likely it has not been updated to  nogc at all - which 
makes scoped kind of joke if it is true :)
Jul 13 2014
parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Sunday, 13 July 2014 at 16:12:16 UTC, Dicebot wrote:

 Quite likely it has not been updated to  nogc at all - which 
 makes scoped kind of joke if it is true :)


Seems to be the case, looking at current scoped() code in Phobos 
(I just updated my dmd/druntime/phobos install:-)

BTW I note that inside the static struct Scoped you have a 
private Scoped_store together with a public alias_this.  This 
would normally clash with 
https://issues.dlang.org/show_bug.cgi?id=10996 -- I'm guessing 
the reason it doesn't in this case is because it's all wrapped up 
in the scoped() template, so that the Scoped struct is actually 
created in the same module (the same scope even!) as all the 
places it will actually be used?
Jul 13 2014
parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Sunday, 13 July 2014 at 16:20:12 UTC, Joseph Rushton Wakeling 
wrote:

 I'm guessing the reason it doesn't in this case is because it's 
 all wrapped up in the scoped() template


... no, it's because the private Scoped_store is passed out via 
the Scoped_payload property.

Anyway, the actual scoped() method itself is templated, so 
whether it can be  nogc or not obviously depends on its arguments 
and has to be inferred.  The trouble is with the destructor 
~this() which is in no way dependent on template parameters, but 
in calling the destructor of the scoped payload, depends on the 
payload's own destructor for whether it can be  nogc or not.
Jul 13 2014
parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Sunday, 13 July 2014 at 16:29:11 UTC, Joseph Rushton Wakeling 
wrote:

 Anyway, the actual scoped() method itself is templated, so 
 whether it can be  nogc or not obviously depends on its 
 arguments and has to be inferred.


Hmm, I tried patching up what I could of the Scoped struct's 
methods to use  nogc, but to no avail where hap.random is 
concerned :-(
Jul 13 2014
prev sibling parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Sunday, 13 July 2014 at 15:34:31 UTC, Dicebot wrote:

 std.typecons.scoped _should_ still work - I actually suggest 
 adding unit tests for this as it is quite an important use case.


Unittest at least for scoped _without_  nogc:
https://github.com/WebDrake/hap/commit/ac820f27f635e0a88790f6c344de5d40752704da

Hey, I have 1111111 commits! :-D
Jul 13 2014
prev sibling parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Sunday, 13 July 2014 at 15:31:51 UTC, bearophile wrote:

 So creating a random number generator can't be  nogc?


I think even as things are there is nothing stopping the user 
from manually allocating and using "emplace" to create an RNG 
instance without relying on the GC.  However, even if not, I 
think this would be less of a problem, as in general things like 
RNG instances can be expected to be allocated "high up" in the 
program and passed down into the inner parts where  nogc becomes 
a concern.

What really matters to me is stuff like Sample and Cover, where 
we can readily expect that they may be called in inner loops of 
the program, and so having lots of allocations via "new" would be 
a big problem.  So, it follows that the current helper functions 
(sample, cover, etc.) need to be rewritten at some point with 
this in mind.

It's not a problem I propose to solve for the 1.0.0 release, but 
it is a problem that needs addressing in the long run.

Out of curiosity, do you have any ideas or suggestions for how to 
address the requirement for RNGs and related functionality to be 
reference types, together with the wish to support  nogc ... ?  
Preferably in a way that avoids the user having to explicitly 
indicate destruction?
Jul 13 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 What really matters to me is stuff like Sample and Cover, where 
 we can readily expect that they may be called in inner loops of 
 the program, and so having lots of allocations via "new" would 
 be a big problem.  So, it follows that the current helper 
 functions (sample, cover, etc.) need to be rewritten at some 
 point with this in mind.


I think  nogc is a good improvement for D, despite Walter and 
other people (and I think Don) were very sceptical about it, 
because it's like a new lens that allows me to see important 
things about my code that I wasn't able to see before. Phobos has 
to be modified in many places to allow both usage patterns for 
people that want to write short clean code (that allocates 
automatically and lets the GC free), and performance-conscious 
people that need to avoid most or all heap allocations. What's 
unfortunate is that the  nogc attribute was not present for lot 
of time of development of Phobos, so several Phobos things now 
need to be modified and some old APIs could give problems. 
std.random2 should offers ways to be used as much as possible 
from  nogc code, see below.



 It's not a problem I propose to solve for the 1.0.0 release, 
 but it is a problem that needs addressing in the long run.


Even if the 1.0.0 release of std.random2 is not much  nogc, in my 
opinion it needs to have an API designed to allow it to be 
retrofitted cleanly and nicely for  nogc usages too.



 do you have any ideas or suggestions for how to address the 
 requirement for RNGs and related functionality to be reference 
 types, together with the wish to support  nogc ... ?  
 Preferably in a way that avoids the user having to explicitly 
 indicate destruction?


If you are not using the GC, and you don't want to indicate 
destruction, you have to use RAII and perhaps RefCounted. You can 
allocate on the C heap manually, or on the stack, or you can 
allocate on the stack or C heap using one of Andrei's future 
allocators.

Bye,
bearophile
Jul 13 2014
parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Sunday, 13 July 2014 at 16:24:29 UTC, bearophile wrote:

 Even if the 1.0.0 release of std.random2 is not much  nogc, in 
 my opinion it needs to have an API designed to allow it to be 
 retrofitted cleanly and nicely for  nogc usages too.


Completely agree.  Incidentally the library is intended for use 
with dmd 2.065+ which precludes unqualified use of  nogc for now, 
but that will be addressed after 2.066 is released and ldc/gdc 
upgrade their frontend/Phobos dependencies.


 If you are not using the GC, and you don't want to indicate 
 destruction, you have to use RAII and perhaps RefCounted. You 
 can allocate on the C heap manually, or on the stack, or you 
 can allocate on the stack or C heap using one of Andrei's 
 future allocators.


Stack allocation is arguably appropriate for stuff like Sample, 
however, the created entity needs to be able to escape the scope 
of the helper function which allocates it.
Jul 13 2014
prev sibling parent "Chris Cain" <zshazz gmail.com> writes:
On Thursday, 19 June 2014 at 21:27:17 UTC, Joseph Rushton 
Wakeling wrote:

 I realized that it ought to be possible to allow a more direct 
 drop-in replacement for std.random by adding static opCalls to 
 the classes which were previously structs.

 Thoughts on this, in favour, against ... ?


I'd say do it and make it  deprecated ... in general, I think 
allowing a "struct like constructor" for a class is bad style (at 
least for std, anyway) and should be discouraged, but deprecating 
it makes it an easy upgrade initially and will make it easier for 
people to compare the old vs new way with their code.
Jun 22 2014