[Haskell-cafe] Re: Performance question

[Benedikt Huber]

haskell at kudling.de schrieb:
> Hi,
> 
> i have compared a C++ implementation with a Haskell implementation of the Monte Carlo Pi approximation:
> 
> http://lennart.kudling.de/haskellPi/
> 
> The Haskell version is 100 times slower and i wonder whether i do something obvious wrong.
>
Hi,
Nice benchmark, but I think the culprit is the random number generator.
For simplicity, here is a 1-1 translation of the C++ code:

 > main =
 >    do args <- getArgs
 >       let samples = read $ head args
 >       randomNumbers <- genRandoms
 >       print (monteCarlo samples randomNumbers)
 > genRandoms :: IO [Double]
 > genRandoms = liftM randoms getStdGen
 > monteCarlo :: Int -> [Double] -> Double
 > monteCarlo samples = go 0 samples where
 >     go cnt 0 _ = (4.0 :: Double) * (fromIntegral cnt) /
 >                  (fromIntegral > samples)
 >     go cnt k (x:y:rs) | sqrt (x*x + y*y) <= 1.0 = go (cnt+1) (k-1) rs
 >                       | otherwise               = go cnt     (k-1) rs

The profiling shows that most time is spend in genRandoms:

genRandoms Main 199 1  96.5   98.3    96.5   98.3

When replacing genRandoms by (repeat 0.5), the haskell code is only a 
little bit slower than the C++ code *with* random number generation.

Of course, the random number generation in C++ takes time too:

 > montecarlo(0) $ pprof --text ./monte_carlo /tmp/profile
 > Total: 6691 samples
 >    3928  58.7%  58.7%     5965  89.1% _main
 >    2134  31.9%  90.6%     2134  31.9% _do_rand
 >     435   6.5%  97.1%      435   6.5% _rand
 >     194   2.9% 100.0%      194   2.9% 0x00003072
 >       0   0.0% 100.0%     6691 100.0% __mh_execute_header
 >       0   0.0% 100.0%     6691 100.0% start

But the factor 100 is clearly due to genRandoms.

cheers, benedikt

> Profiling says that the majority of the time is spend in "main". But i have no idea where.
> 
> Can someone give me a hint?
> 
> Thanks,
> Lenny
> 
>                                                                individual    inherited
> COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc
> 
> MAIN                     MAIN                                                   1           0   0.0    0.0   100.0  100.0
>  main                    Main                                                 254           1  88.1   90.8   100.0  100.0
>   monteCarloPi           Main                                                 255           1   0.6    1.1    11.9    9.2
>    pairs                 Main                                                 257    10000000   0.7    1.4     0.7    1.4
>    countHits             Main                                                 256    10000001   4.2    2.9    10.6    6.7
>     accumulateHit        Main                                                 258    27852236   3.0    2.3     6.4    3.8
>      isInCircle          Main                                                 259    30000000   3.3    1.5     3.3    1.5
>  CAF:lit_r1A7            Main                                                 248           1   0.0    0.0     0.0    0.0
>   isInCircle             Main                                                 260           0   0.0    0.0     0.0    0.0