vendredi 30 janvier 2015

How to explain this profilng data of Haskell random generator for huge memory usage and low speed?

I want to profile the speed of Haskell random generator, and my test case is to generate 1000000 double precision random numbers range from zero to one and calculate their sum. here is my code:



import System.Random
import System.Environment
import Control.Monad.State
import Data.Time.Clock
type Seed = Int
intDayTime :: IO Int
intDayTime = getCurrentTime >>= return.(floor.utctDayTime :: UTCTime->Int)
n = 1000000 :: Int
main :: IO ()
main = do
calc <- getArgs >>= return . (read ::(String->Int)).head
seed <- intDayTime
let calcit :: Int->Double
calcit 1 = calc1 n seed
calcit 2 = calc2 n (mkStdGen seed)
calcit _ = error "error calculating"
in print $ calcit calc
calc1 ::Int->Seed->Double
calc1 n initSeed =
let next :: Seed->(Double,Seed) -- my simple random number generator, just for test
myRandGen :: State Seed Double
calc :: Int->Int->Seed->Double->Double
next seed = let x = (1103515245 * seed + 12345) `mod` 1073741824 in (((fromIntegral x)/1073741824),x)
myRandGen = state next
calc _ 0 _ r = r
calc n c s r = calc n (c-1) ns (r + nv)
where (nv,ns) = runState myRandGen s
in calc n n initSeed 0
calc2 ::Int->StdGen->Double
calc2 n initSeed =
let myRandGen :: State StdGen Double
calc :: Int->Int->StdGen->Double->Double
next :: StdGen->(Double,StdGen)
next gen = randomR (0,1) gen
myRandGen = state next
calc _ 0 _ r = r
calc n c s r = calc n (c-1) ns (r + nv)
where (nv,ns) = runState myRandGen s
in calc n n initSeed 0


and I compile the code with



ghc profRandGen.hs -O3 -prof -fprof-auto -rtsopts


run with



./profRandGen.exe 1 +RTS -o # for calc1
./profRandGen.exe 2 +RTS -o # for calc2


and the profiling data for calc1 is



total time = 0.10 secs (105 ticks @ 1000 us, 1 processor)
total alloc = 128,121,344 bytes (excludes profiling overheads)


profiling data for calc1 is



total time = 1.48 secs (1479 ticks @ 1000 us, 1 processor)
total alloc = 2,008,077,560 bytes (excludes profiling overheads)


I can understand that the random generator in System.Randomwould be slower, but why would it be slower so much and why would it allocating much more memory?


I used tail recursion in my code and compiled wit -O3 option, why didn't I get constant memory usage?


is there anything wrong in my code? for example, is it because there being lazy evaluation that tail recursion is not optimized and a lot of memory is allocated? If so,How could this program be further optimized?





Aucun commentaire:

Enregistrer un commentaire