ブログやめる日記 このページをアンテナに追加 RSSフィード

プロフィール

tanakmura

ブログをやめるまでの軌跡

0011 | 11 |
2006 | 08 | 09 |
2009 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 |
2011 | 09 |
2012 | 11 | 12 |

2012-12-05 このエントリーを含むブックマーク

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

f:id:tanakmura:20121205020209p:image

左が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 です(宣伝))

2012-11-28 このエントリーを含むブックマーク

つか久々に書いてリファラ見てると、リファラの情報量なくなっててやばい。

http://www.suzukikenichi.com/blog/google-turns-on-ssl-encryption-for-search/

多分一番でかいのは、Googleのが無くなってる点だと思うのだけど、つか検索情報を世界で一番有効活用してるのがGoogleなわけで、通信が暗号化されててもGoogleに見えてたらあんま意味なくねという感が。

あと短縮URLは可及的速やかに滅ぶべき。

2012-11-20 このエントリーを含むブックマーク

うーんいや、なんか単に「整数の足し算すらポリモルフィックな挙動をするHaskellさんひどい」みたいな話の気がしてきたな。型クラスが最内ループに届かなければ(どういう意味?)、Cの自動並列とそれほど変わらない気が。

2012-11-19 続: 副作用の無い関数型言語を使えば並列プログラミングがしやすいと このエントリーを含むブックマーク

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が遅くてイライラするときなんて言って心を鎮めてるの??

iwagiwag 2012/11/19 14:52 > Eclipseが遅くてイライラするときなんて言って心を鎮めてるの??
よし、RAMDISKにソースを置くぞとかですかね、EclipseのキャッシュをRAMDISK上にするのも効果あります。Java が遅いんじゃなくてIOなんで…。
あとjvmのオプションをいじるとかですかね、ヒープサイズをでかくしたりとか。
それをやってもCDTで3万行くらいのCソースを編集するときは、1文字編集するたびに1msくらい固まって発狂しそうになりましたが…。

tanakmuratanakmura 2012/11/19 23:14 > Java が遅いんじゃなくてIOなんで…。
なるほど…

2011-09-01 このエントリーを含むブックマーク

会社の飲み会でここの内容を参考にしたとか言われて非常に申しわけない気分になるなど。

ふざけた文体で書いてた理由の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

かな…