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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe