[Haskell-beginners] List operations

[Daniel Fischer]

On Thursday 19 May 2011 18:15:31, Ertugrul Soeylemez wrote:
> Daniel Fischer <daniel.is.fischer at googlemail.com> wrote:
> > However, since you're asking about cost, which indicates that you care
> > for performance, the above would be better written as
> > 
> > [x*x*x | x <- list]
> > 
> > unless you depend on the small differences in the outcome [I'm not
> > quite sure how many bits may be affected, not many, typically none or
> > one].  Functions like (**), exp, log, sin, cos, ... are slow, very
> > slow.  If the exponent is a small (positive) integer, specifically
> > giving a sequence of multiplication steps is much faster, also using
> > (^) instead of (**) is faster for small exponents (but slower than an
> > explicit multiplication sequence).
> 
> Neither does this really match my intuition,

A multiplication takes ~1 clock cycle, calling out to pow takes way more (I 
confess, I don't know how many clock cycles a function call takes).

> nor can I confirm it with
> an experiment.  Applying (** 3) a million times to a Double takes a
> second and gives me the expected Infinity.  Applying (^3) or (\x ->
> x*x*x) a million times to the same value, well, I didn't want to wait
> for it to finish.
> 
> The experiment was ran with the following codes in GHCi:

Don't benchmark in ghci, use compiled code.

> 
>     iterate (** 3) 1.000000001 !! 1000000
>     iterate (^3) 1.000000001 !! 1000000
>     iterate (\x -> x*x*x) 1.000000001 !! 1000000
> 
> Note that exponentiation is a cheap operation on Double.
> 

{-# LANGUAGE BangPatterns #-}
module Main (main) where

import Criterion.Main

main :: IO ()
main = defaultMain
    [ bench "multiply"  (whnf (test (\x -> x*x*x)) 10000)
    , bench "power"     (whnf (test (\x -> x**3))  10000)
    , bench "intPower"  (whnf (test (^ (3 :: Int))) 10000)
    ]

test :: (Double -> Double) -> Int -> Double
test fun k = go k 0 (fromIntegral k)
  where
    go :: Int -> Double -> Double -> Double
    go 0 !acc !d = acc
    go j acc d = go (j-1) (acc + fun d) (d-1)

benchmarking multiply
collecting 100 samples, 20 iterations each, in estimated 727.8770 ms
bootstrapping with 100000 resamples
mean: 367.1096 us, lb 366.0110 us, ub 370.5876 us, ci 0.950
std dev: 11.04278 us, lb 2.089208 us, ub 22.41965 us, ci 0.950
found 5 outliers among 100 samples (5.0%)
  4 (4.0%) high severe
variance introduced by outliers: 0.998%
variance is unaffected by outliers

benchmarking power
collecting 100 samples, 3 iterations each, in estimated 767.6125 ms
bootstrapping with 100000 resamples
mean: 2.322663 ms, lb 2.318265 ms, ub NaN s, ci 0.950
std dev: 106.4797 us, lb 52.31957 us, ub NaN s, ci 0.950
found 7 outliers among 100 samples (7.0%)
  6 (6.0%) high severe
variance introduced by outliers: 0.999%
variance is unaffected by outliers

benchmarking intPower
collecting 100 samples, 8 iterations each, in estimated 775.3134 ms
bootstrapping with 100000 resamples
mean: 798.4662 us, lb 794.1207 us, ub 806.9849 us, ci 0.950
std dev: 31.24913 us, lb 17.17793 us, ub 59.85220 us, ci 0.950
found 7 outliers among 100 samples (7.0%)
  4 (4.0%) high mild
  3 (3.0%) high severe
variance introduced by outliers: 0.999%
variance is unaffected by outliers

> 
> Greets
> Ertugrul