J

title(J)

links pbbs prog txt all log log2 log3 about

guideline

2008-12-05

_ 告知しろと言われたので(1ヶ月ほど前に)

最近 _

http://d.hatena.ne.jp/w_o/ _

こっちに書いてます _

_

あとこの日記ツールAtomのマシンにしてから初めて動かすのだけど、1.5年分の記録を日記にするのに44秒かかるとか酷い _

2008-09-18

昔書いたコードが読めねー。 _

2008-09-15

_ つつついにやってしもうたよ

今日間違えて会社行った。照明付いてなかったときは何事かと思ったよ。僕としてはあまり一般人の枠から積極的にはみ出たいとは思っていないのでこれはショック。 _

_

生活するうえで祝日を知るしくみが無いので仕方ないとは言えるが。むしろ今まで間違えなかったのが奇跡ともいえる。 _

まあ、今月は今までと違ってちゃんとスケジュール決まってないうえにひとりのプロジェクトやってたから、というのが大きいだろうな。 _

今月はあと来週の火曜日が休みなので注意すること!!!!! _

_ そういえばマザーボードかえた

三週間くらいまえ。なんとなく。LGA775初めて見て感動した。 _

適当に余ったパーツで実家のマシンでもつくるかと思ったがハードル高いな。具体的に言うとOffice。Officeパッケージ版買うとそれだけで安いPCと同じくらいだからなぁ… _

あと実家の人達は _

などやっており、僕よりもマシンパワーを必要としていると言える。なので、Celeron Dがうをんうをん言いながら動いてるのを見るとなんとも言えない気分になる。 _

あと、メーカー製のマシンに付いてくるOEMのWindowsてどのパーツに付いてることになってるのだろうか?マザーボード? _

_ 桜の名所が毛虫の名所に変わるとき

毛虫って誰に許可を得て公道で緑色の物体を吐き出してるわけ?命張ったギャグのつもり? _

_ 昨日の続き

もうちょっと書いておく。 _

つまり、僕としては、「プログラミング言語は実行時の速度を中心にして設計されるべき」と、したい、という話。 _

別にこれは社会的な流行に逆らってやろうという意味を含んでるわけではなくて(含んでるが)、ちゃんとした根拠があって、それは、「パフォーマンスを求めるプログラミングは年々難しくなっていってる」という点だ。 _

かつて、速いプログラムというのは、なるべくサイクルが少なくなるように命令を並べることであった。しかし、CPUがキャッシュを積み、複雑な命令を実装し、並列化され、それがネットワーク上に分散するようになり、「速いプログラム」が満たすべき条件というのははっきりとは決められなくなってきている。 _

ハードウェアの進化のおかげで、大抵の問題は最適化しなくても十分な速度で動くようになってはいるものの、しかし、未だに「速ければ速いほどいいよ」という世界も存在している。ここにふかーい溝があって、今までのプログラミングパラダイムは「ちまい最適化はしなくてもいい問題」のほうにばかり進化してきたので、「速ければ速いほどいいよ」という世界から見た場合にそういったレイヤが全て障害物として立ち塞がるという状況になっている(と思う)。なので基本的に最適化する場合は、抽象化するレイヤなどはなるべく入りこまないようなプログラミングスタイルが好まれる(というか僕が好んでいる)。 _

で、アプリケーションの記述の抽象化、という点で、プログラミング言語ができることは枝葉の部分を除いてもうあまり無いだろうことは、構造化プログラミング、オブジェクト指向、関数型というパラダイムを通じて皆さんご存知のことだろうと思う。結局この部分で重要なことは、「ちゃんとした仕様があること」「その仕様をきれいに設計できてること」で、プログラミング言語ができることは、せいぜい、「設計の部分でなるべく明らかな間違いが入らないこと」ぐらい。 _

(実際には「ライブラリが整備されてること」が最も重要なんだけど…これは面倒なので考えない) _

_

