# #StackBounty: #performance #haskell #recursion #optimization #benchmarking Why do these fixpoint cata / ana morphism definitions outper…

### Bounty: 100

Consider these definitions from a previous question:

``````type Algebra f a = f a -> a

cata :: Functor f => Algebra f b -> Fix f -> b
cata alg = alg . fmap (cata alg) . unFix

fixcata :: Functor f => Algebra f b -> Fix f -> b
fixcata alg = fix \$ f -> alg . fmap f . unFix

type CoAlgebra f a = a -> f a

ana :: Functor f => CoAlgebra f a -> a -> Fix f
ana coalg = Fix . fmap (ana coalg) . coalg

fixana :: Functor f => CoAlgebra f a -> a -> Fix f
fixana coalg = fix \$ f -> Fix . fmap f . coalg
``````

I ran some benchmarks and the results are surprising me. `criterion` reports something like a tenfold speedup, specifically when `O2` is enabled. I wonder what causes such massive improvement, and begin to seriously doubt my benchmarking abilities.

This is the exact `criterion` code I use:

``````smallWord, largeWord :: Word
smallWord = 2^10
largeWord = 2^20

shortEnv, longEnv :: Fix Maybe
shortEnv = ana coAlg smallWord
longEnv = ana coAlg largeWord

benchCata = nf (cata alg)
benchFixcata = nf (fixcata alg)

benchAna = nf (ana coAlg)
benchFixana = nf (fixana coAlg)

main = defaultMain
[ bgroup "cata"
[ bgroup "short input"
[ env (return shortEnv) \$ x -> bench "cata"    (benchCata x)
, env (return shortEnv) \$ x -> bench "fixcata" (benchFixcata x)
]
, bgroup "long input"
[ env (return longEnv) \$ x -> bench "cata"    (benchCata x)
, env (return longEnv) \$ x -> bench "fixcata" (benchFixcata x)
]
]
, bgroup "ana"
[ bgroup "small word"
[ bench "ana" \$ benchAna smallWord
, bench "fixana" \$ benchFixana smallWord
]
, bgroup "large word"
[ bench "ana" \$ benchAna largeWord
, bench "fixana" \$ benchFixana largeWord
]
]
]
``````

And some auxiliary code:

``````alg :: Algebra Maybe Word
alg Nothing = 0
alg (Just x) = succ x

coAlg :: CoAlgebra Maybe Word
coAlg 0 = Nothing
coAlg x = Just (pred x)
``````

Compiled with `O0`, the digits are pretty even. With `O2`, `fix~` functions seem to outperform the plain ones:

``````benchmarking cata/short input/cata
time                 31.67 μs   (31.10 μs .. 32.26 μs)
0.999 R²   (0.998 R² .. 1.000 R²)
mean                 31.20 μs   (31.05 μs .. 31.46 μs)
std dev              633.9 ns   (385.3 ns .. 1.029 μs)
variance introduced by outliers: 18% (moderately inflated)

benchmarking cata/short input/fixcata
time                 2.422 μs   (2.407 μs .. 2.440 μs)
1.000 R²   (1.000 R² .. 1.000 R²)
mean                 2.399 μs   (2.388 μs .. 2.410 μs)
std dev              37.12 ns   (31.44 ns .. 47.06 ns)
variance introduced by outliers: 14% (moderately inflated)
``````

I would appreciate if someone can confirm or spot a flaw.

*I compiled things with `ghc 8.2.2` on this occasion.)

postscriptum

This post from back in 2012 elaborates on the performance of `fix` in quite a fine detail. (Thanks to `@chi` for the link.)

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.