StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Some things to consider:</p> <ul> <li>Use the <a href="http://hackage.haskell.org/package/mersenne-random-pure64" rel="noreferrer">mersenne-random</a> generator, it is often >100x faster than StdGen</li> </ul> <p>For raw all-out performance, write a custom State monad, like so:</p> <pre><code>import System.Random.Mersenne.Pure64 data R a = R !a {-# UNPACK #-}!PureMT -- | The RMonad is just a specific instance of the State monad where the -- state is just the PureMT PRNG state. -- -- * Specialized to a known state type -- newtype RMonad a = S { runState :: PureMT -> R a } instance Monad RMonad where {-# INLINE return #-} return a = S $ \s -> R a s {-# INLINE (>>=) #-} m >>= k = S $ \s -> case runState m s of R a s' -> runState (k a) s' {-# INLINE (>>) #-} m >> k = S $ \s -> case runState m s of R _ s' -> runState k s' -- | Run function for the Rmonad. runRmonad :: RMonad a -> PureMT -> R a runRmonad (S m) s = m s evalRmonad :: RMonad a -> PureMT -> a evalRmonad r s = case runRmonad r s of R x _ -> x -- An example of random iteration step: one-dimensional random walk. randStep :: (Num a) => a -> RMonad a randStep x = S $ \s -> case randomInt s of (n, s') | n < 0 -> R (x+1) s' | otherwise -> R (x-1) s' </code></pre> <p>Like so: <a href="http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27414#a27414" rel="noreferrer">http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27414#a27414</a></p> <p>Which runs in constant space (modulo the <code>[Double]</code> you build up), and is some 8x faster than your original.</p> <p>The use of a specialized state monad with local defintion outperforms the Control.Monad.Strict significantly as well.</p> <p>Here's what the heap looks like, with the same paramters as you:</p> <p><img src="https://i.imgur.com/LtqwW.png" alt="alt text" title="Custom state monad"></p> <p>Note that it is about 10x faster, and uses 1/5th the space. The big red thing is your list of doubles being allocated.</p> <hr> <p>Inspired by your question, I captured the PureMT pattern in a new package: <a href="http://hackage.haskell.org/package/monad-mersenne-random-0.1" rel="noreferrer">monad-mersenne-random</a>, and now your program becomes this:</p> <ul> <li><a href="http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27423" rel="noreferrer">Using monad-mersenne-random</a></li> </ul> <p>The other change I made was to worker/wrapper transform iterateM, enabling it to be inlined:</p> <pre><code> {-# INLINE iterateM #-} iterateM n f x = go n x where go 0 !x = return x go n !x = f x >>= go (n-1) </code></pre> <p>Overall, this brings your code from, with K=500, N=30k</p> <ul> <li>Original: 62.0s</li> <li>New: 0.28s</li> </ul> <p>So that is, <strong>220x faster</strong>.</p> <p>The heap is a bit better too, now that iterateM unboxes. <img src="https://i.imgur.com/ZRrP1.png" alt="alt text"></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload