Stack Builders News

A collection of thoughts and notes by our team


Juan Pedro Villa

Obverse versus Reverse: Benchmarking in Haskell with criterion


In the Obverse and Reverse blog post, we used mathematics to improve the performance of a function that returns the elements of a list in reverse order. More specifically, we used mathematics to get from:

obverse :: [a] -> [a]
obverse []     = []
obverse (x:xs) = obverse xs ++ [x]

To:

reverse :: [a] -> [a]
reverse xs = reverse' xs []
  where
    reverse' []      ys = ys
    reverse' (x:xs') ys = reverse' xs' (x:ys)

Additionally, we measured the time it takes for both functions to reverse specific lists using the clockSomething function, which uses the clock package as described by Chris Done in Measuring duration in Haskell:

clockSomething :: a -> IO ()
clockSomething something = do
  start <- getTime Monotonic
  void (evaluate something)
  end <- getTime Monotonic
  fprint (timeSpecs % "\n") start end

In particular, we clocked the time it takes to reverse lists of one and ten million consecutive integers, as follows:

ghci> clockSomething (obverse [1..1000000] :: [Integer])
320.47 ms
ghci> clockSomething (reverse [1..1000000] :: [Integer])
176.93 ms
ghci> clockSomething (obverse [1..10000000] :: [Integer])
3.38 s
ghci> clockSomething (reverse [1..10000000] :: [Integer])
1.63 s

Instead of using lists of consecutive integers, we can use QuickCheck to generate lists of a given length with arbitrary integers:

arbitraryIntVectorOf :: Int -> IO [Int]
arbitraryIntVectorOf n = generate (vectorOf n arbitrary)

For example:

ghci> arbitraryIntVectorOf 10
[5,15,11,6,-22,21,-18,29,10,1]
ghci> arbitraryIntVectorOf 10
[24,-23,-19,15,20,-9,21,-30,-28,5]

Now we can generate several lists of ten million random integers and compare the time it takes for both functions to reverse them:

main :: IO ()
main = do
  putStrLn "obverse versus reverse/10000000..."
  putStr   "  obverse/1... "
  arbitraryIntVectorOf 10000000 >>= clockSomething . obverse
  putStr   "  reverse/1... "
  arbitraryIntVectorOf 10000000 >>= clockSomething . reverse
  putStr   "  obverse/2... "
  arbitraryIntVectorOf 10000000 >>= clockSomething . obverse
  putStr   "  reverse/2... "
  arbitraryIntVectorOf 10000000 >>= clockSomething . reverse
  ...

And this is just an executable that we can add to a Cabal file as a benchmark:

benchmark clock-benchmarks
  build-depends:
    base,
    clock,
    formatting >= 6.1.0,
    QuickCheck,
    reverse,
    time
  default-language: Haskell2010
  ghc-options:      -Wall
  hs-source-dirs:   benchmarks
  main-is:          ClockBenchmarks.hs
  type:             exitcode-stdio-1.0

In order to run clock-benchmarks, we use cabal bench:

$ cabal bench clock-benchmarks
...
Benchmark clock-benchmarks: RUNNING...
obverse versus reverse/10000000...
  obverse/1... 3.63 s
  reverse/1... 1.85 s
  obverse/2... 4.44 s
  reverse/2... 1.33 s
  obverse/3... 3.30 s
  reverse/3... 2.27 s
  obverse/4... 3.22 s
  reverse/4... 2.14 s
  obverse/5... 3.38 s
  reverse/5... 1.32 s
Benchmark clock-benchmarks: FINISH

In average, obverse and reverse took 3.59 and 1.78 seconds to reverse lists of ten million elements, respectively, which confirms that reverse beats obverse in terms of performance.

Even though clocking things is useful, Haskell provides much more powerful ways to benchmark programs, like Bryan O'Sullivan's criterion benchmarking library, which has an easy tutorial and complete documentation. Let's use criterion for comparing the obverse and reverse functions.

First, we define a function that generates two lists of a given length with arbitrary integers using the arbitraryIntVectorOf function:

arbitraryIntVectorsOf :: Int -> IO ([Int],[Int])
arbitraryIntVectorsOf n = do
  xs <- arbitraryIntVectorOf n
  ys <- arbitraryIntVectorOf n
  return (xs,ys)

Second, we create an executable in which we run obverse and reverse over random lists of one hundred, one thousand, and ten thousand integers:

