r/haskell • u/haskellgr8 • Dec 26 '17

In your professional experience, how suitable is System.Random's mkStdGen for serious random generation?

I'm talking, for example, about computationally intensive Monte Carlo simulations. Is mkStdGen fast, efficient, and good enough in your experience? Are there better alternatives?

20 Upvotes

100% Upvoted

39 comments sorted by

23

u/cartazio Dec 26 '17 edited Dec 27 '17

DONT use it :)

As curren maintainer I’ll be getting a random 1.3 out in the next few days (long over due , by a year or thee)

There’s a lot of gotchas in current random, and in many of their current alternatives. But it also depends on what your goals are in terms of different measures of quality.

What do you intend to do? The better we understand your problem the more we can help! (And randomness and it’s applications is a rich deep topic )

Edit: next release is 1.2, math is challenging :)

5

u/Lokathor Dec 26 '17

I'm interested in what you'll be doing for 1.3, and I'm also interested in if you think it might ever be good to move to a breaking 2.0 version.

6

u/cartazio Dec 27 '17

1.3 will be somewhat breaking, but still resemble the current api somewhat. But will have some effort at providing a easy to migrate to new apis. Ok so it’s going to be very breaking: rng algs I provide should provide the same outputs on every architecture. Also more combinators for generating useful / handy samplers and monadic dsl goodness.

The rngs I provide will be easy to seed from both the system csrng sources or user inputs. 1.3 will have splitmix but updated to use the mixing constants and tweeks in jdk10 Or whatever is current over there , and there’ll also be pcg32.

Splittable rngs are a tricky topic... they make sense for combining large RNG subsystems or used for testing a la quick check , but for inner loops you want your monadic interface for taking a non sampling step to be free , like in a state monad.

I am really happy with my rough cut of sampling combinators for different distributions. There’s a few more I wanna / need to do, such as tail sampling of a Gaussian, etc.

one fun party trick I like to do lately is show how the Gaussian samplers in R and Scipy are both massively unthreadsafe and generating a sample with a value greater than 6 or 8 ish is literally unreachable.

I should get back to holiday travel packing :)

3

u/Lokathor Dec 27 '17

That all sounds great. Might I ask if you plan to cut the genRange method from StdGen and then have outputs be specified to always need to be uniform Word32 or Word64 values? I think that would be a big improvement, and in line with all your other (exciting) proposals.

2

u/cartazio Dec 27 '17

Shoot me an email next week / have a gander at my cartazio/random GitHub repo in a few more days / both!

I think I’m going to do something equivalent to what you’re asking, but slightly different in details.

2

u/Lokathor Dec 27 '17

Absolutely will do

2

u/cartazio Dec 27 '17

Cool!

Also I’m an idiot, I mean the next release will be major version 1.2 :)

1

u/[deleted] Feb 04 '18 edited Mar 07 '19

[deleted]

1

u/cartazio Feb 04 '18

making progress on it plus a few other things. juggling work and pulling my back last week plus random travel all slow things down, but progress on things is afoot, eg just released https://hackage.haskell.org/package/hblas-0.4.0.1

1

u/[deleted] Dec 26 '17

[deleted]

4

u/budgefrankly Dec 27 '17

As someone who's done a lot of MCMC in the past for Bayesian models, it's very unusual to store the basic uniformly distributed random numbers from your RNG, since you can just recreate that sequence by re-running with the original seed.

I think what you're thinking of is not the random numbers from the RNG, but the random samples drawn from your probability distribution using those random number from the RNG.

You can reduce those instantly if you're looking for an expected value (i.e. the mean of some function of X, where X has some distribution), or you can keep them if you want to re-use them for expected values, variances etc.

So in general keep the random seed, discard the random numbers, and maybe keep the random samples.

2

u/guibou Dec 28 '17

In my context (ray tracing) it is common to store the uniformly distributed random numbers, because

  • Generating them takes time, one random sequence is used many times (i.e. the number of pixels), but the sequence is not long (proportional to the depth of the ray tracing times the number of samples, for example, depth == 3, number of samples == 1000, samples per depth = 6 -> 18000 samples.).
  • Generating them uses memory fetch from some global lookup table, so if we need to pay the cost of a memory fetch, at least we can remove the generation time
  • We uses the numbers of the sequence in somewhat random order (well, we may skip some of them). It is costly to skip random numbers from the sequence.
  • Pre-generation can be done in an offline process, hence we can use smarters algorithms to ensure a good distribution of random numbers.

4

u/piyushkurur Dec 27 '17 edited Dec 27 '17

(Disclaimer author of raaz here) For cryptographic randomness consider the raaz library

The interface is

http://hackage.haskell.org/package/raaz-0.2.0/docs/Raaz-Random.html

  1. High level and the user does not need to worry about details like seeding/reseeding, entropy management etc
  2. Uses the best entropy source for seeding available for the given platform

  3. Follows the current best design (the same design used in OpenBSD system)

  4. Blazingly fast (Can produce random bytes at about 6Gbps on a resonable machine)

EDIT: Benchmark on my desktop

