[Haskell-cafe] Re: True Random Numbers
James Andrew Cook
mokus at deepbondi.net
Wed Apr 14 06:37:09 EDT 2010
I have now had a chance to experiment with these a bit, and have come up with some changes that bring random-fu's speed in these tests into line with Control.Monad.Random's when compiled with ghc-6.12.1, although it is still a bit slower when using GHC 6.10.4. This is partially because one of the optimization flags I enabled does not work with ghc-6.10.4 (strict dictionaries - the flag exists on the older ghc but causes it to panic on several of the source files).
Actually, I'm a bit surprised I was able to get comparable performance out of it on either platform, because it's doing a bit more with the StdGen than System.Random's "Random" class in the first place. In the Double case, it's using more entropy (System.Random converts a uniform Int32 to a Double, random-fu expects at least 52 bits of entropy in a Double) and in the Int case it's doing an extra 'mod' and a rejection test to make the results uniform.
In any case, it is still far from perfect (in particular, these exact same tests are still a bit slower for Integer even on ghc-6.12.1), but I believe it is better. If anyone has any further suggestions, either about how to speed things up or about other places to focus effort on improving, please pass them on to me.
BTW, I was able to get vector-algorithms to build on GHC 6.10.4 by commenting out an internal type signature (I don't have the system I did this on in front of me but I seem to recall it was a function called "partitionBy" or similar, towards the bottom of Intro.hs), and after that I had no further trouble building criterion.
On Apr 9, 2010, at 6:51 AM, Gökhan San wrote:
> mokus at deepbondi.net writes:
>> are you using the hackage-released version of random-fu or the darcs
> I was using the hackage version, but since then I switched to the darcs
> version. (Btw, began using it in some of my projects and I'm really
> happy about it.)
>> In the above case, I was using IO in the first bgroup and State StdGen
>> in the second.
> I'm running it on a x86_64 Gentoo Linux box with GHC 6.10.4 and was
> unable to install Criterion (apparently, impossible is happening while
> compiling vector-algorithms) so I used 'time' to come up with some
> Below doesn't include IO tests (randomRIO, etc.), since they turned out
> to be spectacularly slow anyway. Results using ghc -O2.
>> module Main (main) where
>> import Data.Random
>> import Data.List
>> import Control.Monad.State
>> import Control.Monad.Random
>> import System.Random
>> test = p1 `fmap` getStdGen
>> type RType = Double
> /usr/bin/time results for (test, RType):
> (p1, Double) : ~3.3 secs
> (p2, Double) : ~1.7 secs
> (p3, Double) : ~1.0 sec
> (p1, Int) : ~1.9 secs
> (p2, Int) : ~1.0 sec
> (p3, Int) : ~0.5 sec
>> count = 10 ^ 6
>> range = (-10, 10)
>> type P = StdGen -> [RType]
>> p1 = evalState (sample (replicateM count (uncurry uniform range))) :: P
>> p2 = evalRand (replicateM count (getRandomR range)) :: P
>> p3 = take count . evalRand (getRandomRs range) :: P
>> main = test >>= (print . foldl' (+) 0)
> Using 'sum' turned to be rather misleading (took up to a minute to sum
> up 'Double's; this problem was less apparent for p1), so I had to use
> foldl' here to get consistent results between 'Int's and
> 'Double's. '`using` rnf' produced similar results.
> Also, using DevURandom for random-fu produces almost the same results.
> Gökhan San
More information about the Haskell-Cafe