Bagaimana menjelaskan data profil generator acak Haskell ini untuk penggunaan memori yang besar dan kecepatan rendah?

Saya ingin membuat profil kecepatan generator acak Haskell, dan kasus pengujian saya adalah menghasilkan 10.00000 angka acak presisi ganda berkisar dari nol hingga satu dan menghitung jumlahnya. ini kode saya:

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

dan saya mengkompilasi kodenya dengan

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

dijalankan dengan

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

dan data profil untuk calc1 adalah

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

data profil untuk calc1 adalah

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

Saya dapat memahami bahwa generator acak di System.Randomakan lebih lambat, tetapi mengapa generator tersebut menjadi sangat lambat dan mengapa ia mengalokasikan lebih banyak memori?

Saya menggunakan rekursi ekor dalam kode saya dan dikompilasi dengan opsi -O2 -fforce-recomp, mengapa saya tidak mendapatkan penggunaan memori yang konstan?

apakah ada yang salah dalam kode saya? misalnya, apakah karena evaluasi yang lambat sehingga rekursi ekor tidak dioptimalkan dan banyak memori yang dialokasikan? Jika ya, bagaimana program ini dapat lebih dioptimalkan?


person Alaya    schedule 31.01.2015    source sumber
comment
Penggunaan memori konstan? Dengan Haskell? Saya tidak pernah mendengarnya karena hampir semua hal di Haskell dialokasikan. Saya rasa itu sebagian dari intinya, sebenarnya... juga, menurut saya tidak ada -O3, hanya -O2. Juga, pastikan untuk memiliki -fforce-recomp.   -  person MaiaVictor    schedule 31.01.2015
comment
Ya... Saya mendengar bahwa jika saya mengkompilasi dengan -O2, panggilan ekor akan dioptimalkan, jadi saya rasa saya mungkin mendapatkan penggunaan memori yang konstan...   -  person Alaya    schedule 31.01.2015
comment
Anda dapat dengan aman mengandalkan optimasi panggilan ekor dan fungsinya tidak akan menambah tumpukan. Dengan begitu, jika Anda, misalnya, menulis fungsi yang tidak melakukan apa pun selain menjumlahkan angka, saya kira fungsi tersebut akan mendapatkan penggunaan memori yang konstan. Namun begitu Anda melakukan apa pun di dalamnya yang memerlukan alokasi (yang berarti apa saja di Haskell), Anda harus membayarnya. Itu tebakan saya - menurut saya sangat kecil kemungkinannya Anda bisa mendapatkan program Haskell dengan memori konstan yang sebenarnya, tapi saya mungkin salah.   -  person MaiaVictor    schedule 31.01.2015
comment
Jadikan akumulator Anda ketat.   -  person Daniel Wagner    schedule 31.01.2015
comment
@Viclib Menurut pengalaman saya, sangat umum untuk mengoptimalkan loop sehingga loop akan berjalan dalam ruang yang konstan jika Anda malas. Lihat contoh means di Real World Haskell melalui di sini. Versi rekursif ekor dan akumulasi ketat berjalan dalam ruang konstan.   -  person MasterMastic    schedule 31.01.2015
comment
@Viclib Ruang konstan tidak berarti tidak ada alokasi. Ini hanya berarti bahwa memori dibebaskan secepat dialokasikan.   -  person Carl    schedule 31.01.2015


Jawaban (1)


Seperti yang dikatakan Daniel Wagner di komentar, akumulator negara bagian Anda tidak ketat. Pertama, coba impor Control.Monad.State.Strict. Itu saja mungkin sudah cukup! Jika tidak, Anda juga perlu mengubah myRandGen sedemikian rupa sehingga memaksa generator baru lebih teliti sebelum menggantinya di negara bagian.

person sclv    schedule 22.02.2015