Skip to content
No description, website, or topics provided.
Branch: master
Clone or download
Pull request Compare This branch is 30 commits ahead of feuerbach:master.
Latest commit 331e18a Oct 30, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
Data
.gitignore
Base.hs
Church.hs
Codensity.hs
Computation.hs
Free.hs
Freer.hs Add Freer Dec 10, 2015
Fused.hs
LICENSE
Main.hs
NoRemorse.hs NoRemorse: update for AMP, fix warnings Dec 10, 2015
README.md Fix benchmarks link Oct 30, 2018
Setup.hs Cabalize Dec 10, 2015
freemonad-benchmark.cabal
results.html
run
stack.yaml

README.md

A benchmark comparing the performance of different free monad implementations.

The benchmark simulates the state monad using various flavors of free monads, and compares them to the standard State monad from transformers.

Note that this is not a comparison of extensible effects system. Free monads may be used to implement an extensible effect system. Under most implementations, extensible effects introduce an even bigger overhead (dispatching upon the effect requests); this overhead is not present in this benchmark. However, if your free monad is slow (which it probably is, as this benchmark shows), any effect system based on it won't be fast.

Running the benchmark

stack build && stack exec freemonad-benchmark -- -o results.html

Results

Criterion report

Implementations

  1. Free

    data Free f a = Pure a | Free (f (Free f a))
  2. Free/lazy

    The same standard Free monad emulating the lazy State monad.

  3. Church

    The Church-encoded free monad:

    newtype ChurchFree f a = ChurchFree
      { runChurchFree :: forall w. (a -> w) -> (f w -> w) -> w }
  4. Codensity

    The standard Free monad, codensity-transformed. See Asymptotic Improvement of Computations over Free Monads.

  5. NoRemorse

    A free monad from Reflection without Remorse.

  6. Freer

    The Freer monad from Freer Monads, More Extensible Effects, aka the operational monad.

  7. Effects

    An extensible effects implementation with higher-order effects based off Freer Monads, More Extensible Effects maintained by @joshvera and @robrix.

  8. Fused

    An implementation of Fusion for Free: Efficient Algebraic Effect Handlers by @brfk.

Workloads

For every implementation, there are two tests, for left- and right-associated chains of binds. Some free monads (e.g. the standard one) suffer from quadratic complexity on left-associated chains of binds.

You can’t perform that action at this time.