main :: IO ()
main =
  defaultMainWith
    (defaultConfig {reportFile = Just "obverse-versus-reverse.html"})
    [env (arbitraryIntVectorsOf 100)
         (\ ~(xs,ys) ->
            bgroup
              "obverse versus reverse/100"
              [bench "obverse" $ nf obverse xs
              ,bench "reverse" $ nf reverse ys])
    ,env (arbitraryIntVectorsOf 1000)
         (\ ~(xs,ys) ->
            bgroup
              "obverse versus reverse/1000"
              [bench "obverse" $ nf obverse xs
              ,bench "reverse" $ nf reverse ys])
    ,env (arbitraryIntVectorsOf 10000)
         (\ ~(xs,ys) ->
            bgroup
              "obverse versus reverse/10000"
              [bench "obverse" $ nf obverse xs
              ,bench "reverse" $ nf reverse ys])]

We use criterion's defaultMainWith, which takes a configuration and a list of benchmarks. We use the default configuration, but specify a report file to get a complete report. We have three benchmarks, which correspond to the lists of one hundred, one thousand, and ten thousand elements.

For each benchmark, we use env, which creates an environment (in each case, it creates two lists of the given length) and then uses it to produce a benchmark. Each benchmark consists of two benchmarks grouped by bgroup and identified by either "obverse" or "reverse". The benchmarks apply both functions to the generated lists using nf (which evaluates the result to head normal form) taking into account that the result is a lazy structure.

Of course, we can add this executable to a Cabal file, as follows:

benchmark criterion-benchmarks
  build-depends:    base, criterion, QuickCheck, reverse
  default-language: Haskell2010
  ghc-options:      -Wall
  hs-source-dirs:   benchmarks
  main-is:          CriterionBenchmarks.hs
  type:             exitcode-stdio-1.0

And run it using cabal bench:

$ cabal bench criterion-benchmarks
...
Benchmark criterion-benchmarks: RUNNING...
benchmarking obverse versus reverse/100/obverse
time                 35.82 μs   (35.34 μs .. 36.44 μs)
                     0.998 R²   (0.998 R² .. 0.999 R²)
mean                 36.06 μs   (35.66 μs .. 36.50 μs)
std dev              1.406 μs   (1.218 μs .. 1.591 μs)
variance introduced by outliers: 43% (moderately inflated)

benchmarking obverse versus reverse/100/reverse
time                 919.8 ns   (912.1 ns .. 930.7 ns)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 936.5 ns   (925.9 ns .. 949.1 ns)
std dev              40.75 ns   (35.83 ns .. 44.23 ns)
variance introduced by outliers: 60% (severely inflated)

benchmarking obverse versus reverse/1000/obverse
time                 5.994 ms   (5.934 ms .. 6.050 ms)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 5.987 ms   (5.964 ms .. 6.021 ms)
std dev              81.83 μs   (58.04 μs .. 130.1 μs)

benchmarking obverse versus reverse/1000/reverse
time                 9.551 μs   (9.495 μs .. 9.633 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 9.510 μs   (9.490 μs .. 9.558 μs)
std dev              92.05 ns   (52.81 ns .. 165.5 ns)

benchmarking obverse versus reverse/10000/obverse
time                 1.520 s    (1.499 s .. 1.537 s)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 1.518 s    (1.514 s .. 1.520 s)
std dev              3.648 ms   (0.0 s .. 4.206 ms)
variance introduced by outliers: 19% (moderately inflated)

benchmarking obverse versus reverse/10000/reverse
time                 133.6 μs   (133.1 μs .. 134.4 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 134.7 μs   (133.9 μs .. 136.1 μs)
std dev              3.611 μs   (2.359 μs .. 5.243 μs)
variance introduced by outliers: 22% (moderately inflated)

Benchmark criterion-benchmarks: FINISH

The output of each benchmark lists the time needed for a single execution of the function being benchmarked, followed by a goodness of fit measure which should lie between 0.99 and 1, the mean execution time, the standard deviation, and an optional warning of variance introduced by outliers, which is moderate in three cases and severe in one (but we'll ignore that for now and blame "the phase of the moon").

Again, it's clear that reverse beats obverse considering the execution times, but the report file includes charts and a lot of useful information, as well as details about what everything means.


Many thanks to Franklin Chen, who suggested using criterion for comparing the obverse and reverse functions.

Do You Have What it Takes To Be a Stack Builder?