Haskell で高速なプログラムを書くときに注意すること

Haskell は表現力が高いプログラミング言語だが、気をつけないと非効率的なコードが生成されてしまうことがある。では、どういうところに気をつければ高速なコードになるのか。少し調べてみた。

この記事に書くのは、あくまで原則とかそういうやつなので、コンパイラーの最適化（正格性解析、インライン化、自動ボックス化解除）によっては、自前で工夫しても意味がない、つまり、コンパイラーに任せた場合と同じ結果になるかもしれない。どういう場合に早くなるかはケースバイケースなのだ。

ここで扱うトピックは大きく分けると、

正格評価
型クラスの特殊化
Unboxed 値
その他

となる。あくまで自分用の備忘録であり、特に突飛なことを書いているつもりはないので、知ってる人はアーハイハイという感じで読み飛ばしてしまえるだろう。また、筆者の理解が浅く、誤解に基づいたことを書いているかもしれないので、あまり信じすぎないように。

なお、この記事では、 Haskell 処理系として GHC を前提とする。

1. 正格評価

Haskell は遅延評価の言語なので、変数が指すモノとしては「評価済みの値」「まだ評価されていない値(サンク)」の2種類が想定される。変数を使う際にこれをいちいちチェックして、後者なら値を評価して、とやっているとまどろっこしいので、最初から正格評価してしまえば高速化できる可能性がある。

変数の束縛を正格にする

変数に束縛される時点で値を評価してしまえば、参照時にサンクかどうか判断する必要がない。GHC の BangPatterns 拡張を使うと、変数束縛時に ! を書くことによってその束縛を正格に出来る。

モジュールの変数束縛全てを正格にしたい場合、 GHC 8.0 に追加された Strict 拡張が使える。この場合、遅延評価を全く使えなくなるというわけではなく、明示的に ~ を書くことによって束縛を遅延評価にできる。

Bang patterns and Strict Haskell — GHC Users Guide

データ型のフィールドを正格にする

データ型を定義する際、フィールドの型名の前に ! をつけることによってそのフィールドを正格にできる。これは標準の Haskell にある機能である。

例を挙げると、Data.Complex モジュールで定義されている複素数型 Complex a は次のように定義されている。

data Complex a = !a :+ !a

あるモジュールの全てのデータ型のフィールドを正格にしたい場合、 GHC 8.0 で追加された StrictData 拡張を使うことができる。

2. 特殊化する

型クラスは便利だが、型クラスを使って関数を多相化するとコストが発生する可能性がある。実態としては C++ の仮想関数的な感じのはず。

（2019年2月8日更新：「型クラスを使うと関数呼び出しの際にコストが発生する」から「型クラスを使って関数を多相化するとコストが発生する可能性がある」に表現を弱めた。ついでにもう少し書いておくと、「C++ の仮想関数的な感じ」には「C++ の仮想関数は具体的なクラスが判明していれば仮想関数テーブルを経由せずに呼び出すような最適化ができる」ことも暗に含んでいる。というわけで型クラスの場合も具体的なインスタンスが判明していれば辞書を経由せずに呼び出す最適化が可能である。）

例えば、今まで具体的な Int や Double を使って

squareInt :: Int -> Int
squareInt x = x * x

squareDouble :: Double -> Double
squareDouble x = x * x

と定義していた関数を、 Num a に変えて

square :: Num a => a -> a
square x = x * x

に変えると遅くなる可能性がある、ということである。（インライン化された場合は多分遅くならないと思う）

型クラスを使う場合に特殊化しておくと、型クラスの関数を呼び出す際のコストが発生しないバージョンが作られるので、「型クラスによって一般的な関数を書きつつ、具体的な型の場合は効率的な実装が使われるようになる」ということが可能になる。抽象化と効率の両方を求める場合に、特殊化は強力な武器となりうる。

SPECIALIZE pragma — GHC Users Guide

関連： INLINABLE pragma : 関数を INLINABLE にしておくと、その関数に対する SPECIALIZE pragma を別のモジュールに書けるようになる。

3. Unboxed 値

