Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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?
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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 :)
Re: hap.random: a new random number library for D
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
Re: hap.random: a new random number library for D
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?
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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 :-(
Re: hap.random: a new random number library for D
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 111 commits! :-D
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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 ... ?
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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! :-)
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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/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? 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
Re: hap.random: a new random number library for D
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 ... :-)
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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/cyytvhixkqlbwkmiu...@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
Re: hap.random: a new random number library for D
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 :-)
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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/ :-)
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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
Re: hap.random: a new random number library for D
Pass it by reference, I see no reason why MT can't be pure.
Re: hap.random: a new random number library for D
Kagamin: Pass it by reference, I see no reason why MT can't be pure. I meant strongly pure :-) Bye, bearophile
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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
Re: hap.random: a new random number library for D
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).
Re: hap.random: a new random number library for D
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?
Re: hap.random: a new random number library for D
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
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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/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. 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.
Re: hap.random: a new random number library for D
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
hap.random: a new random number library for D
Hello all, Some of you may remember my earlier draft of a class-based std.random successor: http://forum.dlang.org/thread/cyytvhixkqlbwkmiu...@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
Re: hap.random: a new random number library for D
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.
Re: hap.random: a new random number library for D
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! :-)
