副作用の無い関数型言語を使えば並列プログラミングがしやすいという幻想
誰が言い出したのか知らないが…世の中には関数型言語が並列プログラミングの次世代だとかいう主張を見かけることがある。
間違いとは言えないが、ちょっと誇張しすぎだろ、という話。
まず、最初に、話が混乱しないように、特殊な記法やライブラリを使うことによって並列化するのがいかに退化であるか、という話をしておこう。
「特殊な記法やライブラリを使って並列化」とは、
# なんか適当な言語があるとして… data0 = [4,1,4...] data1 = [1,9,8...] def nanika_operation a b = ... parallel_map data0 data1 nanika_operation # 並列実行DA！
というような書きかたをして並列することを指す。
これは、別に関数型言語を持ち出してこなくても、C/C++にはOpenMPがあるし、標準C++の範囲でもTBBを使えば、おそらく、なんとかなるものである。
「わざわざ並列であることを指示して並列化する」というのは、言語のデザインとしては確実に間違いです。(実際に必要な場面はあるがそれはOpenMP,TBBで良い)
- わざわざ手で書いてるのがダサい
- 並列化が安全ではない処理でも並列化できてしまう
- アーキテクチャにあわせて最適な並列を行う、ということができない
これは確実に退化です。Fortranコンパイラは既にこの先へ行っています。
で、これは本文のテーマではないのでこのへんにしておこう。またそのうち書くかもしれない。あと反論があればすぐに書くよ。
というわけで、ここでのテーマは、補助記法無しで並列化する場合の話。
以下、「自動並列化」というと、「補助記法無しで、普通のコードを自動並列化する場合」のことを指す。
自動並列化、というと、「どのように処理を分散させるか」が問題のように思われるが、実際には、分散させること自体はそれほど問題ではない。
分散させる方法については、既に手法は沢山あるし、どうせ自動で処理するのだから、その手法を全部試して一番速いものを探すとかしてやればよい。
実際に問題になるのは「並列化」ではなく、以下二点である。
- どこを並列化すれば速くなるのかを探す
- 安全に並列化できる場所はどこにあるかを探す
で、僕の主張は、関数型言語はこれら二点を解決してくれるものではない、というものである。
まず、「どこを並列化すれば速くなるのかを探す」という点について。
副作用の有無と、「速くなる場所を探す」というのは、何も関係無い、というのは説明しなくてよいだろう(反論があればぜひ)。
なので、この点については「純粋関数型言語は何の助けにもならない」と言える。
次に「安全に並列化できる場所はどこにあるかを探す」である。これは、実際は、「依存性がどこにあるかを探す」という問題になる。
ここの問題が、「副作用の無い純粋関数型言語は並列化しやすい」というような幻想を生んだ原因だろう、と、僕は推測している。
つまり、「副作用のある言語では、色々なんかごちゃごちゃしてるので、依存性がわかりにくいが、副作用が無いと依存性がわかりやすいので並列化しやすいですよ」、というようなこと。
よく考えると、少しなんか変だということがわかるはず
- 副作用があると色々ごちゃごちゃして依存性がわかりにくい…て、ほんまか
- 副作用が無いと依存性がわかりやすい…て、ほんまか
- 依存性がわかりやすいと並列化しやすい…って実際に依存性があったらどうすんねん
まず、「副作用があると依存性がわかりにくい」と、いうのは、まあ、本当。だが、この点、ローカル変数についてだけ言えば、「SSA解析する」、ということで決着が付いている。問題はポインタやグローバル変数が混ざった場合。
「ポインタやグローバル変数が混ざった場合」、というのは、次の「副作用が無いと依存性がわかりやすい」と関係しているのだが、「副作用が無いと依存性がわかりやすい」というのはちょっと違うだろ、と。
依存性を探すときに面倒な問題として、「関数ポインタ」の存在が挙げられる。
ループ中で関数ポインタ経由の関数呼び出しを行った場合、ループを見ただけではそのループが何をやっているのか定義できない、と、なるのである。安全な解析をする場合、「なんかよくわからないループ」は「危険そうなので並列化しない」という解析結果を出すしかない。
なので、関数ポインタを含むループを並列化する上で、関数ポインタの解析を放棄するわけにはいかない。
で、この「関数ポインタ経由の関数呼び出し」を解析する場合は、ループを含む関数の呼び出しもとまで辿っていって、呼び出しもとごとに解析する「コンテキストセンシティブな解析」とやらをやるのだが、これがかなり処理時間に影響をあたえるので面倒、とかである。
関数型プログラミングをしている場合、後悔関数を使うことはよくあるので、この面倒なコンテキストセンシティブ解析をやらねばなるまい。
で、コンテキストセンシティブな解析を実装したとすると、ポインタ、グローバル変数の問題も、大体解決してしまうのである。(このへんは理解が浅いので間違いかも)
文章が下手すぎるが、まとめると、
副作用のある言語は、ポインタ、グローバル変数の問題を持っているので、副作用が無い言語に比べると並列化しにくい場面というのはある。
だが、副作用がある、ない、に関係無く、もっと面倒な関数ポインタの問題というのがあって、これを解決できるなら、ポインタ、グローバル変数の問題も解決できる。
よって、実際、この「依存性の解析」という点において、「純粋関数型が副作用のある言語に比べて有利である」、とは思えない。
と、いったような感じ。
で、最後の問題「依存性がわかりやすいと並列化しやすい」は、一部論理の飛躍があることがわかるだろう。すなわち、「依存性が無い場合はよいけど、依存性があったらどうすん？」
依存性があった場合にできることは、
- 自動並列化は諦める
- 人類の夢であるアルゴリズム書き換えを行う
のどちらかしかなく、どちらも副作用のある/ない、にはほとんど関係ない。
