[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 mailing list