[Haskell-cafe] Performance best practices

[Jaro Reinders]

I think the best way to test the performance is to use a benchmarking
library such as criterion (http://www.serpentine.com/criterion/)

    import Criterion.Main
    import Data.List (inits,tails)

    splits1, splits2, splits3 :: [a] -> [([a],[a])]
    splits1 xs = zip (inits xs) (tails xs)

    splits2 [] = [([],[])]
    splits2 xs@(x:xs') = ([],xs) : [(x:as,bs) | (as,bs) <- splits2 xs']

    splits3 = go id where
      go prefix xs = (prefix [],xs) : case xs of
        x:xs -> go (prefix . (x :)) xs
        [] -> []

    main = defaultMain
      [ bench "splits1" $ nf splits1 input
      , bench "splits2" $ nf splits2 input
      , bench "splits3" $ nf splits3 input
      ]
      where
        input :: [Int]
        input = [1..1000]

It gives the following results on my computer:

    benchmarking splits1
    time                 4.693 ms   (4.625 ms .. 4.752 ms)
                         0.999 R²   (0.998 R² .. 0.999 R²)
    mean                 4.725 ms   (4.694 ms .. 4.758 ms)
    std dev              97.37 μs   (77.95 μs .. 123.3 μs)

    benchmarking splits2
    time                 12.10 ms   (11.96 ms .. 12.25 ms)
                         0.999 R²   (0.999 R² .. 1.000 R²)
    mean                 12.08 ms   (12.03 ms .. 12.14 ms)
    std dev              149.7 μs   (110.0 μs .. 199.1 μs)

    benchmarking splits3
    time                 4.110 ms   (4.025 ms .. 4.187 ms)
                         0.997 R²   (0.996 R² .. 0.999 R²)
    mean                 4.124 ms   (4.081 ms .. 4.177 ms)
    std dev              147.6 μs   (115.6 μs .. 238.5 μs)
    variance introduced by outliers: 17% (moderately inflated)

On 01-08-2019 04:45, Todd Wilson wrote:
> Dear Cafe:
> 
> I'm getting to the point in my Haskell learning curve where I'm
> getting more interested in the fine points of programming for
> performance and would be grateful for some ideas of the tools and
> options available for exploring this. To make this concrete, let me
> give a simple example. Here are two different ways of coding the same
> list-splitting function:
> 
>    import Data.List (inits,tails)
>    splits1, splits2 :: [a] -> [([a],[a])]
>    splits1 xs = zip (inits xs) (tails xs)
>    splits2 [] = [([],[])]
>    splits2 xs@(x:xs') = ([],xs) : [(x:as,bs) | (as,bs) <- splits2 xs']
> 
> For example, splits1 [1,2,3] is
> [([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])].
> 
> How do these functions compare in their actual time and space usage?
> It seems that, asymptotically, tails is O(n) while inits is O(n^2) in
> both time and space (when fully evaluated), and splits2 is also
> O(n^2), but how would I go about comparing them in actual usage to get
> a more precise comparison? What profiling or run-time statistics could
> I gather to make a decision about which one to use in a situation
> where performance mattered (assuming for the sake of discussion that
> such a situation existed for this simple example)? And, out of
> curiosity, is there an even more efficient way to code this function?
> Thanks,
> 
> Todd Wilson
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
>