[Haskell-cafe] Performance problem with random numbers
Brandon S. Allbery KF8NH
allbery at ece.cmu.edu
Sat Oct 13 12:42:10 EDT 2007
On Oct 13, 2007, at 11:40 , ntupel wrote:
> On Sat, 2007-10-13 at 09:56 -0400, Brandon S. Allbery KF8NH wrote:
>> Now you need to start forcing things; given laziness, things tend to
>> only get forced when in IO, which leads to time being accounted to
>> the routine where the forcing happened. If random / randomR are
>> invoked with large unevaluated thunks, their forcing will generally
>> be attributed to them, not to functions within the thunks.
> But AFAIK random and randomR only take a StdGen (plus a range argument
> in case of randomR) as argument so I don't understand where the
> unevaluated thunks might be actually? (Maybe I should have said that
> random and randomR are the ones from GHC's System.Random module.)
Your apparently simple StdGen argument is actually a sort of program
state (represented by unevaluated thunks, not by a state monad; see
below) which gets altered with every invocation of random. If
nothing is forced until the very end, it in effect becomes an
expression which produces the desired StdGen, with the uses of the
previous StdGen values as "side effects" of its computation that
occur when the thunk is evaluated at the end. I'm not sure I'm up to
working through an example of what this looks like.
Suffice it to say that in a lazy language like Haskell, almost any
"simple" expression can in practice end up being a suspended
computation (a thunk) consisting of whatever is supposed to produce
it. And in the general case (e.g. you don't use strictness
annotations) the only way to force evaluation is to do I/O, so it's
quite normal for a "naive" program to end up being one big thunk
dangling off a PutStrLn. So why does random get tagged for it?
Because it's a state-like function (that is, a function of the form s
-> (a,s); compare to the definition of the State monad) which takes a
StdGen and produces a modified StdGen, so when Haskell finally
evaluates the thunk most of the activity happens in the context of
evaluating that modification.
Hopefully someone reading -cafe can explain it better; I'm pretty
lousy at it, as you can probably tell.
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery at kf8nh.com
system administrator [openafs,heimdal,too many hats] allbery at ece.cmu.edu
electrical and computer engineering, carnegie mellon university KF8NH
More information about the Haskell-Cafe