6.2. より速く: 高速に動作するプログラムを作る

あなたのHaskellプログラムを速くするのにあたって、鍵となる道具はGHCのプロファイル機能である。これは別途第5章. プロファイルを取るで説明されている。プログラムが時間/空間をどこで使っているのかについて実際のこと(あなたがどんな風に想像しているかではなくて)を知ることにおいて、プロファイルを取ることに代わるものは存在しない。

もう一つ銘記すべきことだが、プログラムの性能を劇的に向上させるための圧倒的に良い方法は、より良いアルゴリズムを使うことである。プロファイルによってどこが時間を食っているかが分かったら、下に書いてあるもろもろの調整を試みる前に、プログラムについて再考した方が良いだろう。

プログラムを速くするためのもう一つの極めて効率的な方法は、誰か別の人によって真剣に調整されたライブラリコードを使うことである。Data.Listにあるのよりも良いクイックソートを書くことはできるかもしれないが、それはimport Data.Listとタイプするのに比べてずっと大きな時間が掛かるだろう。

GHCでコンパイルされたプログラムが過度に遅いときは、どんなものであれ報告してほしい。近頃は速度に関してGHCにまともな競争相手がいなく、過度に遅いとはどういうことかはっきりしないので、自分の判断を使ってほしい。もちろん、GHCでコンパイルされたプログラムが、同じプログラムをNHCやHugsでコンパイルしたものよりも遅いなら、それは間違いなくバグである。

最適化(-Oまたは-O2を使う)

これはプログラムを速くするにあたって最も基本的な方法である。コンパイル時間は遅くなる。特に-O2のときに顕著である。

現在、-O2は-Oとほとんど区別が付かない。

LLVMを介してコンパイルする

LLVMコード生成器は、ネイティブコード生成器と比べてずっと良いコードを生成することがある。これは普遍的なものではなく、コードに依存する。激しく数値演算するコードは、LLVM経由でコンパイルしたときに最大の改善を見せるようである。また、-optloおよび-optlcフラグを使って特定のフラグをLLVMに渡すのを実験してみることもできる。ただし、これらのフラグを設定するとGHCは通常のフラグをLLVM最適化器とコンパイラに渡さなくなるのに注意。

多重定義関数に気を付けよ

Haskellの(型クラスを使った)多重定義は洗練されているし、趣味が良いし、美点を挙げればきりがないが、これが内側のループに残ったままになると性能には致命的である。これをつぶすには次のような方法がある。

明示的な型シグネチャを与える

シグネチャを書くというのが基本的な技である。そもそも、エクスポートされた最上位の関数に型シグネチャを書くのはソフトウェア工学上の良い習慣である。(ヒント: -fwarn-missing-signaturesを使うと、シグネチャに関して良い習慣を保つのが楽になる)

エクスポートされていない、あるいは局所的に定義された多重定義関数については、自動特殊化(-Oで有効になる)が面倒を見てくれるはずである。

SPECIALIZEプラグマを使う

プログラム中で鍵となる関数について、多重定義を特殊化すると良い。7.18.8. SPECIALIZEプラグマおよび7.18.9. SPECIALIZE instanceプラグマを見よ。

どこに多重定義が隠れているか知る方法

原始的な方法だが、インタフェースファイル上で多重定義された型シグネチャをgrep(検索)すると良い。インタフェースファイルは--show-ifaceオプションで見ることができる。(4.7.7. インタフェースファイルに関連するその他のオプションを見よ)

% ghc --show-iface Foo.hi | egrep '^[a-z].*::.*=>'

正格な関数は心強い味方

であり、特に遅延パターン照合は敵である。

(「正格な関数」とは何かを知らないなら、関数型プログラミングの教科書を参照してほしい。ここで一言二言説明してもあまり役に立たないだろうから)

次のふたつの例を考える。

f (Wibble x y) =  ... # 正格

f arg = let { (Wibble x y) = arg } in ... # lazy

前者の方が良いコードが生成される。

もう少し自然な例として、より正格なコード(目指すべきもの)のためにletの代わりにcaseを使うというのがある。

f (Wibble x y)  # 美しいが、遅い
  = let
        (a1, b1, c1) = unpackFoo x
        (a2, b2, c2) = unpackFoo y
    in ...

f (Wibble x y)  # 醜いが、それで良い
  = case (unpackFoo x) of { (a1, b1, c1) ->
    case (unpackFoo y) of { (a2, b2, c2) ->
    ...
    }}

単一構築子の型はGHCとの相性が良い

関数が、単一構築子の型(ただ一つのデータ構築子を持つ型のこと。例えば、タプルは単一構築子の型である)について正格ならなお良い。

newtypeはdataよりも良い

データ型に構築子が一つしかなく、その構築子にフィールドが一つしかない場合、data宣言ではなくnewtype宣言を使うと良い。newtypeは大抵の場合最適化によって排除される。

関数が正格かどうか知るにはどうしたら良い？

推測しようとしてはいけない。問い合わせるのだ。

インタフェースファイル中でその関数を探し、そのプラグマ中の第三フィールドを探す。__S <strng>となっているはずである。<string>の部分がこの関数の引数の正確性を表している。Lはlazy(良くない)であり、SとEは正格(良い)であり、Pは「プリミティブ」(良い)である。U(...)は正格かつアンパック可能(非常に良い)であり、Aは存在しないこと(非常に良い)を表す。

