I've found DiffArrays to be way too slow/memory-hogging for real usage. Since you are in IO already (StateT s IO), you'll probably be better off using a mutable array for a data structure.
Some things are still best done in the imperative style. You can be a bit safer by using ST as the bottom monad, however, and returning the result as a pure array. This gives you a single copy per "runST". Alternatively, use IntMap instead of arrays if you want a pure data structure with reasonably efficient update/lookup. -- ryan On Tue, Mar 3, 2009 at 4:44 PM, Tobias Olausson <[email protected]> wrote: > Hello all. > I am currently implementing an emulation of a CPU, in which the CPU's > RAM is part of the internal state > that is passed around in the program using a state monad. However, the > program performs > unexpectingly bad, and some profiling information makes us believe > that the problem is the high > memory usage of the program. > > The program below is similar to our main program used when testing a > sorting algorithm in this CPU: > > module Main where > > import Control.Monad.State.Lazy > import Data.Word > import Data.Array.Diff > import Control.Concurrent (threadDelay) > > data LoopState = LoopState > { intVal :: Integer > , diff :: DiffUArray Word8 Word8 > } > > initState :: LoopState > initState = LoopState 0 (array (0x00,0xFF) [(idx,0)|idx<-[0x00..0xFF]]) > > main :: IO () > main = do > execStateT looper initState >>= putStrLn . show . intVal > > looper :: StateT LoopState IO () > looper = do > st <- get > let res = intVal st + 1 > idx = fromIntegral res > put $ st { intVal = res, diff = (diff st) // [(idx,idx)] } > if res == 13000000 > then return () > else looper > > Of course our program does more than updating a counter ;-) > Compiling and running this program yields the following result: > > [~]:[olaussot] >> ghc --make -O2 -o array ArrayPlay.hs > [~]:[olaussot] >> ./array +RTS -sstderr > ./array +RTS -sstderr > 13000000 > 313,219,740 bytes allocated in the heap > 1,009,986,984 bytes copied during GC > 200,014,828 bytes maximum residency (8 sample(s)) > 4,946,648 bytes maximum slop > 393 MB total memory in use (3 MB lost due to fragmentation) > > Generation 0: 590 collections, 0 parallel, 3.06s, 3.09s elapsed > Generation 1: 8 collections, 0 parallel, 3.56s, 4.21s elapsed > > INIT time 0.00s ( 0.00s elapsed) > MUT time 0.27s ( 0.27s elapsed) > GC time 6.62s ( 7.30s elapsed) > EXIT time 0.00s ( 0.00s elapsed) > Total time 6.89s ( 7.57s elapsed) > > %GC time 96.1% (96.4% elapsed) > > Alloc rate 1,155,958,754 bytes per MUT second > > Productivity 3.9% of total user, 3.6% of total elapsed > > Why does the program spend 96.1% of its total running time collecting garbage? > Any tips to make this program perform better are appreciated. > Please do tell if anything is unclear. > > -- > Tobias Olausson > [email protected] > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
