Re: [Haskell-cafe] Performance problem with random numbers
On Sat, 2007-10-13 at 18:33 -0300, Isaac Dupree wrote: GHC StdGen's random and randomR are somewhat slow. I found that changing to a custom ((x*a + b) `mod` c) random-generator (instance of RandomGen) much sped things up (since nothing depended on the random numbers being good quality). Yes, I also switched now to a simple custom linear congruential generator (which is random enough for this task) and restructured the code a bit and am happy now since it is even a bit faster than the Java implementation :) Thanks, Thoralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Performance problem with random numbers
We'd be delighted if someone offered a more performant library to put into future GHC releases. Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Don | Stewart | Sent: 13 October 2007 22:38 | To: Isaac Dupree | Cc: haskell-cafe@haskell.org | Subject: Re: [Haskell-cafe] Performance problem with random numbers | | isaacdupree: | ntupel wrote: | Thanks for your reply Stefan. Unfortunately I could measure only a | relatively small improvement by changing to concrete types | | the sample code was about one second faster when compiled with -O2. | Profiling again indicated that most time was spend in random and randomR | | GHC StdGen's random and randomR are somewhat slow. I found that | changing to a custom ((x*a + b) `mod` c) random-generator (instance of | RandomGen) much sped things up (since nothing depended on the random | numbers being good quality). (Then I switched to a small C function to | do the randomization and make all the OpenGL calls, and it sped up by | another factor of 4.) | | | I've seen similar results switching to the SIMD mersenne twister C | implementation for randoms: | | http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html | | If there's interest, I can package up the bindings for hackage. | | -- Don | ___ | Haskell-Cafe mailing list | Haskell-Cafe@haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
Does the GHC code generator makes use of SIMD instructions? Maybe via the C compiler? Cheers, Peter Simon Peyton-Jones wrote: We'd be delighted if someone offered a more performant library to put into future GHC releases. | I've seen similar results switching to the SIMD mersenne twister C | implementation for randoms: ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
On Tue, Oct 16, 2007 at 06:07:39PM +0200, Peter Verswyvelen wrote: Does the GHC code generator makes use of SIMD instructions? Maybe via the C compiler? No. GHC uses GCC extensions, and GCC doesn't support automatic SIMD use. (You could use -unreg and an advanced compiler. Good luck finding a compiler smart enough to work around the idiocies incurred translating Haskell to ANSI C; -unreg is very slow) Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
The Mersenne twister should be able to split better than most. but I'm not sure how efficient it is. On 10/14/07, Isaac Dupree [EMAIL PROTECTED] wrote: Don Stewart wrote: I've seen similar results switching to the SIMD mersenne twister C implementation for randoms: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html If there's interest, I can package up the bindings for hackage. looks nice... at least for those of us who have non-old computer CPUs Is there a decent way to implement 'split'? A way that doesn't take too long to run, and produces fairly independent generators? Isaac ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
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 CENTREMODULE %time %alloc random Random60.0 54.5 randomRRandom20.0 23.3 next Random17.5 17.0 main Main 1.92.5 randomList Random 0.62.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 CENTREMODULE %time %alloc random Random58.6 54.5 randomRRandom22.9 23.3 next Random14.6 16.5 main Main 2.52.5 randomList Random 1.33.1 Many thanks again, Thoralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
On Oct 13, 2007, at 6:52 , ntupel wrote: 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 (...) COST CENTREMODULE %time %alloc random Random60.0 54.5 randomRRandom20.0 23.3 next Random17.5 17.0 main Main 1.92.5 randomList Random 0.62.8 Now you need to start forcing things; given laziness, things tend to only get forced when in IO, which leads to time being accounted to the routine where the forcing happened. If random / randomR are invoked with large unevaluated thunks, their forcing will generally be attributed to them, not to functions within the thunks. (Yes, this means profiling lazy programs is a bit of a black art.) -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
On Sat, 2007-10-13 at 09:56 -0400, Brandon S. Allbery KF8NH wrote: Now you need to start forcing things; given laziness, things tend to only get forced when in IO, which leads to time being accounted to the routine where the forcing happened. If random / randomR are invoked with large unevaluated thunks, their forcing will generally be attributed to them, not to functions within the thunks. But AFAIK random and randomR only take a StdGen (plus a range argument in case of randomR) as argument so I don't understand where the unevaluated thunks might be actually? (Maybe I should have said that random and randomR are the ones from GHC's System.Random module.) Thanks, Thoralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
On Oct 13, 2007, at 11:40 , ntupel wrote: On Sat, 2007-10-13 at 09:56 -0400, Brandon S. Allbery KF8NH wrote: Now you need to start forcing things; given laziness, things tend to only get forced when in IO, which leads to time being accounted to the routine where the forcing happened. If random / randomR are invoked with large unevaluated thunks, their forcing will generally be attributed to them, not to functions within the thunks. But AFAIK random and randomR only take a StdGen (plus a range argument in case of randomR) as argument so I don't understand where the unevaluated thunks might be actually? (Maybe I should have said that random and randomR are the ones from GHC's System.Random module.) Your apparently simple StdGen argument is actually a sort of program state (represented by unevaluated thunks, not by a state monad; see below) which gets altered with every invocation of random. If nothing is forced until the very end, it in effect becomes an expression which produces the desired StdGen, with the uses of the previous StdGen values as side effects of its computation that occur when the thunk is evaluated at the end. I'm not sure I'm up to working through an example of what this looks like. Suffice it to say that in a lazy language like Haskell, almost any simple expression can in practice end up being a suspended computation (a thunk) consisting of whatever is supposed to produce it. And in the general case (e.g. you don't use strictness annotations) the only way to force evaluation is to do I/O, so it's quite normal for a naive program to end up being one big thunk dangling off a PutStrLn. So why does random get tagged for it? Because it's a state-like function (that is, a function of the form s - (a,s); compare to the definition of the State monad) which takes a StdGen and produces a modified StdGen, so when Haskell finally evaluates the thunk most of the activity happens in the context of evaluating that modification. Hopefully someone reading -cafe can explain it better; I'm pretty lousy at it, as you can probably tell. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
On Sat, 2007-10-13 at 12:42 -0400, Brandon S. Allbery KF8NH wrote: Your apparently simple StdGen argument is actually a sort of program state (represented by unevaluated thunks, not by a state monad; see below) which gets altered with every invocation of random. If nothing is forced until the very end, it in effect becomes an expression which produces the desired StdGen, with the uses of the previous StdGen values as side effects of its computation that occur when the thunk is evaluated at the end. I'm not sure I'm up to working through an example of what this looks like. Thanks Brandon. I understand your argument but I don't know how to put it into practice, i.e. how to force the evaluation of StdGen. - Thoralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
On Oct 13, 2007, at 13:30 , ntupel wrote: On Sat, 2007-10-13 at 12:42 -0400, Brandon S. Allbery KF8NH wrote: Your apparently simple StdGen argument is actually a sort of program state (represented by unevaluated thunks, not by a state monad; see below) which gets altered with every invocation of random. If nothing is forced until the very end, it in effect becomes an expression which produces the desired StdGen, with the uses of the previous StdGen values as side effects of its computation that occur when the thunk is evaluated at the end. I'm not sure I'm up to working through an example of what this looks like. Thanks Brandon. I understand your argument but I don't know how to put it into practice, i.e. how to force the evaluation of StdGen. For starters, look into seq. Try applying it to any expression using a generated random number. This should force evaluation to occur somewhere other than when random is trying to figure out what StdGen value it's been told to use as its initial state. Alternately you can put all the uses in IO and use Control.Exception.evaluate (or even print). This is probably not what you want to do in your actual production code, however. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
On Sat, 2007-10-13 at 13:35 -0400, Brandon S. Allbery KF8NH wrote: For starters, look into seq. Try applying it to any expression using a generated random number. This should force evaluation to occur somewhere other than when random is trying to figure out what StdGen value it's been told to use as its initial state. Ok, but I still wonder where that might be. random and randomR are used in a function named next as show here: next :: (Array Int a, Array Int a, UArray Int Double) - StdGen - (a, StdGen) next (xs, as, rs) g = let n = length $ indices xs (x1, g1) = randomR (0, n - 1) g (x2, g2) = random g1 r = rs!x1 in if x2 = r then (xs!x1, g2) else (as!x1, g2) x1 and x2 are used in the same function so I assume this already requires their evaluation. The only function that calls next is randomList: randomList :: (Array Int a, Array Int a, UArray Int Double) - StdGen - [a] randomList t g = let (n, g') = next t g in n:randomList t g' Cf. my original e-mail for the complete program. Alternately you can put all the uses in IO and use Control.Exception.evaluate (or even print). This is probably not what you want to do in your actual production code, however. Right. This is not what I want. Many thanks again, Thoralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
ntupel wrote: Thanks for your reply Stefan. Unfortunately I could measure only a relatively small improvement by changing to concrete types the sample code was about one second faster when compiled with -O2. Profiling again indicated that most time was spend in random and randomR GHC StdGen's random and randomR are somewhat slow. I found that changing to a custom ((x*a + b) `mod` c) random-generator (instance of RandomGen) much sped things up (since nothing depended on the random numbers being good quality). (Then I switched to a small C function to do the randomization and make all the OpenGL calls, and it sped up by another factor of 4.) Isaac ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
isaacdupree: ntupel wrote: Thanks for your reply Stefan. Unfortunately I could measure only a relatively small improvement by changing to concrete types the sample code was about one second faster when compiled with -O2. Profiling again indicated that most time was spend in random and randomR GHC StdGen's random and randomR are somewhat slow. I found that changing to a custom ((x*a + b) `mod` c) random-generator (instance of RandomGen) much sped things up (since nothing depended on the random numbers being good quality). (Then I switched to a small C function to do the randomization and make all the OpenGL calls, and it sped up by another factor of 4.) I've seen similar results switching to the SIMD mersenne twister C implementation for randoms: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html If there's interest, I can package up the bindings for hackage. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
On Sat, 2007-10-13 at 14:37 -0700, Don Stewart wrote: I've seen similar results switching to the SIMD mersenne twister C implementation for randoms: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html If there's interest, I can package up the bindings for hackage. I would definitely be interested. Many thanks, Thoralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
Don Stewart wrote: I've seen similar results switching to the SIMD mersenne twister C implementation for randoms: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html If there's interest, I can package up the bindings for hackage. looks nice... at least for those of us who have non-old computer CPUs Is there a decent way to implement 'split'? A way that doesn't take too long to run, and produces fairly independent generators? Isaac ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
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 signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance problem with random numbers
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