アンパック可能なU(...)引数については、構成要素の正格性が括弧内に書かれる。つまり、もし引数が二要素のタプルで、U(AU(LSS))と書かれていたなら、これが意味するのは「このタプルの第一要素は使われない。第二要素は再びアンパック可能で、三つの構成要素(第一要素についてはlazy、第二・第三要素については正格)から成っている」ということである。

関数がエクスポートされていないなら、-ddump-simplフラグを追加してコンパイルすれば良い。全ての定義について、型シグネチャの隣に、インタフェースファイルにあるのと全く同じプラグマ情報が表示される。(それから、コア表現は見ていて面白いですよ)

鍵となる関数がINLINE化されるようにする(特にモナド)

頻繁に使われるある種の関数に対してINLINEプラグマを使うことで劇的な効果を期待できることがある。7.18.5.1. INLINEプラグマを見よ。

明示的なエクスポートリスト

モジュールに明示的なエクスポートリストがないと、GHCはモジュール中の全てがエクスポートされていると考えざるを得ない。これは様々な悪影響を引き起こす。例えば、あるコードが実際には(もしかしたら展開の結果)使われていなくても、それはエクスポートされていて、他のモジュールに必要とされているかもしれないので、捨て去ることができない。

GHCは、エクスポートされていないと分かっているコードに対してはかなり攻撃的になることができる。

コアを読もう

(コアとは、GHCがコードを操作する際に用いる形式のこと) -ddump-simpl付きでコンパイルすれば良い。(-Oを付けるのを忘れないように)

プロファイルによってコストの高い関数が見付かったら、その関数のコア形式のコードを見てみると良い。letは良くない。caseは良い。辞書(d.<Class>.<Unique>)は良くない。入れ子になったラムダは良くない。明示的なデータ構築子は良い。プリミティブ演算(eqInt#など)は良い。…

正格性注釈を使え

正格性注釈('!')を構築子フィールドに付けるのにはふたつの利点がある。第一に、プログラムがより正格になるので、正格性解析器のできる仕事が多くなる。第二に、スペースリークを減らすのに役立つことがある。

場合によっては三番目の利点もある。-funbox-strict-fields(4.10.2. -f*: プラットフォーム非依存のフラグ)が使われているとき、正格なフィールドは構築子中にアンパックあるいは非ボックス化され、一つまたは複数の間接参照の階層が取り除かれることがある。アンパックは単一構築子のデータ型にしか作用しない。(Intが良い例である)

-Oなしに-funbox-strict-fieldsを使うのはあまり良い考えではない。発生するパックとアンパックが最適化によって取り除かれないからである。実際、-Oを使っているときでさえ-funbox-strict-fieldsが性能を悪化させることがあり得る。しかしこの可能性は低い。(もし起こったら知らせてほしい)

非ボックス化された型(GHC拡張)を使え

もし本気で速度を望むなら、そして「生の」部分を理解したいと思うなら、7.2.1. 非ボックス化型に非ボックス化型の使いかたの情報がある。

明示的な非ボックス化型に訴える前に、正格な構築子フィールドと-funbox-strict-fieldsを使う(上記参照)のを試した方がいいだろう。この方法なら、コードの可搬性を失わずに済む。

foreign import(GHC拡張)を使って、速いライブラリとリンクする

これは大変だが、それでも、世の中には激しくチューンされたライブラリコードがたくさんあり、正しい道はそれらと競うのではなく、それらとリンクすることである。

第8章. 他言語関数インタフェース(FFI)に他言語関数インタフェースの説明がある。

Floatを使うな

Complexを使うなら、間違いなくComplex Doubleを使うべきであり、Complex Floatを使うべきではない。(前者は大いに特殊化されているが、後者はそうでない)

Float(おそらく32ビット)を使うのは、自分が何をしているか本当に分かっているのでない限り、大抵の場合悪い考えである。Doubleを使うべきだ。速度上の欠点は滅多にない。現代の機械はどちらにも同じ浮動小数点数演算ユニットを使うからだ。Doubleを使えば、数値的な誤差で自分の首を締める可能性がずいぶん少なくなる。

Floatを使うのが良案である場合の一つは、それが大量に必要な場合、例えばFloatの巨大な配列である。これはDoubleの場合と比べて半分の領域しか必要としない。ただし、64ビットの機械ではこれは成り立たない。

非ボックス化配列(UArray)を使え

GHCは、IntやCharなどの基本的な算術要素型に対して、非ボックス化された値を要素に持つ配列をサポートしている。詳細はData.Array.Unboxedライブラリを見よ。これらの配列は、Data.Arrayの標準Haskell98配列よりもずっと速いことが期待できる。

より大きいヒープを使え

プログラムのGC統計情報(-S RTSオプション)がプログラムが多くのGC(例えば実行時間の20%以上)をしていると報告する場合、より多くのメモリを使うことが有効かもしれない。これには、-M<size>または-A<size> RTSオプションを使う。(4.17.3. ガベッジコレクタを制御するためのRTSオプションを見よ)