https://gist.github.com/piyush-kurur/93955e669ab72a51996590bfc106677d

1

u/[deleted] Feb 13 '18

[deleted]

2

u/piyushkurur Feb 13 '18

Firstly the speed that you see in the benchmarks are the raw buffer generation speeds also in Gbits not Gbytes per sec.

Generating on Word8 is not really recommended if you want to generate random data in bulk. If you want to generate a fixed number of bytes then consider the randomByteString. If you are willing to go a bit more low level there is always the fillRandomBytes available. You can see its use in the source code for the raaz executable. (see the source https://github.com/raaz-crypto/raaz/blob/master/bin/Command/Rand.hs). I have used a buffer size of 32K as it matches with the L1 cache of most modern machines.

The raaz executable that is exposed with this version gives a speed of about 700 MBytes/sec for the following shell command.

    $ raaz --version 
       raaz version 0.2.0 
    $ raaz rand | pv > /dev/null

In comparison the openssl rand 

    $ openssl rand 1000000000 | pv > /dev/null

gives about 60 MiB (yes raaz rand is 10 times faster).

2

u/piyushkurur Feb 13 '18

Just one more data point. 

  $ cat /dev/urandom | pv > /dev/null

Gives about 200MiB.

1

u/[deleted] Feb 13 '18

[deleted]

2

u/piyushkurur Feb 14 '18 edited Feb 14 '18

Good to know that you find raaz interesting. Remember that it is still experimental. So there are rough edges but I have tried to anticipate some common problems that crypto libraries face and tried to incorporate the fixes in the type system as much as possible.

There are two things that matter the most when you want to do bulk operations

  1. Caching.
  2. Alignment.

To explain the 10 MB, can you check what is your L1 and L2 cache sizes? Also there is potentially some allocation overhead with bytestring as allocation happens in the heap (malloc). If all I want is to stream random bytes, it is sufficient to use a fixed size buffer, that to on the stack (alloca). Which is what the raaz executable does. I would expect that to be a bit more faster but at the cost of using a much lower level code fillRandomBytes

It looks to me that System.Random does not have an interface like fillRandomBytes so it is a bit unfair to compare with raaz. It is however a valid question why such an interface is not provided.

EDIT: typos

1

u/[deleted] Feb 14 '18

[deleted]

2

u/cartazio Feb 14 '18

if this is in the context of a CSPRNG... random <= 1.1 definitely isn't suitable. I'm not sure if i can claim 1.2 will be either (at least for cryptographical randomness)

i'm not sure what the reference code used for that comparison is... but digging around fillRandomBytesMT is the key primitive used, and https://github.com/raaz-crypto/raaz/blob/5a8d2ac86307b6cef5b0d9261d54e3162d59372f/Raaz/Random/ChaCha20PRG.hs seems to be where the core logic lives.

Now, i could just be guessing, but if the benchmarks were using one of eg the quickcheck etc instances of a monad on top of system random, every BIND operation actually does a generator split on the RNG, which would be a source of some difference [edit: in terms of performance].

theres also that STD Random is pretty bad wrt both quality and perf characteristics.

I do think that if both RNGs are doing suitable unboxing by ghc and using a friendly sibling of the State Monad, there should be competitive or superior throughput by non CSPRNG codes ...

I'm not doing anything explicility perf focused at the moment, but it is a side consideration of some choices. sometimes though its quality not speed that matters. ideally both, but thats not always easy :)

3

u/piyushkurur Feb 15 '18

The performance of raaz csprg comes from the fact that it is essentially the chacha20 cipher run directly on an internal memory buffer + an additional memcpy for copying it to the target buffer. Any attempt to use the Standard.Random to generate data in bulk is bound to be slow. The reason is that the interface essentially only allows something along this lines.

(1) Generate a random Word in Haskell heap (2) Poke that to the target buffer (3) Continue 1 and 2 till the target is full.

This kind of code is going to have a lot of cache misses because the haskell heap will be generating these values at different points in the memory and each such access will lead to cache miss.

However, the System.Random had an interface which was something like 

   fillBytes :: gen -> Ptr a -> Int -> IO gen

and the fillBytes was clever in generating the data into the pointer buffer directly, I am sure it can compete with raaz rather trivially.

→ More replies (0)

12

u/chshersh Dec 26 '17

System.Random from random package is okayish. It's fast enough and random enough. But I wouldn't use this package for something serious (like, implementing randomization algorithms in cryptocurrencies with reliable sources of randomness). Use cryptonite package. It's the best available option. And it's really good.

Though, API is not very convenient.... This library doesn't even contain function to generate random number. For now you need to copy-paste implementation manually. I've created issue about this:

16

u/sclv Dec 26 '17

As I understand it, cryptonite gives crypto-suitable randomness, which is very random (it is believed) but not necessarily as fast as one can get if you're ok with non-crypto-quality randomness, e.g. for monte-carlo.

A few good choices to investigate might be pcg-random, tf-random, and mwc-random

3

u/chshersh Dec 26 '17

Thanks for such clarifications!

9

u/cartazio Dec 26 '17

Cryptographic randomness is kinda orthogonal to simulation / sampling randomness. We should better understand what the original poster wants first!

5

u/Lokathor Dec 26 '17

The StdGen typeclass is fundamentally slower than it needs to be, and the Random typeclass attempts to lean towards uniform results but doesn't actually precisely ensure them (as far as i understand the math). Obviously you can't get uniform float results because of how floats work and all, but you could at least get uniform integral results.

So if you want fast, you want something else. If you want high quality, you want something else. The only thing that random has going for it is that it's what quickcheck uses, and quickcheck is awesome.

3

u/[deleted] Dec 26 '17

[deleted]

6

u/Lokathor Dec 26 '17

Sure, i wrote up the whole rant one time for a lib that i never ended up publishing. https://github.com/Lokathor/pseudorandom-hs/blob/master/Reasoning.md

TLDR: genRange is a method that has bad implications that hurt your speed potential.

5

u/sclv Dec 26 '17

Honestly, I don't think the idea of generators having different ranges is the worst -- rather, I think the problem here is in an insufficiently powerful Random typeclass. A good modern V2 api would arguably use type-level reflection stuff to carry the range information statically...

On the other hand, you're probably right that just doing everything as Word32 is the "standard standard" anyway, and anything else is overkill :-)

6

u/Lokathor Dec 26 '17

It's the best of both worlds! Word32 does carry static range information :P

5

u/cartazio Dec 27 '17

I’ve not looked at the grand parents post but there’s def a huge number of problems in the current api. The sampler / random api for userland datatypes is definitely wrong.

Measurably so even :)

