[Haskell-cafe] Generate random UArray in constant memory space.

[Daniel Fischer]

Am Dienstag 09 Februar 2010 13:18:23 schrieb Vasyl Pasternak:
> Hello Cafe,
>
> I tried to generate memory-efficient list of random numbers, so I've
> used uvector library for this task. But it doesn't work,
> it still allocates more than 6Gb of memory for the random list of 10
>
> million elements. Here is the code:

Hmm,

$ ghc -O2 --make ranVec
[1 of 1] Compiling Main             ( ranVec.hs, ranVec.o )        
Linking ranVec ...
$ ./ranVec 10000000 +RTS -sstderr
5130
   4,919,912,080 bytes allocated in the heap
         883,256 bytes copied during GC
          26,896 bytes maximum residency (1 sample(s))
          25,620 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

maximum residency is just eight bytes more than for 100,000 or 1,000,000 
numbers. I think that is constant space.

The ~5 GB total allocation is sequential, ten million new StdGens are 
produced and allocated, then immediately garbage collected. I see no 
problem (except that StdGen is slow, e.g. the Mersenne twister is much 
faster [and allocates less, but still linear in size]).

> > import Text.Printf
> > import System.Random
> > import Control.Applicative
> > import System.Environment
> > import Data.Array.Vector
> >
> > randomListU :: (Int, Int) -> StdGen -> Int -> (UArr Int)
> > randomListU b g size = unfoldU size gen g
> >   where gen g = let (x, g') = randomR b g
> >                 in JustS (x :*: g')
> >
> > main = do
> >   [size] <- map read <$> getArgs
> >   let ints = randomListU (-10, 10) (mkStdGen 1) size
> >   printf "%d\n"  (sumU ints)
>
> Could someone give a hint, how to implement this function in constant
> memory space?
>
> Thank you in advance.
>
> Best regards,
> Vasyl Pasternak