[Haskell-cafe] Performance problem with random numbers

[Don Stewart]

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.

-- Don