Freer Monads: Too Fast, Too Free

The venerable Lyxia had this to say about my last post on freer monads:

I agree the performance argument is way less important than the frequency at which it’s thrown around makes it seem. The reason freer performance sucks is that you’re repeatedly constructing and deconstructing trees at runtime. However, that is only a consequence of the implementation of freer as a GADT (initial encoding). I bet the final encoding can do wonders:

newtype Freer f a = Freer (forall m. Monad m => (forall t. f t -> m t) -> m a)

I spent a few days working through the implications of this, and it turns out to be a particularly compelling insight. Behold the microbenchmarks between freer-simple and an equivalent program written against mtl:

benchmarking freer-simple
time                 745.6 μs   (741.9 μs .. 749.4 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 745.1 μs   (742.2 μs .. 748.5 μs)
std dev              10.68 μs   (8.167 μs .. 14.23 μs)

benchmarking mtl
time                 10.96 μs   (10.93 μs .. 10.98 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 10.95 μs   (10.92 μs .. 10.99 μs)
std dev              119.3 ns   (93.42 ns .. 153.7 ns)

Not so good; freer-simple is like 75x worse in this case! But the same program again when written in this final encoding is pretty damn fast:

benchmarking too-fast-too-free
time                 24.23 μs   (24.10 μs .. 24.37 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 24.27 μs   (24.15 μs .. 24.40 μs)
std dev              448.8 ns   (355.8 ns .. 586.1 ns)

It’s roughly 2x slower than mtl, which is AKA 35x faster than freer-simple. This is pretty sweet, and it comes with the benefit of getting to keep the underlying semantics of freer-simple.

So without further ado, I’d like to share my work-in-progress with you, tentatively named too-fast-too-free. This is ready for prime-time, but I’d prefer to merge it to someone upstream rather than pollute hackage with yet another free(r) monad extensible effects package.

I’ll do it if I have to, but the performance is fair game for anyone who wants it. If I don’t hear from anyone by next week, I’ll publish a new package to hackage and begin the freer monad revolution we’ve all been waiting for.

What the Heck Is Any of this Stuff Anyway?🔗

Let’s investigate this finally-encoded type and see where this performance comes from:

newtype Freer f a = Freer
  { runFreer :: forall m. Monad m => (forall t. f t -> m t) -> m a
  }

The type of runFreer is saying “if you give me a Freer f a and a natural transformation from f to some monad m, then I can give you back an m a.” Sounds promising, right?

Freer’s instance for Monad is written in terms of this final m, and so short of shunting around some functions, we’re not really paying any cost for binds compared to just writing in terms of m:

instance Monad (Freer f) where
  Freer ma >>= f = Freer $ \k -> do
    a <- ma k
    runFreer (f a) k

Compare this to the approach used by freer-simple which needs to allocate leafs in a tree for every bind (and for every fmap and ap!) That’s a huge win already.

Turning Freer into Eff uses the same trick as freer-simple—let Eff r be Freer (Union r), where Union r is a value that can be any effect in r. A natural transformation forall m. Monad m => (forall t. Union r t -> m t) must therefore handle every possible effect in r, and so we haven’t lost any capabilities with our new encoding.

The challenging part was figuring out how to plumb state through the encoding of Freer f a—after all, many interesting interpreters are necessarily stateful.

Fortunately there’s a trick. Because Eff (e ': r) a can be interpreted in terms of any Monad m, we can choose m ~ StateT s (Eff r), and get our statefulness from StateT directly. Because StateT’s bind is written in terms of its underlying monad, this trick doesn’t cost us anything more than shunting another few functions around.

We can achieve short-circuiting interpreters similarly by evaluating them via ExceptT (Eff r). In fact, this pattern turns out to be pretty common—and it generalizes thusly:

transform
    :: ( MonadTrans t
       , MFunctor t
       , forall m. Monad m => Monad (t m)
       )
    => (forall m. Monad m => t m a -> m b)
       -- ^ The strategy for getting out of the monad transformer.
    -> (eff ~> t (Eff r))
    -> Eff (eff ': r) a
    -> Eff r b
transform lower f (Freer m) = Freer $ \k -> lower $ m $ \u ->
  case decomp u of
    Left  x -> lift $ k x
    Right y -> hoist (usingFreer k) $ f y

Admittedly the type is a little terrifying, but library code can specialize it down to less offensive combinators.

At the end of the day, this final encoding means that Freer code specializes down to its eventual result anyway, giving us the “fusion” of fused-effects without the boilerplate.

Hopefully these results are enough to finally put the “free monads have bad performance” argument to rest. I’ll have some promising results on the bracket front as well that require some refinement, but hopefully those will come sooner than later.

¡Viva la freer monad revolucion!