[Haskell-cafe] Performance problem with random numbers

[Stefan O'Rear]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20071012/c06e85a3/attachment-0001.bin