Haskell における通常の値は、「ボックス化」されている。値をボックス化すると、どんな型の値でも扱える多相関数を実現できたり、実際の値の代わりに「未評価の値（サンク）」を持てたりして、都合がいい。しかし、値をボックス化すると、ボックス化しない場合と比べて余計にメモリを消費するので、効率的なプログラムという観点からはあまりよろしくない。

幸い、 Haskell (GHC) にも unboxed 値を扱う手段は存在する。ただし、ボックス化によって実現していた多相性や遅延評価は捨てなければならない。遅延評価はともかく、多相性を失うのはなかなか辛い。

Unboxed Array

Haskell には Data.Array モジュールに配列を表すデータ型が用意されている。この Array 型は、多相的に定義されている以上、もちろんそれぞれの要素がボックス化されている。

しかし、具体的な Int 型や Double 型の配列が欲しい、という場合には、 unboxed 配列というものを使うことができる。配列としての操作は、 (!) などをそのまま使える。

Array 型に対応する unboxed 配列は Data.Array.Unboxed の UArray 型である。

注意点として、 unboxed 配列の要素の型に関する一般的な関数は書けない。例えば、

firstElement :: Ix i => UArray i e -> e
firstElement a = a ! fst (bounds a)

という関数は型エラーになる（UArray じゃなくて Array なら問題なく通る）。UArray を使うときは、必ず、要素の型が具体的になるようにしよう。

（ただし、同じ関数でも、「さらに一般化」して firstElement :: (IArray a e, Ix i) => a i e -> e のように型を定義してやれば上手く型がつく。IArray は Array i e や UArray i Int などをインスタンスに持つ型クラスである。）

変更可能な配列 IOArray, STArray に対応する IOUArray, STUArray もある。

【2018年2月23日補足】Data.Vector にも unboxed 版がある。

UNPACK プラグマ

データ型を定義する際に、フィールドに UNPACK プラグマをつけると、 unboxed 値を保持してくれるようになる。

