続: 副作用の無い関数型言語を使えば並列プログラミングがしやすいと
http://d.hatena.ne.jp/white-azalea/20121027/1351337261
(今気付きました。レスポンス遅くてすいません)
確かに、指摘されてるとおり、もとの僕が書いた文(http://d.hatena.ne.jp/tanakmura/20090429/1240996946)の「依存性の解析が難しい」というのは論理おかしいという気がする。
あと大分前に書いたものなので、今は考えかた変わってる部分もあって、書いた当時の気分で反論書くというのも難しいのだけど、まあ、でも、関数型言語で並列とか1bitも信用してないのは変わってないので、以下、関数型だから並列とか信用しない理由について書く。
(一応本職は最適化みたいなことをやってるので、妄想成分はあまり多くないはず)
そもそも遅いのが並列化して速くなったところで意味があるのか
10倍遅いプログラムが並列化して10倍速くなったところで、その並列化に意味はあるのか。というのが一番の疑問で…
はいはいShootout、Shootout。
http://shootout.alioth.debian.org/u32/benchmark.php?test=all&lang=ghc&lang2=gpp
これについては、
http://shootout.alioth.debian.org/u32/program.php?test=fannkuchredux&lang=ghc&id=3
とかのForeignとかData.ByteArrayおよびあちこちに出てくる '!' について教えてくれたらもう少し真面目に考えるので誰か教えてほしい。(どうやって'!'を入れる適切な位置を見つけるのか?とか)
Haskellの自動並列化は難しい
(Haskell以外に一般に言えるかは不明)
Haskellで並列化とかもう20年くらい(?)言ってるけどなんで実装出ないの?(parとかDPHとかはどうでもいい)
C/C++なら、ほんの一部とはいえ実装されているのに?
実際のところ、今のアーキテクチャ上の今のGHCの実装で動くプログラムを自動で並列化するのは、C言語を自動並列化する以上に相当に難しいと思う。(任意のコア間の通信時間がゼロに近いCPUとかであれば可能な気もするが…)
リンク先の文で、「どこでも並列化すればよろしい。」と書いてあるのは、多分
map f [長いリスト]
とかいうのがあった時、fの中身とか考えないで実行すればよい、とかの話だと思うのだけど(違うかったらすいません)、実際は以下二点の問題から、そんなに簡単にはいかないと思う。
まず、通信時間について。通信時間を考えると、副作用とか関係なく自動並列化はむずいという話。
今のCPUは、コア間通信に500cycleぐらい、OSが介入すると数万clkぐらい必要で、そのコストを償却するには、相当の計算量が必要で、計算量が足りないと遅くなってしまう。
例えば500cycle(=1000命令)程度の関数なら、2コアで実行すると、通信500cycle + 計算250cycle = 750cycleで、ふつうに実行するより遅い。
10コアで処理時間1/9倍とかやろうとすると、オーバーヘッドを1%ぐらいに抑える必要があって、通信500cycleを1%に抑えるには、50000cycleぐらい必要、今のCPUなら1cycle2命令ぐらいなので、10万個程度の命令が無いといけない。そんな大きい処理を抱えた関数はほとんどないと思う。
なので、そのへんを考えると、関数の中身を解析して、実行時間を見積もるのは必須だと思う。
このとき、関数型スタイルで書くのが良くなくて引数で受け取った関数を使う場合、グローバルにコンテキストセンシティブな解析をする必要があるのだけど、これは大変計算量が多い。
(http://www.slideserve.com/alexandria/cloning-based-context-sensitive-pointer-alias-analysis-using-bdds の P11 ぐらい。これの中身は無理という話ではなくてBDD使えばできるよという話だけど…あんまちゃんと読んでない)
コンテキストセンシティビティついては、Cでも同じ問題があるので言語の問題ではないのだけど…ともかく、副作用が無いからと言って、どこでも並列化すればよいというものでもない。
実際には、通信オーバーヘッドを償却できる程度の大きさの関数だけが並列化できる。
とか書くと、これは、今のシングルスレッドを重視してるCPUが悪いとか言う人がいるかもしれんが、そうではないと思う。
今の半導体は、計算自体よりもデータ転送のほうにコストがかかるらしい(http://www.nvidia.com/content/PDF/sc_2010/theater/Dally_SC10.pdf のP37とか)ので、それを踏まえると、外部との通信を減らして、極力コア内にリソースを集中していくようになっているのは、半導体/電荷自体が抱える特性が原因だと思う。
次にGHCの実装の問題。
GHCは遅延評価実現のために、関数ポインタを付けかえたりなんだかんだしてるのだけど、これ実際マルチスレッドと大変相性悪いと思う。
f x = .. なんかxを使う処理 .. g xyzzy = let x = <なんかすごい重い処理> in map f [(f0 x), (f1 x), (f2 x)]
というのがあるとすると。で、この <なんかすごい重い処理> がどこで実行されるかというと…あんまよく理解してないが、まあ、fの中で実行されるとしよう。
この時mapが並列化されていると、 <なんかすごい重い処理> は必要以上に実行される可能性があって、異様に遅くなる可能性がある。
多分、詳細は、
http://www.haskell.org/~simonmar/papers/multiproc.pdf
↑に書いてあると思っていて、まあ、今30秒ぐらい流し読みしただけなので適当なことを書くが、
3.2 A good idea: lock-free thunks
1. ...
2. Many thunks are cheap, so duplicate evaluation often doesn't matter.
「いっぱい実行するしgood ideaでしょ」とか書いてあるし、そういうことなんだと思う。
あと、ふたつのスレッドで関数ポインタを書き換えあって実行とか分岐予測イジメすぎである。