だけど、「実行速度の向上」という点では、プログラミング言語ができることはまだあるだろう、という話だ。例えば、昨日書いた上位レベルでのスケジューリングとか。あと、これからは命令数よりもメモリアクセスの最適化のほうが必要になってくる場面があると予想され、今までの「フラットなメモリ」だけを想定した言語は全て平等に糞になるとも予想できる。そこらへんをどう扱うか、とか考えるほうがドリームがあるだろう、というような。 _

_

つまり、もうしばらくは「どれだけアプリケーションのモデルの抽象をうまく扱えるか」というのは遠慮しようじゃないか、むしろ速度向上を目指そうで!というのが、僕の主張である。 _

_

話がずれてきた & なんか偉そうになってきたので、とりあえずこのへんで終わっておく。(すごく中途半端) _

_

とは言っても、今の時代、パフォーマンスが求められるのは行列の乗算だけである、という点は十分に考えておく必要があり、つまり、僕が作りたいプログラミング言語は行列のかけ算が書けるプログラミング言語だということだったんだね!(←「かける」と「書ける」をかけている(←「かける」と「書ける」と「かける」をかけている(←(ry(←(r(←( _

_ イベント処理とスレッド

あんま考えがまとまってないのでうやむやに書いてたのだけど、ツッコまれたのでもうちょっと書いておく。 _

性能を考えなかった場合、イベントを複数スレッドで処理する、例えば「パケットの到着を待つスレッドをバックグラウンドで動かします」的なアーキテクチャは糞だと思う、というような話。 _

_

ここでは、 _

があって、「ある状態のときにイベントが発生すると、なんか出力して状態遷移する処理」を「イベント処理」としておく。 _

ただのオートマトンのような気がするが、問題をややこしくするために、「大人の事情により、マシンの全状態は曖昧に定義されてるし、イベントは気分によって減ったり増えたりする」と、しておく。 _

_

イベント処理で起こる代表的な問題は次の二点であると思う。 _

  1. 抽象的な状態と実際の状態変数の間で整合性がとれてないタイミングでイベントが発生する
  2. 状態とイベントの全組み合わせが列挙されてない

で、マルチスレッドでイベント処理すると、この問題を大変ややこしくするわけである。 _

_

まず、整合性。 _

抽象的な状態と実際の状態変数の間で整合性がとれてない、というのは、下のコードで、 _

struct {
    int size;  /* サイズ */
    int remain; /* 残り */
    int usage; /* 使用量 */
}buffer;

func () {
    buffer.remain--;
    /* (!) */
    buffer.usage++;
}

(!)で示した箇所のことをいう、としておく。ここでは面倒なので抽象的な状態を定義してないが、大体(size = remain + usage)を満たしてることを仮定して抽象的な状態を定義してる、としておいてほしい。 _

そうすると、この(!)で示した箇所では、実際の状態変数 buffer は抽象的な状態としては無効な状態になっている、とかいうような。 _

_

イベント処理では、この整合性がとれていないタイミングでイベントが発生すると、正しい処理ではなくなる。 _

で、この問題はシングルスレッドの場合とマルチスレッドの場合では都合が違って、マルチスレッドのほうが _

という点で、大変めんどくさい。 _

まず、検証という点、シングルスレッドでは、「整合性がとれてないタイミングでイベント読み出し関数を呼ばない」ことを検証する必要があり、マルチスレッドの場合は「整合性がとれてないタイミングでは状態変数の更新ががアトミックにされていること」を検証する必要がある。 _

さて、ここで大きな違いは、シングルスレッド版は、「うっかり付けてないこと」を検証するのに対し、マルチスレッド版は、「うっかり忘れてないこと」を検証する、という点だ。どちらが大変か、というと、僕の個人的な経験でいうと、後者のほうが大変であると思う。「付けている箇所」を列挙するのは簡単だけど、「忘れている箇所」を列挙するのは簡単ではない。 _

「そんなことはない」という人がいれば、僕はあなたと議論する必要があるように感じる。 _

_

で、ここまで、状態変数の整合性の検証がめんどくさい、という話。次に、状態の列挙の話。 _

_

マルチスレッドによって、プログラムが書きやすくなる、なんていうことはありえない、というようなことが言いたい。 _

(あまり僕の思考としてまとまってないので以下の記述も全然まとまっていない) _

_

まず、重要なのは、「アプリケーションの状態は一箇所にまとまってるべき」という点。アトミックな更新をする、という点でも、状態の検証をやりやすいように、という意味でも、これは重要であると思う。 _

あれ?違うな。言いたいこととしては、 _

Q. マルチスレッドにすると嬉しいのってどんな場面ですか? _

A. そんな場面はありません _

ということなのだけど、なんか色々問題が混ざってるな。なんだ? _

あたり?イベント処理をマルチスレッドでやるのは、ここらの問題をごっちゃにしてしまってるような気がするのだよな。 _

_

ちゃんとまとめるつもりがまとまらなかった。すいません。 _

2008-09-14

またレベル上げゲーをやってしまった… _

レベル上げゲーに近付かない仕組みが必要だよな。というかお金でレベルが買えるゲームとかやるといいのか。 _

_ 並列プログラミングしよう

前から真面目に書こうと思ってたけど、最近真面目にテキスト書く力が衰えてる気がするので、適当に書いとく。 _

ほんとはもうちょっと科学的に書いて会社で使えるようにしたいのだけど、全然科学的じゃないのでここに書いておく。 _

とりあえず思い付きで書いて、あとで真面目な文書にしたいという欲求は若干あるが、それが面倒くさい重力圏を脱出するだけの力があるかどうかは不明(おそらくない) _

(なお、これは僕の個人的な考えであり、会社としてこういう考えが普及してるというようなのではありません。) _

_ マルチスレッドに対する姿勢

まず、僕の中では、「マルチスレッドにするのは性能のため」という考えかたがある。 _

性能向上以外の目的でマルチスレッドにするのは、おそらく間違いである、ということだ。 _

何故か?というと、このテキストは科学的な考察を入れない予定なので、その点についてはうやむやにしておく。 _

一言で言うと、「マルチスレッド化は問題をわかりにくくするから」。イベントの検証漏れなどは、シングルスレッドプログラミングでは、「プログラムが書けない」という問題として現れるが、マルチスレッドプログラミングでは「タイミングの問題」として現れることがある。 _

前者のほうが問題が露見しやすいので前者が問題っぽいけど、実際は後者のほうが根が深いことは考えるまでもなく明らか(考えるまでもなくメソッド) _

後者のほうがライブラリの疎結合的に美しく見えてしまうので、イベントをスレッドで扱うライブラリはいくつかあるが、そのようなライブラリは早くこの世から無くなってほしいと思う。 _

_

…と、なんか長くなりそうだな。このへんの話は本題とあまり関係無いので、別の機会に書く。 _

僕の中では並列、並行プログラミングの目的は、性能向上のためであり、それ以外の目的はない、という点だけ書きたかった。 _

_ 概要

マルチスレッドとか書いてるが、別にマルチスレッドについて書きたいのではない。 _

並列プログラミングというのは、もっと抽象的にできて、例えば、以下のようなものはひとつの考えかたで、抽象化して扱うことができると思う。(実際にはもっとある) _

で、書きたいこととしては、こういうのを一括して扱うにはどういうモデルにすればいいか、という話。 _

_ 全体図

まず、登場人物は、以下のふたり。 _

「スケジューラ」は中心にあるCPUだと考えてもらうとありがたい。「計算ノード」はCPUとは限らないで、たとえば、HDDとかUIの向こうにいる人間なども含む、としておく。 _

なお、「計算ノード」は、「実際に物体があること」が期待される。僕の目的は効率向上なので、「実際に計算する物体が存在するか、しないか」は重要な違いです。また、あとあと書く(かもしれない)計算ノードの特性も実際の物体のそれを正しく表現しているほうがよい。 _

(と、いうのは、「アクターモデルとどう違うの?」と聞かれたときにこう答えるようにしよう、という僕の決意) _

_

一個のスケジューラに複数の計算ノードがぶらさがってるという感じを想像してみてください。 _

_

んで、スケジューラが計算ノードにrequestを投げて、しばらくするとreplyが返ってくるというような感じ。 _

実際にはこれは階層化されてるのだけど、階層化してるのはどう扱ったらいいか考えてないのでそれは保留で。 _

_

これだけだと、よく見かけるメッセージパッシングモデルのような気がしてつまらないので、もうちょっと手を加える。 _

計算ノードは、「request buffer」と「reply buffer」を持つ、というようにする。 _

requestやreplyは直接やりとりするのではなくて、このバッファを介してやりとりする。 _

_

request buffer と reply buffer は直接的なデータ構造ではないかもしれない。 _

例えば、CPUに対して命令を投げる場合を考えると、それはコンパイラ中にあるグラフ構造、ということになるし、人間に対して画面表示を出す場合を考えると、画面の状態がこの「request buffer」ということになる。(あと、音声も含まれるかもしれない) _

_

で、request bufferとreply bufferは、「容量」という特性を持つ。 _

この「容量」は、そのまま、requestやreplyを入れておける数のことを示す。 _

_

全体図としてはこのくらいか。と、いうのも、図を描くのが面倒になってきたからだ。 _

_

さて、このようなモデルを考えると、「並列化したときの最適なスケジューリング」と、いうのは以下の制約をなるべく満たすようにしよう、という努力である、と見做すことができる _

  1. 各計算ノードに付いてる request buffer をなるべくからっぽにしないようにする
  2. 各計算ノードに付いてる request buffer, response buffer はなるべく満杯にならないようにする

まず、(1)は、暇な計算ノードを作らない、という意味。で、(2)は、リソース不足で効率悪くなるのを防ぐ、という意味。 _

_

さて、このようなモデルを考えた場合、何が嬉しいのかというと…何が嬉しいのだろうか。書いててわからんな。 _

でも経験的に言って、こういうように考えると嬉しい場面は確かにあるので…えーと。また気が向いたら続きを書く。 _

_

実際には以下のパラメータがあって、 _

そういううにょうにょを満たす必要があるのだけど、そういうの教科書にのってそうなので、ここでは書かない。 _

_ で、何が言いたいかというと

並列プログラミングのためのプログラミング言語というのは、ここらへんをうまくやってくれる言語である、と思うのだよな。 _

C言語とそのコンパイラがやった仕事のひとつに、CPUという小さな世界でスケジューリングをうまくやった、というのがあるはず。 _

これと同じことをもっと上のレベルでもやれば、それで「並列プログラミングのためのプログラミング言語」になれると思う、という話で。 _

_

たとえば、ここにA、Bというタスクがあって、それぞれ、「(1)ファイルからread(2)計算(3)結果をwrite」を1000回くりかえすというタスクだとする。 _

並列の世界では、これの最適なコードは、 _

read start A
read start B
read start A
read start B
read wait  A
calc start A
read wait  B
calc start B
loop 498 
  write A
  write B
  read start A
  read start B
  read wait A
  read wait B
  calc start A
  calc start B
  ...
end loop
calc wait A
calc wait B
write A
write B

途中で面倒になって適当になってるが、大体こんな感じになる。こんなコード誰が書きたいと思うだろうか。僕が思う。さらに、これを書いたうえで、A、Bのデータ入出力量、計算時間などのパラメータによってアーキテクチャごとにスケジューリングを変えないといけないというオマケ付きである。 _

ふつうは↓こう書きたいはず。 _

func A
   read A
   calc A
   write A

func B
   read B
   calc B
   write B

loop 1000
  A()
  B()

で、ここで、 _

ぐらいわかれば、下の簡単なコードから上のよくわからんコードを生成するのは不可能ではないはず(多分)。 _

_

さらに、プログラミング言語にread,write,calcのレイテンシやマシンのリソースを表現するだけの機能があれば、「CPUが一個しかない場合はシングルスレッドコードを生成する」「タスクAのcalcの中に計算レイテンシが長い部分があれば、その途中にタスクBのcalcを入れてレイテンシを隠蔽する」とかのようなことも不可能ではないと思う。 _

_

で、で、で、ここから先は考えてないので終了。 _