Zenn
🏃

モナドオリンピック1-トラック競技-

2021/03/15に公開
Haskell
benchmark
monad
tech

はじめに

最速のモナドを決めるモナドオリンピックを開催することになりました。
この大会では、各ライブラリの提供するモナドたちが
様々な競技（ベンチマーク）に挑戦します。

競技説明

今回は副作用のないシンプルなベンチマークで計算速度を測ります。

ベンチマーク

おなじみのfibをつかいます。普通のfibは返り値が整数型ですが、次の理由から偶奇を表すブール値にしています。

  • Int型にするとReaderモナドやIdentityモナドで返り値がUnboxingされて有利になりすぎる。
  • Integer型にすると演算にかかる時間が無視できない
Fib.hs
xor :: Bool -> Bool -> Bool
xor True x = not x
xor False x = x

fib :: Monad m => Int -> m Bool
fib = go
  where
    go n
      | n <= 1 = pure $! n == 1
      | otherwise = do
        r1 <- fib (n -1)
        r2 <- fib (n -2)
        pure $! r1 `xor` r2

評価方法

fib nを評価してその結果の数を計算するまでにかかった時間をもとに、1秒あたりのbind演算子(>>=)の処理性能(binds/s)を算出します。

  • パラメータnは10,20,30（軽い計算、中程度の計算、重い計算）でそれぞれ評価します。

  • bind演算子はインライン展開されるかどうかで大きく処理性能が変わることが知られています。そのため、インライン展開されるfibとインライン展開されないslowFibでそれぞれ評価します。

    {-# NOINLINE slowFib #-}
slowFib :: Monad m => Int -> m Bool
slowFib = fib

Binds/sの算出

fib nを評価した時のbindの計算回数をB(n)と表すことにすると

\begin{aligned} B(0) &= 0 \\ B(1) &= 0 \\ B(n) &= B(n-1) + B(n-2) + 2 \end{aligned}

となります。この定義にしたがって計算するとB(10) = 176, B(20) = 21{,}890, B(30) = 2{,}692{,}536 となります。

実行時間TをB(n)で割ったものを処理性能(binds/s)とします。

選手紹介

以下のモナドたちを評価します。

baseパッケージ

よく使うモナドを対象とします。

  • Either
  • Identity
  • IO
  • List ([])
  • Maybe
  • Reader ((->) r)

transformersパッケージ

transformersにて定義されているモナドトランスフォーマーを評価します。
各トランスフォーマーのベースモナドはIdentityとします。

なおListTはDeprecatedなので除外しています。

  • AccumT
  • ContT
  • ExceptT
  • MaybeT
  • ReaderT
  • RWST
    • Strict (RWSSTと表記)
    • Lazy (RWSLTと表記)
    • CPS (RWSCTと表記)
  • SelectT
  • StateT
    • Strict (StateSTと表記)
    • Lazy (StateLTと表記)
  • WriterT
    • Strict (WriterSTと表記)
    • Lazy (WriterLTと表記)
    • CPS (WriterCTと表記)

その他

transformersの代替となるモナドたちを評価します。

競技結果

Fib

fib結果

nの大きさによって大きく性能が変わるモナドはbind演算子が定数時間ではないということをあらわしています。

結果をまとめるとモナドたちは以下のように分類できます。

順位 モナド 処理性能
1 Identity/Reader/ReaderT/SelectT 2.2e8
2 IO/RIO/StateS/StateL/RWSCT/RWSST/WriterCT/WriterST 1.6e8
3 Maybe/MaybeT 1.5e8
4 Either/ExceptT 1.4e8
5 ContT/AccumT/WriterLT 1.3e8
6 Eff/EffSkeleton 1.0e8
>>> 越えられない壁 <<<
7 List/RWSLT 5e6

純粋な計算をモナド上で行う場合以下のことに注意しましょう。

  • Reader系はオーバーヘッドなし
  • baseやtransformerの多くのモナドは30%~40%のオーバーヘッド
  • extensible-effects、extensible-skeletonは55%のオーバーヘッド
  • List/RWST.Lazyは40倍遅い

オーバーヘッドがあるとはいえ、List/RWSLT以外は最悪でも二倍遅くなる程度なので
ほぼ気にせず使って良さそうです。

SlowFib

slowfib結果

予想どおりインライン展開されたバージョンにくらべて5倍-40倍遅くなりました。
多くのモナドでn=10に比べてn=20,30が顕著に遅くなっていますが、
これはGCによるものだと考えられます。

  • 引数を必要としないモナド（MaybeT/ExceptT/Writer/Eff/EffSkeleton)は5倍程度遅い
  • 引数を必要とするモナド（ReaderT/AccumT/ContT/RWST/SelectT/StateT)は40倍遅い
  • IdentityはなぜかEither等よりも遅くなる

まとめ

今回の結果からモナドを使用する時には以下のことに注意しましょう。

  • 多くのモナドは30-50%程度のオーバーヘッドであり気にせず使って良い。
  • ListやLazy系のモナドではサンクがたまりやすく、非常に低速になることがあるので注意。RWST.CPSやStateT.StrictやWriterT.CPSのStrict系モナドを使いましょう[1]
  • bind演算子がインライン展開されないと5倍から40倍遅くなるため、Monad m制約がつく関数はINLINE(またはINLINABLE)プラグマを指定しましょう。

となります。モナドを選ぶ際の一助になれば幸いです。

ただし、今回の結果はあくまで純粋な計算をモナド上で行った場合の性能評価であることに注意してください。実用的なプログラムではbind演算子よりもそのモナドで行う副作用がボトルネックになることの方が多いでしょう。

次回以降の競技では副作用を起こすプログラムの性能評価を行なっていきます。

なお今回使用したベンチマークは以下のレポジトリから参照できます。

https://github.com/autotaker/benchmark-effect-libraries/tree/a59a9d4d70f9d250b52e77fdcb5236e0bb59705c

脚注

  1. Listモナドは救いようがないです。重い計算に使うべきではありません。 ↩︎

Discussion