[Haskell-cafe] Performance problem with random numbers

[ntupel]

On Fri, 2007-10-12 at 20:25 -0700, Stefan O'Rear wrote:
> On Sat, Oct 13, 2007 at 12:09:57AM +0200, ntupel wrote:
> > setup :: (Ord a, IArray a2 a, IArray a1 e, Num a) => [e] -> [a] -> (a1 Int e, a1 Int e, a2 Int a)
> > calcAlias :: (Ord e, Num e, IArray a e, Ix i, IArray a2 e1, IArray a1 e1) => a2 i e1 -> a1 i e1 -> a i e -> [i] -> [i] -> (a1 i e1, a i e)
> > next :: (IArray a2 e1, IArray a e1, Ord e, IArray a1 e, RandomGen t, Random e) => (a Int e1, a2 Int e1, a1 Int e) -> t -> (e1, t)
> > randomList :: (Random e, RandomGen t1, IArray a2 e, Ord e, IArray a t, IArray a1 t) => (a Int t, a1 Int t, a2 Int e) -> t1 -> [t]
> 
...
> I would try specializing to StdGen, UArray, and Int, for RandomGen,
> IArray, and Random respectively.


Thanks for your reply Stefan. Unfortunately I could measure only a
relatively small improvement by changing to concrete types, e.g. using

setup :: [a] -> [Double] -> (Array Int a, Array Int a, UArray Int
Double)

calcAlias :: Array Int a -> Array Int a -> UArray Int Double -> [Int] ->
[Int] -> (Array Int a, UArray Int Double)

next :: (Array Int a, Array Int a, UArray Int Double) -> StdGen -> (a,
StdGen)

randomList :: (Array Int a, Array Int a, UArray Int Double) -> StdGen ->
[a]

the sample code was about one second faster when compiled with -O2.
Profiling again indicated that most time was spend in random and randomR
(I manually added cost centers into "next"):

	   main +RTS -p -RTS

	total time  =        8.00 secs   (160 ticks @ 50 ms)
	total alloc = 2,430,585,728 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

random                         Random                60.0   54.5
randomR                        Random                20.0   23.3
next                           Random                17.5   17.0
main                           Main                   1.9    2.5
randomList                     Random                 0.6    2.8


previously (i.e. with long class contexts) it looked like this:


	   main +RTS -p -RTS

	total time  =        7.85 secs   (157 ticks @ 50 ms)
	total alloc = 2,442,579,716 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

random                         Random                58.6   54.5
randomR                        Random                22.9   23.3
next                           Random                14.6   16.5
main                           Main                   2.5    2.5
randomList                     Random                 1.3    3.1


Many thanks again,
Thoralf