■

ちょうどそこそこ参照数稼げたので参考までにどのぐらい情報量無くなってるかというと、

左がhttp://d.hatena.ne.jp/w_o/20121202#1354384823
右がhttp://d.hatena.ne.jp/w_o/20061008#p1


で、赤く示したのが、辿るのが難しいリファラ。(t.coはtwitterの検索に放り込んだら見られるらしいがめんどい + そのうち消えるのやめてほしい)


まあ、twitterの登場によってwebに文章書く人の絶対数は増えたと思うし、人口増えるのは何よりも素晴らしいことだと思うので、一向に構わないし、僕も全然ブログっぽい文書かなくなったのでt.coを作ってる側の人間なんだけど、逆リンクを使ってハンドアックスを投げ合う文化みたいなのはもう失われたと思うと寂しいものがあるね…

(あ、左の上から二番目は意味あるリファラだった http://atnd.org/events/34539 です(宣伝))

■

つか久々に書いてリファラ見てると、リファラの情報量なくなっててやばい。
http://www.suzukikenichi.com/blog/google-turns-on-ssl-encryption-for-search/
多分一番でかいのは、Googleのが無くなってる点だと思うのだけど、つか検索情報を世界で一番有効活用してるのがGoogleなわけで、通信が暗号化されててもGoogleに見えてたらあんま意味なくねという感が。
あと短縮URLは可及的速やかに滅ぶべき。

続: 副作用の無い関数型言語を使えば並列プログラミングがしやすいと

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の中身とか考えないで実行すればよい、とかの話だと思うのだけど(違うかったらすいません)、実際は以下二点の問題から、そんなに簡単にはいかないと思う。

  • 通信時間の問題
  • GHCの実装(STG)の問題


まず、通信時間について。通信時間を考えると、副作用とか関係なく自動並列化はむずいという話。
今の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でしょ」とか書いてあるし、そういうことなんだと思う。


あと、ふたつのスレッドで関数ポインタを書き換えあって実行とか分岐予測イジメすぎである。

まとめ

というような感じで、まあ最初に関数型 de 並列とか最初聞いた時からうさん臭いと思ってたが、調べれば調べるほど無理そうな感じが強くなるばっかりで今ではHaskellのことは全然信用してない。


あとあんま関係無いけど、Haskellの人ってGHCのfasmよりC++で書いたfllvmのほうが性能良い点について聞かれたらなんて言い訳してんの？

あとさらに関係無いけど、Java遅くないって言ってる人って、Eclipseが遅くてイライラするときなんて言って心を鎮めてるの？？

■

会社の飲み会でここの内容を参考にしたとか言われて非常に申しわけない気分になるなど。
ふざけた文体で書いてた理由の1/3ぐらいが「真面目に参考にしようと思って見に来た人をガッカリさせよう」という意図だった…ので、まあ、いんだが、弊社内でそれが実現されるのは想定外…だった。


まあそれはいいとして、 http://d.hatena.ne.jp/w_o/ が、メインだと知らないと言われたので一応書いておくと、主に書いてるのは http://d.hatena.ne.jp/w_o/ です。


ここの内容の続きは書いてないけど…続きについては、かなり心残りがあって、OHCI/EHCI/GPU/HD Audioのうちいくつかは書きたかった。それとACPIちゃんと理解したい。

あと、ちゃんとまとめたい気分は結構ある、ので、誰か本にしたいという人がいれば tanakmura@ gmail.こむ まで連絡ください。
本にならないとしてもまた人生に暇ができたら書きたい。


なお、ここで参照してるファイル類は、infoseekが終了した影響で、 http://int.main.jp/ に移動してます。

最新は
http://int.main.jp/files/qo3-20100112.tar.gz
かな…

■

また起きられなかった。もう二度と酒は飲まない。
まあ、アレだよね…アレ…。酒はコミュニケーション云々とか言う人がいるが、話したいことがあるなら、ホワイトボードある会議室用意して議題を文章に起こしてから話してほしいと思うね…

最近、僕はコミュニケーション能力は「単位時間あたりに情報を転送する能力」ぐらいにしか考えてない気がしてて…まあ、良いんだか悪いんだか…

いや、まあ、アレだよね…アレ…
(TODO:ここに色々なことに対する罵詈雑言を書く)