[Haskell-cafe] Performance problem with random numbers

[Don Stewart]

dons:
> stefanor:
> > On Sat, Oct 13, 2007 at 12:09:57AM +0200, ntupel wrote:
> > > Dear all,
> > > 
> > > I have implemented a small module to generate random items with a given
> > > probability distribution using the alias approach [1] and unfortunately
> > > compared to similar implementations in C++ or Java it is about 10 times
> > > slower. I have to confess that I am still in the early stages of writing
> > > Haskell programs so there is hopefully something I can do about it and I
> > > hope some helpful soul on this list can give me a hint. 
> > 
> > > 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 haven't looked at your code in depth, but these long contexts are
> > something of a red flag.  Overloading in Haskell is a very neat
> > mechanism, but it is not really suitable for inner loops; each type
> > class listed turns into an extra parameter, and proxy methods use
> > indirect function calls for the operations (which unfortunately show up
> > in profiles with the same names as the specific operations).
> > 
> > I would try specializing to StdGen, UArray, and Int, for RandomGen,
> > IArray, and Random respectively.
> > 
> > P.S. Most real programs (outside of specialized niches like Monte-Carlo
> > simulation) spend neglible amounts of time in random number generation.
> > Profile before optimizing!  If you've already profiled the real program,
> > ignore this postscript.
> > 
> > Stefan
> 
> 
> I agree with Stefan's analysis. Very suspicious types for high
> performance code! 
> 
> And again, the only time random generation actually mattered to me was
> in a high perf monte carlo simulation, after all the inner loops had
> been specialised.
> 

I should add: and in that case we called the mersenne twister generator
carefully optimised in C.

-- Don