data Foo = Foo {-# UNPACK #-} !Double

注意点として、多相的なフィールドに対しては使えない。つまり、

data Foo' a = Foo' {-# UNPACK #-} !a

とは書けない。先ほど Data.Complex の例を見たが、 Complex a の実部と虚部に対して UNPACK プラグマをつけることはできない。自分で

data ComplexDouble = MkComplexDouble {-# UNPACK #-} !Double {-# UNPACK #-} !Double

というデータ型を定義すれば実部と虚部を unboxed 値で保持することは可能である。

ちなみに、具体的な型に strictness flag ! をつけておくとコンパイラが勝手に UNPACK してくれる場合もあるようである。

UNPACK pragma — GHC Users Guide

Unboxed 型（諸々の名前が `#` で終わるやつ）

配列とかデータ型に格納するモノを unboxed 値にするのは分かったが、 unboxed 値を直接触る事は出来ないのか、ということで、 GHC には unboxed 値を直接触る手段が用意されている。

慣例として、これらの unboxed 型や変数の名前の最後には # をつけるようである。通常は型名や変数名に # は使えないが、 MagicHash 拡張を使うと、名前の最後に # を使えるようになる。

Unboxed types and primitive operations — GHC Users Guide

注意点として、 unboxed 型である以上多相性とかそういうのは一切ない。例えば Int# 同士を足したいと思った時に普通の (+) :: Num a => a -> a -> a は使えず、型ごとに別の名前がついた演算子・関数を使わないければならない。Int# 同士の足し算なら (+#) :: Int# -> Int# -> Int# を使い、Double# なら (+##) :: Double# -> Double# -> Double# を使う。 Word# なら plusWord# :: Word# -> Word# -> Word# となる。Int# 型のリテラルは 1 ではなく 1# と書くし、Double# 型のリテラルは 1# とは書けず 1.0## と書く。

整数の足し算と浮動小数点数の足し算に別の演算子を使うのが嫌だから他のメジャーな関数型言語ではなく Haskell を選んだのに〜〜〜という人には残念だが、 unboxed 型を使う上でこれはやむをえない。

【2018年2月23日追記】最近の GHC で導入された levity polymorphism によって、 unboxed な型に対する多相性をある程度回復できるようだ。参考：Levity polymorphismについて軽く – Qiita

Unboxed 型を使わなくても、数値計算等の場面ではコンパイラが適当に最適化してボックス化を解除してくれる可能性は十分にあるので、そういう場面ではわざわざ unboxed 型を使ってコードを # まみれにするよりは、コンパイラの最適化に期待した方が良いと思われる。

Unboxed 型およびその演算は GHC.Prim モジュールで定義されている。また、標準の Int 等と unboxed 型（Int# 等）を相互変換する時は、 GHC.Types モジュールを import する。GHC.Types モジュールでは Int 等の型が

data Int = I# Int#

という風に定義されているので、型コンストラクター I# を介して boxed 型と unboxed 型を相互変換できる。

4. その他

配列のアクセス時に unsafe 系関数を使って添字チェックを省略する

Array や IOArray などの配列に (!) や readArray でアクセスする場合、添字の範囲チェックが行われる。速度が重要な場面でこのチェックを省きたい場合、 unsafeAt や unsafeRead などの関数を使ってアクセスすると良い。（C++ の std::vector に対して operator[] を使うか at() を使うか、というような違い）

(!) や readArray で使う添字の型は Ix クラスのインスタンスだったが、 unsafeAt や unsafeRead で使う添字の型は Int で固定である。Int による添字は 0 始まりである。

インライン化

INLINE and NOINLINE pragmas — GHC Users Guide

INLINE プラグマを使うことにより、関数をインライン化するようにコンパイラーに指示できる。ただ、小さい関数であれば指示しなくても割と自動的にインライン化してくれるっぽいので、自分で指定することにどれくらい意味があるのかよく分からない。

リライト

Rewrite rules — GHC Users Guide

アジカンの曲ではない。

これはどちらかというとライブラリを書く側向けの機能だと思われる。プログラム中に特定のパターンが出現した場合に、より効率的なコードに置き換えることができる。

例えば、 map f (map g [1..]) と map (f . g) [1..] という式は等価だが、素朴に考えると前者は計算の途中に map g [1..] というリストを作るのに対し、後者はそういうリストは作らない。そこで、プログラム中に前者の形の式が現れたら自動で後者に書き換えてしまおう、という最適化が考えられる。この種類の書き換えの規則を定義できるのが rewrite rule である。

IORef/STRef vs State monad (7月17日追記)

変更可能な状態を持つのに IORef や STRef は便利だが、これらに格納される値はボックス化される。ということは、 C などの言語における変更可能なローカル変数に相当するものを実現するのに IORef/STRef を使うと、ボックス化に伴うメモリ確保等が起こって、思ったほどの効率が出ない可能性がある。

これを回避するには、 IORef/STRef を使うのをやめて、状態を関数の引数で持って回れば良い。手で書くのが煩雑なら、 State monad (IO や ST と組み合わせたいなら StateT monad transformer) を使えば良い。いずれにせよ、コンパイラーが十分に賢ければ Int などを unbox してくれて高速化される可能性がある。

【2018年2月23日追記】Qiita に詳しく書いた：関数内ローカル変数に IORef を使うな – Qiita

雑感

Haskell の型クラスが boxed な型しか扱えないのに対し、 C++ のテンプレートは unboxed かつ多相というのを容易に実現できてしまうので C++ はすごい。C++ に型クラスがあったら最強だったと思われる。（Rust はこれらの良いとこ取りをできるようなので Rust に興味はあるのだが、まだ Rust でバリバリコードを書きたくなる場面には遭遇していない）

Haskell でプログラムを書いている時に、パフォーマンスが重要な部分でいろんな手段をとって高速化するのは良い。しかし、パフォーマンスがそれほど重要でない部分にここに書いたような高速化テクニックを使うべきかどうか、判断に迷う。（ここに書いたようなテクニックを多用すると、どうしてもソースコードが「うるさく」なるので）

【2018年2月23日追記】Haskell Wiki にも “Performance” に関する項目がある： https://wiki.haskell.org/Performance

【2019年7月24日追記】2016年に「Haskell High Performance Programming」という書籍が出版されている。この話題についてまとまったものが読みたければ目を通すと良いだろう：

Samuli Thomasson, Haskell High Performance Programming, Packt

雑記帳

人生やっていき