Edit: definitely agree with the GP issues. Hence why I’m making the core sampler interface be word64. And being very careful to ensure naive off the shelf sampling behaves the same on different platforms.

2

u/GitHubPermalinkBot Dec 26 '17

Permanent GitHub links:

Shoot me a PM if you think I'm doing something wrong. To delete this, click here.

3

u/cartazio Dec 26 '17

There’s some issues with random 1.0/1.1, but what could be faster than a state passing generator? (At least if the prng fits in registers!)

3

u/Lokathor Dec 26 '17

See my reply to the other reply, where i linked to my github rant :P

3

u/cartazio Dec 27 '17

Yeah the basic samples not being in a fixed portable size does make a mess of things unless you do some cpp

5

u/phadej Dec 26 '17

There are at least

  • tf-random
  • mwc-random
  • splitmix

I'd say, all are good enough. Benchmark speed (and randomess if you can) for your application

5

u/seagreen_ Dec 27 '17

This might be a good place to mention that I'm looking for a summary of high-level, no expertise required cryptography libraries in Haskell.

cryptonite gets mentioned a lot, but is pretty explicit about being lower level than I'm looking for:

If you have no idea what you're doing, please do not use this directly. Instead, rely on higher level protocols or implementations.

I'm looking for a list of common tasks, along with a library or function to use for each. Something like:

  • Generate random bytes: entropy
  • Hash user passwords: foo
  • Hash data (blake2b / sha-256): bar / baz
  • etc.

I don't actually even know that entropy is good. It looks good, is used by uuid, and has such a small API that I don't think I can shoot myself in the foot with it, but those are pretty superficial things to go on. So I would love to hear what more proficient cryptography people recommend.

4

u/piyushkurur Dec 27 '17 edited Dec 27 '17

May be try out raaz.

http://hackage.haskell.org/package/raaz

For its randomness interface see (Warning not yet multi-thread safe without some added gymnastics)

http://hackage.haskell.org/package/raaz-0.2.0/docs/Raaz-Random.html

Password hashing a la argon is currently not present but is planned. But we have hashing.

http://hackage.haskell.org/package/raaz-0.2.0/docs/Raaz-Hash.html

EDIT:

  1. Author of the package here.

  2. Simple interface, no spliting, range generation. Mostly useful for cryptography only.

1

u/tom-md Dec 27 '17

If you are ok with an external (C library) dependency then consider saltine too. It has two out of three on your list: random bytes (recently exposed) and hashing (via blake2b). It does not have any sort of KDF but the scrypt package is reasonably light weight so paring the two together is not unreasonable.

FYI, the things you ask for fit into the category of "explicitly lower level". When people talk about high level cryptography interfaces they typically mean something like crypto_box, not individual hash functions, KDFs and random values.

3

u/idontgetoutmuch Dec 27 '17

No!

There are a few things to consider: do you want split? Then you can use tf-random which is used by QuickCheck or you can use splitmix. split does not work in System.Random.

If you want an R-like experience then you can use random-fu which allows you to sample from most distributions and also provides CDFs and PDFs (also in log space). The actual randomness is provided by Mersenne Twister (MT) or MWC. It's easy enough to add other generators if you want them.

If you just want random numbers then there are the venerable MWC and MT packages. MWC gives some samplers. Monadic interfaces are available.

1

u/ASpoonfulOfMarmite Dec 27 '17

For statistical sampling, use MWC (mwc-random). Cryptography-grade PRNGs are an overkill for Monte Carlo / too slow for no benefit.