この記事は注意喚起を目的としており、過激な表題がついている可能性があります。ご了承ください。
手続き型 Haskell と IORef
Haskell には do 記法や Control.Monad の各種関数、そして IORef/STRef という、手続き型プログラミングに適した道具が揃っています。(STRef
も IORef
と同様なので、以下 IORef
のみを扱います)
これらの道具を使うと、例えば次の C プログラム
int someCalculation()
{
int sum = 0;
for (int i = 0; i <= 10000 * 10000; ++i) {
sum += i % 3;
}
return sum;
}
と等価なコードを、 Haskell で次のように書けます(modifyIORef'
によってサンクを潰してやるのが大事なポイントですね!):
someCalculationWithIORef :: IO Int
someCalculationWithIORef = do
sumRef <- newIORef (0 :: Int)
forM_ [0..10000 * 10000] $ \i -> do
modifyIORef' sumRef (+ (i `rem` 3))
readIORef sumRef
…というのは不適切で、そもそも、この場合の sum
(sumRef
) のような関数内ローカル変数に IORef
を使うべきではありません。
IORef
というのは、 C言語で言うところの「ポインターを介した」アクセスとなります(さらに、 Haskell の場合はボックス化のおまけが付きます)。そのため、 IORef
でない通常の変数と比べて、性能が劣る可能性があります。
「Haskell らしい」書き方
いわゆる「Haskell らしい」書き方は、末尾再帰を使った、次のようなコードになるでしょう:
someCalculationWithRec :: IO Int
someCalculationWithRec = return (loop 0 0)
where loop i acc | i > 10000 * 10000 = acc
| otherwise = loop (i+1) (acc + (i `rem` 3))
この程度のコードであれば GHC の最適化によって i
と acc
が正格評価 & unbox 化されることが期待でき1、 C言語での普通のローカル変数を使ったようなアセンブリコードが(たぶん)出力されます。
実際、この「Haskell らしい」コードは IORef を使ったコードよりも速く、筆者の環境では、末尾再帰バージョン (someCalculationWithRec
) は IORef バージョン (someCalculationWithIORef
) のおよそ 1.3 倍の速さでした(後述)。
では、「手続き型の記述をしつつ、(再帰を使った場合と同程度の)最適なパフォーマンスを出す」ことはできないのでしょうか?
できます。 State モナドを使えば。
import Control.Monad.State.Strict
someCalculationWithState :: IO Int
someCalculationWithState = flip evalStateT 0 $ do
forM_ [0..10000 * 10000] $ \i -> do
modify' (+ (i `rem` 3))
get
このコードは GHC の最適化によって、(ループの部分については)末尾再帰を使ったバージョンと同様のアセンブリコードが吐き出されます。
(この場合は Int
を足していくだけなので Sum Int
に対して Writer モナドを使う書き方もできますが、 Writerを使ってはならない ので、 Writer のことは忘れてください。)
この例では変数読み書き以外の処理を行っていないので State
を使いましたが、それ以外の IO
処理が必要な場合は StateT
を使えば良いでしょう。
この例では更新したい変数は1つでしたが、処理の中で複数の変数を更新したい場合もあるかと思います。その場合、状態の型をタプル(または相当のデータ型)にする、 State(T)
をネストする、などの案が考えられますが、どれが良いのかは筆者にはわかりません。(誰か検証して!)
IORef の使い所
IORef の「適切な」使い方としては、
- データ構造の一部が mutable になれるように、データ構造に埋め込む
- unsafePerformIO と組み合わせてグローバル変数を作る
unsafePerformIO と組み合わせて Haskell の型安全性を壊す
などが考えられます。
上記に該当しない場合でも、 IORef
を使った方が見通しが良くなる場合があれば、ケースバイケースで IORef
を使ったら良いでしょう。また、今回は簡単な例だったので IORef
よりも State モナドの方が早くなりましたが、もっと複雑なコードでは違う結果になるかもしれません。
検証用コード
検証用コードを Gist に置いておきました: https://gist.github.com/minoki/9610b1c9113cf3787e221fcce7265f5b
$ git clone https://gist.github.com/9610b1c9113cf3787e221fcce7265f5b.git
$ cd 9610b1c9113cf3787e221fcce7265f5b/
$ stack init
$ stack build
$ .stack-work/install/*/*/*/bin/ioref-test-exe
argument: one of Rec, IORef, IORefLazy, IORefRW, State, StateLazy, Writer, Unboxed
$ time .stack-work/install/*/*/*/bin/ioref-test-exe Rec
100000000
real 0m1.106s
user 0m1.065s
sys 0m0.014s
という風に試せます(筆者の環境では stack exec
経由で実行すると 0.2 秒ほど追加でかかるので、バイナリを直接実行します)。
IORef / 再帰 / State の比較は
$ time .stack-work/install/*/*/*/bin/ioref-test-exe IORef
100000000
real 0m1.486s
user 0m1.451s
sys 0m0.018s
$ time .stack-work/install/*/*/*/bin/ioref-test-exe Rec
100000000
real 0m1.059s
user 0m1.035s
sys 0m0.009s
$ time .stack-work/install/*/*/*/bin/ioref-test-exe State
100000000
real 0m1.125s
user 0m1.087s
sys 0m0.016s
という風になり、再帰と State が同程度で、 IORef が若干遅いという結果が見て取れます。
ちなみに、素直に書いた C++(ほぼC言語)のコードは最適化なしで Haskell の2.5〜3倍の速度でした:
$ clang++ -o test-cpp -std=c++11 test.cpp
$ time ./test-cpp
100000000
real 0m0.388s
user 0m0.375s
sys 0m0.004s
最適化ありの場合は自分で確かめてみてください。C/C++ 処理系の最適化のヤバさが感じられます。
おまけ
効率的に実行される Haskell コードの書き方に関して、以前、筆者のブログに Haskell で高速なプログラムを書くときに注意すること という記事を書きました。興味がある方は見てみると良いかもしれません。
-
もっと複雑なコードで、 GHC の正格性解析に期待できない場合は、 BangPatterns を使って注釈をつける、 Strict 拡張を使うなどの対策をすると良いでしょう。 ↩