ユメのチカラ

Asianux Road Show、まつもとゆきひろさんの講演

Asianux Server 3の出荷を記念して、Asianux Road Showを東京、大阪、福岡で開催する。東京では、Rubyのまつもとさんにご講演をいただく。

なにやら、無理矢理お願いしちゃった感じで恐縮である。

まつもとさんの講演以外にも、わたしも僭越ながらちょびっと登場するし、豪華景品（ものでつるのかよ）があたる、抽選会もあるので奮って参加いただきたい。

エンジニアのためのテクニカルセミナー
2007年10月16日(火)　東京
2007年10月24日(水)　大阪
2007年10月31日(水)　福岡

正直言って、大阪、福岡の集客がまだまだなので、大阪、福岡在住の方は、ぜひご参加いただき、わたしと握手だ。（なお、まつもとさんのご講演は東京のみですので、そこんところはよろしく）

Asianux Road Show
http://www.miraclelinux.com/corp/event_seminar/2007/1016_1031_1.html
Asianux Road Show/東京のご案内。
http://www.miraclelinux.com/corp/event_seminar/2007/1016_1.html

ん？

8月13日より毎日土日も休まず本ブログを書いてきた。下記がこの一月半分のエントリーである。

弊社の他のブログ(ペンギン飼育係が見た、アジアのペンギン、第三のペンギン)はグループで書いているので、話題のバラエティが豊富で結果として新規のお客さんが多い。

一人で書いているとどうしても話題の幅が限られてしまうので、毎日毎日書き続けることと、もう一つしばりを自分に課した。下記のエントリをざっと見ていただけくと、それが何かわかるだろうか(50行後に種あかしする)。

8/13 Asianux Server 3
8/14 イノベーションのジレンマ
8/15 ウィキノミクス
8/16 NHKドラマ「ハゲタカ」
8/17 お休み
8/18 カーネル読書会のおしらせ(第79回)
8/19 北鎌倉
8/20 grubでのエラー
8/21 減量
8/22 コインロッカー・ベイビーズ
8/23 再放送：「ハゲタカ」
8/24 シリコンバレーの思い出
8/25 Suica
8/26 世界陸上
8/27 ソースコードの読み方
8/28 闘うプログラマ
8/29 チューニング
8/30 ツッコミ力
8/31 デバッグ方法論
9/01 図書館
9/02 ナニーニ
9/03 21世紀のプログラムは君たちが作る
9/04 ぬこ
9/05 ネタ切れ
9/06 ノルマ
9/07 ハッカー倫理
9/08 ビル・ゲイツの手紙
9/09 フリーソフトウェアの価値観
9/10 ベストセラーは読まない
9/11 北東アジアOSS推進フォーラム
9/12 Matzとひろゆき
9/13 mixiのスケーラビリティ
9/14 ムリ、ムダ、ムラ
9/15 メモリアクセスは遅い
9/16 Model View Controller
9/17 山勘で分岐先を実行することを投機的実行と呼ぶ
9/18 U-20プログラミング・コンテスト
9/19 よしおか賞とAsianux Server 3出荷記念
9/20 Lightning Talks
9/21 Richard Stallman
9/22 類型化
9/23 Latencyの隠蔽
9/24 ロックのいろは
9/25 wired society
9/26 ヲタクとハッカー
9/27 ん？

ページビューを増すために、土日を含めて毎日更新と、バラエティを増すために(話題が偏りすぎないように)、タイトルをあいうえお順にするしばりを自らに課した(なーんだ)。

そーやって記したエントリについてちょっと分析めいたことをしてみる。

46本のエントリのうち28本にはてなブックマークがついた。

人気のトップ5は
8/27 ソースコードの読み方
8/31 デバッグ方法論
9/15 メモリアクセスは遅い
8/24 シリコンバレーの思い出
9/07 ハッカー倫理

特に「ソースコードの読み方」は500を越えるブックマークがつき、この方面の興味が高いことがうかがえる。

8/28 闘うプログラマ
9/17 山勘で分岐先を実行することを投機的実行と呼ぶ
9/23 Latencyの隠蔽
なども2桁ぶブックマークがついた人気だった。

またプログラミングネタやbinary hack系（「メモリアクセスは遅い」、「山勘で分岐先を実行することを投機的実行と呼ぶ」、「Latencyの隠蔽」、「ロックのいろは」）が根強い人気があった。

あと、「ハッカー倫理」にまつわるお話も人気だった。（「フリーソフトウェアの価値観」、「Richard Stallman」など）

ネタ切れで息切れ感がただよったのが、「ネタ切れ」である。短いエントリは無理矢理書いているものが少なくない。

あいうえお順という縛りがあったのでタイトルに無理があるのも少なくない。ノートに50音表を書いて全体像をあらかじめ描いていたのであるが、ところどころ空白のところがあって、そこを埋めるのが厳しかった。「ぬこ」は「ぬ」ではじまる話題が他に思いつかなかったのが正直なところである。

一方で同じ音でも書きたい事が複数あるのもあった。「Richard Stallman」にするかLinus Torvaldsにするかとか。

よしおかひろたかの「50音ブログ」であったわけであるが、ブックマークもいっぱいついたし、毎日まがりなりにも書き続けることができたわけだし、自分としても、締切におわれる漫画家(？)みたいな感覚を得られたし、なかなか面白い経験であった。

ブログというのは自分のために書いているのだから、自分が楽しめなければいけない。そのために何らかのお題を自分に出して、それをこなしていくというのも意外と楽しい。昔のブログを眺めながらそれをネタにするというのも、自分が気がついていない再発見が結構あって勉強になった。

そんなこんなで、本日、「ん？」でこの実験は一区切りとしたい。

ヲタクとハッカー

時々思うのだが、インテルのマニュアルを意味もなく見ている自分というのは、そーとーやばいと思う。別にインテルのマニュアルを隅から隅まで読んだところで会社の経営にプラスになる何かあるわけではなく仕事に直接関わっているというわけでもないので、趣味といえば趣味であるし、それによって経済的なメリットがあるとか人生が幸せになるとか異性にもてるとかそーゆー事は一切ない。

先日テレビを見ていたら換気扇ヲタクという換気扇の美に魅せられた人たちが出ていた。換気扇を見るといてもたってもいられない性格らしい。まあ、世の中にはいろいろな人がいるわけで人に迷惑をかけていなければとやかく言われる筋合いのものでもない。

インテルのマニュアルを繰り返し読んでいるとコンピュータアーキテクチャの実装上の様々なお話が出てきて勉強になって、いつの日か仕事の役にたつのではないかというスケベ心もなくはないがここ数年インテルのマニュアルが仕事で役にたったというのは数年前未踏ソフトウェアプロジェクトでのhardmeterの実装のときと、このブログでも再三とりあげているCache Pollution Aware Patchを実装したとき位だから、やっぱり趣味の範囲を超えないような気がする。

むしろ、ヘネパタがどーだとかコンピュータアーキテクチャの薀蓄を語るときの貴重なネタ本としての活用の機会のほうが圧倒的に多い。ブログでのネタの提供もとでもある。

はっきり言ってIA-32 Architecture Reference Manual Vol 3については穴の開くほど繰り返し読んで、おそらく私以上にこのマニュアルを読んだ人は日本にはそうはいないだろうという実感はあるのだが、（本当かいな？単に自分が知らないだけだとは思うけど）、カーネル読書会みたいに、そーゆーことを嬉々として語れる場があるというのは、幸せなことかと思う。

ヲタク倫理というのがあるのかないのかは知らないが、どーでもいいことにとことん拘ってそれを極めるというのは日本のヲタクの道みたいな気がするけど、それとハッカーの気質というのはかなり共通点があるような気がする。

シリコンバレーはハッカーと資本主義が微妙なバランスの上で成り立っている世界でもまれな地域かもしれないが（過度な類型化に注意しないといけないと自戒しつつ）、一方で東京だって、どうしてどうしてヲタクが様々な価値を作りつつあるのではないかななどと思ったりするのである。

ニコニコ動画RCが大人気であるが、ぱっとみ、YouTubeのパクリかよと思うけど大間違いで、Flashのハッカーが作った、2chの動画版というコンセプトはYouTubeとはまるで違った地平線を開拓した。

日本のエスタブリッシュメントは2chを決して理解しようとしないし分かるつもりもないと思うが、それと同様にニコニコ動画RCのインパクトを理解しようとしないと思う。（閑話休題）

ニコニコ動画RCはヲタクが社会にインパクトを与えたという例だと思う。その意味でヲタク魂はハッカーと共通のものを持ったような気がする。

日本という地域がナード（コンピュータヲタクというような感じの人たち）の価値を理解しないという梅田望夫の指摘は90年代はそうだったかもしれないが、21世紀になって微妙に変化しつつあるのではないかという予感がしている。（というようなことを言うとまた梅田に怒られちゃうのではあるが、だけどあえて書く。）

シリコンバレーの思い出/ユメのチカラ
http://blog.miraclelinux.com/yume/2007/08/post_dd7a.html

シリコンバレー精神/ユメのチカラ
http://blog.miraclelinux.com/yume/2006/08/post_a196.html

フリーソフトウェアの価値観/ユメのチカラ
http://blog.miraclelinux.com/yume/2007/09/post_0866.html

wired society

3連休でブログネタも尽きたことだしなにを書くかなどと考えていて、趣味のインテルのマニュアルを読んでいたところ、割り込みと例外の章（Intel 64 and IA-32 Architectures Software Developer's Manual Volume 3A: System Programming Guide, Part 1）をたまたまめくっていたのでそれについて書こうかなと思ったのだが、急に気が変わる。

昔ウェブ人間論を読んだ時に書いた感想をたまたま読んで、ああ、インターネットは人々と結線(wired)したのだなあなどと再確認した。http://blog.miraclelinux.com/yume/2006/12/post_2666.html

Wiredという雑誌があったけど（今もあるのかな？）、日本語版も出ていたがいつのまにかになくなってしまった、インターネットは我々を結線したというのが非常にインパクトがある概念だった。

世界がインターネットで繋がっている。

すげーぞ、それはというワクワク感であった。

ハッカーがなぜプログラムを書くかという問いかけに私自身まだ明確な回答は持たない。持たないが、自らの自由意志でプログラムを書く多くのハッカーを知っている。給与を貰うプロのハッカーから100％自由意志で誰からも拘束されないでコードを書くハッカーまで様々な人たちがいることを私は知っている。

なぜハッカーはプログラムを書くのか。

21世紀の謎である。しかし、インターネットのおかげで彼らはインターネットに結集した。インターネットは彼らを結線した。

それによってとてつもない価値の再生産が始まった。

結線された社会はそうでない社会よりも幸せなのか。ハッカーはその社会にどのような役割を演じるのか。

疑問はつきない。









下記はボツにした原稿。もったいないのでそのうち使うかもしれない。

割り込みは現在実行中のプロセスとは独立に発生する。例外は現在のプロセスの実行によって引き起こされる。例えばゼロ除算とかページフォルトとかは例外である。

割り込みも例外も発生するとそれに対応したハンドラを起動し様々な処理を行なう。例外の場合、ゼロ除算とかは当該プロセスに通知して実行を終了するものから、ページフォルトのようにOSによって適切に処理されるものまで様々なものがある。

IA-32の場合は、おなじみの下記のマニュアルの第5章を参照のこと。

Intel 64 and IA-32 Architectures Software Developer's Manual Volume 3A: System Programming Guide, Part 1
http://www.intel.com/products/processor/manuals/index.htm

リアルタイム系OSの場合、割り込み処理を一定時間で処理することを保証しなければいけないのでなかなか大変である。

ロックのいろは

ロックと言うのはプログラミング上のコンベンション、慣用句みたいなもので、共有資源へのアクセスに対する同期のメカニズムとして利用される。

ある共有資源を複数のプロセッサ（あるいはプロセスでもいいけど）から同時に利用したいとする。変数に１を加えるという単純な動作ですら同期をとらないと正しい結果を得られない。

ロックはそのような同期を必要とする場面でよく利用される。ロックを取得したただ一つのプロセスのみその共有資源にアクセスできるようにするのである。

アトミックに値をセットしてテストする命令(test and set)を利用しロックが取得できるまでひたすらループして待つ、いわゆるスピンロックという単純素朴な方法がある。IA-32だとxchgという命令があって、あるメモリとレジスタの値をアトミックに（他のプロセッサに邪魔されることなく）行うことができて、それを利用する。例えば、0がロックされていない状態、１がロックされている状態とすると、下記のコードがそれをナイーブに実装したものである。

Spin_Lock:
Get_Lock:
    MOV EAX, 1;
    XCHG EAX, lockvar; // Try to get lock.
   CMP EAX, 0; // Test if successful.
   JNE Spin_Lock;
//
Critical_Section:
   
   MOV lockvar, 0; // Release lock.

lockvarとEAXレジスタの値を交換して、lockvarの値が0であったら誰もロックを取得していないので下に行く。誰かがロックを取得していたら1が入っているので、Spin_Lockにジャンプして繰り返す。ロックを取得できたら、共有資源にアクセスするなりなんなりをして最後にlockvarに0を代入しロックを解放する。そうすると同じロックを取得するために待っていた誰かがロックを獲得できるようになる。

上記の実装は間違いではないのだけど、実装上性能に多くの問題がある。毎回、xchg命令でメインメモリにアクセスに行くのだがアトミック性を保証するため、つまり値を交換しているとき、他の誰かが別の値に交換しないようにバスをロックし、単一のプロセッサだけが当該メモリにアクセスできるようにする。そうするとxchg命令実行中は他のプロセッサはバスがロックされているのでメインメモリにアクセスできない。プロセッサの数が増えれば増えるほどバスの競合が発生しスケールしない。またメモリアクセスは遅いでも書いたが、メモリアクセスはキャッシュアクセスに比べ100倍は遅いので毎回毎回のたのた動き回ることになる。まあ、スピンロックで持っているわけだから別に他に仕事がないので遅くてもいいっちゃいいのだが、先のバスロックはいただけない。

でもって、通常はどうするかと言うと、もう少しリラックスした方法になる。
先の実装のSpin_LockとGet_Lockの間に下記のコードを埋める。何をしているかというと、cmp命令でlockvarが0かどうか最初にチェックしている。つまり、ロックされているかチェックして、仮にロックされていなかったら、Get_Lockにジャンプしてロックの確保を試みる。

Spin_Lock:
   CMP lockvar, 0 ; // Check if lock is free.
   JE Get_lock
   PAUSE; // Short delay.
   JMP Spin_Lock;
Get_Lock:

cmp命令を実行してから、次のxchg命令まではアトミックではないので、他のプロセッサがその間にロックを取得してしまう可能性があるので、xchg命令で再度ロックが確保できるか確認している。cmp命令でlockvarを確認するのは、それがキャッシュに載っていればキャッシュアクセスなので高速に判定できる。ロックが取得できないときのループもキャッシュへのアクセスを延々と続けるので、メインメモリにアクセスしないので、他のプロセッサの邪魔をしないためスケーラビリティがある。メインメモリへのアクセスは他のプロセッサとの調停が必要なのでプロセッサの数が増えれば増えるほどコストが増大するので、できれば避けたいのある。

またスピンループ中にpause命令を入れているがこれはnopで、プロセッサに対しフルスピードでループしているけど他に有益な仕事があるんだったらそれを先にやってもいいよ、あるいは消費電力を落としてもいいよ、みたいなヒントになっている。IA-32の慣用句である。（蛇足）

スピンロックを実装するときに上記のように二重ループにするのはロックのいろはなのであるが、ユーザーランドで実装するときも注意したい。

また上記のようなアプローチはTest and Test-and-setとしても知られている。

上記の例はIntel 64 and IA-32 Architectures Optimization Reference Manualの8.4.2からの引用である。http://www.intel.com/products/processor/manuals/index.htm

メモリアクセスは遅い/ユメのチカラ
http://blog.miraclelinux.com/yume/2007/09/post_b3bc.html

Latencyの隠蔽

プログラマたるものコンピュータの基礎的な知識は必要だと多くの人は言うのだけど、じゃあどこまでが必須でどこまでがオプション（？）なのかというと明確な線引きがあるわけではない。まあ、Kernelとかコンパイラとかをゴニョゴニョする人はCPUのキャッシュがなんたるかくらいは理解していないといろいろ大変かと思う。

時間と空間を交換するというのはコンピュータだけの世界ではない。街のコンビニだって、店頭に並んでいるものはすぐにアクセスできるけど、店頭にないものはすぐにアクセスできないので、在庫量がある一定水準を下回ったら発注のトリガーがかかる。コンビニはその発注サイクルがデパートとかに比べれば異様に多いので、クロックを上げて性能を出すPentium4みたいなものである。発注単位も非常に小さくて、それこそ弁当一個でも平気で発注しちゃうという感じである。在庫をほとんど持たないので、キャッシュミスした時のペナルティは、そのまま機会損失である。倉庫のようなディスカウントストアもあるが、そちらの発注単位はでかくて、大きな空間が必要なので土地のコストが安い郊外に立地している。

アクセスコストとメモリコストの差に注目して記憶領域を階層化するのは、CPUキャッシュだけではなく、メインメモリとディスクキャッシュなどでも行われている。

CPUのレジスタとメインメモリアクセスの速度は100倍くらい違うので、性能を意識する場合CPUキャッシュがどのようなメカニズムで働いているかを十分理解しないといけない。

メモリアクセスは遅い(ユメのチカラ)で指摘したとおり、メモリアクセスが遅いことを前提にいろいろなチューニング方式が考えられるが、一番単純なのは、プリフェッチである。

順アクセスの場合、次にアクセスされる番地が予想できるので、その番地にあらかじめアクセスしておく。そうすれば実際にそのデータが必要になったときにはキャッシュでのアクセスになるので、メモリアクセスを待つと言うことはない。例えばメモリアクセスに200クロックかかっていて、L1キャッシュのアクセスが2クロックだったとすると、L1キャッシュヒットだと残りの198クロックを無駄に待つ必要がないのでより高速な処理ができる。

あるメモリにどのようにアクセスするかはプログラムを書いた人が知っているはずなので、プログラマが陽にヒントとして与えてもいいし、コンパイラがそれを何らかの方法で認識し、積極的にプリフェッチをかけるというのもある。

最近のプロセッサだとメモリアクセスのパターンを見て、順アクセスを検知すると自動的にプリフェッチをする場合もある。投機的なメモリアクセスである。

あらかじめ準備をしておくというのがlatency隠蔽の基本的な考え方である。

もう一つの方法は、時間がかかる処理と並行して、別の処理を実行するというもので、直列に処理をすすめると、長いlatencyを持つものを待たないといけないので、スループットが上がらない。そこで並列に処理できるものをどんどん処理していくという考え方である。

入出力もlatencyが大きいので、入出力と並行して別の処理をするというものである。

スーパースカラなプロセッサは同時に複数の命令を処理するので、そーやって、スループットを向上させたり、latencyを隠蔽したりする。

Computer Architecture: A Quantitative Approach（David A. Patterson, John L. Hennessy ）を読んで、基本的な概念をおさらいしたいところである。(下記）

機械語ではマシンの挙動は理解できない。(未来のいつか/hyoshiokの日記）
http://d.hatena.ne.jp/hyoshiok/20070916#p1

山勘で分岐先を実行することを投機的実行と呼ぶ（ユメのチカラ）
http://blog.miraclelinux.com/yume/2007/09/post_6814.html

類型化

なんでもかんでも類型化してわかったような気になっているのはちょっと危険である。
「欧米か！」といって突っ込むのはお笑いだけでいい。

欧米では～とか、米国では～とか、シリコンバレーではなんちゃらである、と言うフレーズには騙されないようにしないといけない。

言った本人も言われた人々もその瞬間はなんとなく分かったつもりになっているので注意が必要である。わたしも無意識のうちに「大企業ではＸＸＸですね」（ＸＸＸがいい意味の時もあるし悪い意味もある）とか言っていることがあって、お前は大企業の何を知っているのか、調査研究でもしたのかと自分で自分にツッコミたくなることがある。

飲屋の話題であれば、血液型だろうが、星座であろうが、まあ、なんでもいいのであるが、もう少しじっくり考えなければいけないときは類型化のわなにはまらないようにしないといけない。

旅行で行った土地についての評論家というのはよく見かけるが、そんなものである。

Richard Stallman

Richard Stallmanという人は信念の人である。ソフトウェアは自由であるべきだという強い信念を持ち、それを行動するプログラマとして実装してきた。その行動にぶれはない。驚くほど終始一貫している。

いつのころだったか、よく覚えていないのだが多分1999年か2000年前後の話だと思うのだが、彼がなんかの機会で来日をするという話を聞きつけ、彼に「カーネル読書会」で話しをしてくれないかと直接メールを書いた。

わたしはYLUG（横浜Linux Users Group）というユーザーグループのメンバーでオフラインのミーティングを不定期で開催している。あなたが来日するという話を聞いたので、そのミーティングでお話をいただけないか。

返事は、「YLUGという名前はフェアではない。Yokohama GNU/Linux Users Group という名前であるべきだ。そのような名前に変えるなら話をしてもいいだろう」というものであった。YLUGのメーリングリストで彼の申し出を議論したところ、そこまでして彼に話してもらうこともなかろうということでカーネル読書会でのゲストということにはならなかった。

本日のカーネル読書会はGPL V3についてg新部さんにお話をいただく。

Richard StallmanがいなかったらGPLもフリーソフトウェアもここまで普及することはなかったわけで、まさに孤高のプログラマ、最後のハッカーである。

Lightning Talks

最近のカンファレンスでは、ごくごく軽量のアイデアの発表の場としてLT (Lightning Talks) というセッションがある。

時間はだいたい5分。5分をすぎると強制的に打ち切り。容赦なし。

5分というのは、どーでもいい発表については何十分も聞かされなくていいので、観客に優しい。

5分というのは、これを聞いてくれというエッセンスを凝縮できれば、準備もそんなに大変じゃないので、発表者にも優しい。

エネルギーをそんなに使わないので環境にも優しい（ほんまかいな？）。

5分じゃ何にも伝えられないではないか、と思ったあなたはまだまだ青い。5分で伝わらないアイデアというのは、5時間でも伝わらないのである。自分の思いを5分間でぎゅぎゅっと圧縮できなければ、その程度のアイデアなのである。

最近ではLTが若者の発表の鍛錬、訓練の場になってきていて、どちらかというと一発芸の披露の場という感じがしないでもないが、それはそれでいいと思う。若者だけではなくわたしのようなロートルもどんどんLTで自分のアイデアを熱く語ってみるべきだと思う。5分間一本勝負なので、老いも若きも同じ土俵でアイデア勝負である。

なかなか楽しいではないか。

ライトニングトークスの歴史（懸田剛）
http://giantech.jp/wiki/LTHistoryForEM

ライトニングトークス入門（天野良）
http://mugiwara.jp/ki2/wifky.pl?p=%5BEngineerMind%5D%A5%E9%A5%A4%A5%C8%A5%CB%A5%F3%A5%B0%A5%C8%A1%BC%A5%AF%A5%B9%BF%E5%C0%E8%B0%C6%C6%E2

よしおか賞とAsianux Server 3出荷記念

というわけで、よしおか賞を昨日発表した。
9月18日は記念すべきAsianux Server 3の出荷日でもある。
http://www.miraclelinux.com/products/linux/axs3/campaign.html

ベータテスト参加者を公募してフィードバックをいただくというのは弊社としては初めての企画で、応募いただけるかどうか不安な点も多々あったのだが、無事応募いただいた。ありがとうございます。

賞品につられた(？)という話もなくはないが、わざわざベータ評価をいただきまことにありがとうございました。

一つ一つコメントを読まさせていただいた。開発者一同感謝したい。

選考の方法については上記URLを参照していただくとして、今後ベータテスト等を実施する場合の貴重な経験となった。利用者と一体となったバザール的な開発方法への模索についても今後の課題としたい。

また、Asianux Server 3出荷を記念しAsianux Road Showを開催する。

http://www.miraclelinux.com/corp/event_seminar/2007/1016_1031_1.html

テクニカルセッションも満載なのでお時間のある方は奮って参加いただきたい。

10月16日、東京
10月24日、大阪
10月31日、福岡

U-20プログラミング・コンテスト

今年もU-20プログラミング・コンテストの審査員を勤めさせていただいた。既に経済産業省から個人、団体部門の入賞作が発表されている。（別紙２） http://www.meti.go.jp/press/20070914003/20070914003.html

特に団体部門の最優秀作品の完成度は高く、審査員一同う～んとうなってしまった。

ゲーム関係の作品は正直わたしがゲームをやらないので、作品性とプログラミングからの観点からの評価とが難しいところであるが、どれも力作ぞろいであった。

若者のプログラムを見るのは楽しい。

10月1日の授賞式で再会するのが楽しみである。

U20プロコン最終審査会/Matzにっき
http://www.rubyist.net/~matz/20070901.html#p01

山勘で分岐先を実行することを投機的実行と呼ぶ

「機械語ではマシンの挙動は理解できない」というのをはてなの日記で書いた。この手のbinary hack ネタは意外と受けるということを発見したので「ユメのチカラ」でも取り上げる。

あらかじめ言っておくけど99.9％のプログラマにとって下記のような話を意識しなければいけないというような状況は、まあない。OSやRDBMSあるいはコンパイラの実装者のうちでもごくまれな0.1％の状況で意識しなければならないというようなお話である。

多くの人は知らなくても困らないが知っていても邪魔にはならない知識である。

ハードウェアが機械語を実行するプロセスはごくごく単純化すると下記になる。

• PC（プログラムカウンタ）がさすアドレスにある命令を取り出す（フェッチという）。
• フェッチした命令を解釈する（デコードという）。
• 命令を実行する。
• PCを一つ増やす。（分岐命令ならPCをそのアドレスに書き換える）

命令の実行のステージでも、アドレスおよびレジスタの決定、メモリからの読み込み、レジスタへの書き込み、メモリへの書き込みなど様々な状態が発生する。

フェッチするハードウェアとデコードするハードウェア、実行するハードウェアは、それぞれ別々に実装されているので、同時に実行できる。通常はそれらの処理をパイプラインにして、ある瞬間瞬間では、フェッチ、デコード、実行等等がそれぞれ独立に実行されている。
分岐命令がなければこのパイプラインは乱れることなく、次々と命令をフェッチできる。

ところが分岐命令があると、次にフェッチする命令が、命令を実行した後でないと確定できないので、それを待つ必要がでてくる。通常のプログラムだと数命令に一つくらいは分岐命令なので、そのたびにパイプラインにとまってしまって、はなはだ効率が悪い。（ものの本によるとgccで実行される命令の約17％は分岐命令である）

Pentium 4系のアーキテクチャであると20段のパイプラインなのでナイーブな実装をすると20クロックも分岐先のアドレスを決定するために待たないといけない。

ループを回すなんていうのは、ひたすら分岐しているようなものであるから、これはどうにかしたいと思うのが人情である。ソフトウェアからの解はループアンローリングという力技で、ループをする代わりにひたすら代入文を展開して、どんと実行してしまうのである。分岐する回数が減れば減るほど、分岐時のペナルティが減るということである。

ハードウェアからの解が、分岐予測と投機的な実行である。

分岐予測というのは、分岐先を予測すること（そのまんまの命名だな）、その予測結果でどんどん命令をフェッチしてあらかじめ実行することを投機的実行という。当然予測が外れることもありその場合は実行結果を取り消して再度実行しなければいけないので分岐予測が外れた場合のペナルティは大きい。

さて分岐の予測方法も、アドレスが小さい方に分岐する場合は、分岐すると予測するとかアドレスの大きい方へ分岐するときは分岐しないと予測するというような静的な決めうちの予測もあれば、前回の分岐先を覚えておいて、前回の分岐先へ分岐するというような動的な分岐予測もある。

例えば、ループを百回繰り返す99回は分岐し、最後の一回は分岐しないので分岐予測は99回成功したりするので、静的な分岐予測でも思いのほか上手くいったりするのである。

if文の場合then部分とelse部分ではthenを実行するほうが可能性が高そうなので積極的にそっちを選ぶなんていうことである。

前回分岐した先を覚えておいてそちらに分岐するという方式（動的な分岐予測）でも、実際に実行してみなければどっちに分岐するか分からないという意味で「山勘で分岐先を実行」しているのである。

IA-32 Intel Architecture Software Developer's Manual を紐解いてみると分岐先を記録するメカニズムがある。どっちに分岐したとか、例外、割り込みなどの情報を記録できる。この情報を上手に利用すれば、分岐予測が外れまくっている場所を特定したりすることができる。

またそのメカニズムを利用して実行カバレージを計測するというようなツールもある。（btrax）つまり、あるテストプログラムを実行し、プログラムのどの分岐を通ったかを計測すれば、テストプログラムによって実行されていない場所が発見できるので、その部分を実行するようなテストケースを追加するというような使い方ができるのである。 http://btrax.sourceforge.jp/

命令キャッシュミスが発生しまくっている場所を特定しそれをもとにチューニングするとか、分岐予測が外れまくっている場所を特定しそれをもとにチューニングするとかいう事は言うのは簡単なのだけど実用までにはまだもう少し時間がかかりそうなお話である。（ネタとしてはカーネル読書会でやった命令キャッシュに優しいPostgreSQLの実装というのがある。「第71回カーネル読書会CC-Optimizer: キャッシュを考慮した問合せ最適化器」）

ということでハードウェアの動作を深く理解したうえでのチューニングネタはまだまだ山のようにあるのである。多くのプログラマはふつー意識しなくてもいいことだけどね。

Model View Controller

Smalltalkでの実装が元祖とされているが、データと手続きをつかさどるModel、表示をつかさどるView、ユーザーの入力（イベント）を処理するControllerという要素に分離し設計実装するソフトウェアモデルである。

Web系のアプリケーションの設計では定番のパターン。

正直言うと、そっち方面の経験も土地勘も乏しいので理屈の上ではわかっていても自分の血となり肉となっている感じはしない。

メモリアクセスは遅い

多くのプログラマにとってメモリアクセスの速度を気しなければならない状況というのはめったに無いが、OS、ライブラリ、コンパイラ、RDBMSなどの実装をする時には意識をしなければならない場合がある。

IA-32 Intel Architecture Optimization Reference Manual (order number 248966) をひもとくと6章にOptimizing Cache Usageというのがある。

マイクロベンマークの定番 lmbench http://www.bitmover.com/lmbench/ では、一次キャッシュ(L1)や二次キャッシュ(L2)を測定してくれる。例えば、わたしが利用しているノートだと、L1が1.776nsでL2が5.3490ns、メインメモリアクセスが139.4nsである。

Memory latencies in nanoseconds - smaller is better
    (WARNING - may not be correct, check graphs)
---------------------------------------------------
Host                 OS   Mhz  L1 $   L2 $    Main mem    Guesses
--------- -------------  ---- ----- ------    --------    -------
asianux2. Linux 2.6.9-3  1700 1.776 5.3490  139.4

クロック数でいうと、L1が3クロック、L2が9クロック、メインメモリが237クロックくらいになる。

L1とメインメモリでは2桁のアクセス速度の差がある。CPUのクロックはムーアの法則によって18ヶ月で倍になると言われていたが、その間のメモリ速度の向上は数%で、年々そのギャップは広がる傾向にある。

近年、性能向上のためのクロック数の向上は消費電力の上昇をまねいたため、性能向上のためにはクロック向上ではなくコア数の増加という傾向になりつつある。それにしても、CPUの速度向上にくらべてメモリ速度の向上ペースは低いので、そのギャップの拡大はおわっていない。

昔はCPUのクロックと同じ速度でメモリにアクセスできたが、現状では100倍程度遅いことを覚悟しないといけない。

性能を極限まで追及する時には、そのキャッシュの振舞いを理解する必要がある。リストをたぐるような操作はアドレスが連続していないので最悪毎回キャッシュミスをひきおこし、メインメモリにアクセスする必要が生じる。従って速度が2桁遅くなる。一方配列を順アクセスする場合は最初の一回はキャッシュミスをおこすがその後はキャッシュにデータがあるのでメインメモリにアクセスしなくてすむので高速な実行が可能になる。

リストやハッシュはキャッシュに厳しいが配列はキャッシュに優しい。

リスト処理の場合は次にアクセスするところ(nextポインタの指しているところ)が分るので、あらかじめプリフェッチをしておけばlatencyを隠蔽できる。

Rubyの RejectKaiji2007で発表したRubyのキャッシュミスを削減した話はキャッシュミスをプリフェッチで削減するというアイデアを実装したものである。

RejectKaigi2007
http://blog.miraclelinux.com/yume/2007/06/rejectkaigi2007.html

一方プリフェッチというのは今あるデータを追い出して新しいデータをキャッシュに置くという事であるから、追い出されたデータがすぐに必要になるとキャッシュミスを発生させる場合がある。これをcache pollution(キャシュ汚染)という。ページのスラッシングみたいなものである。なんでもかんでもプリフェッチをしてキャッシュにのせればいいというものでもない。

そのアイデアを元に作ったのがcache pollution aware patchである。

Linux Kernel 2.6.18とCache Pollution Aware Patch
http://blog.miraclelinux.com/yume/2006/09/linux_kernel_26_2c2c.html

CPUのクロック数の上昇は消費電力の増加をまねくのでマルチコア化が進展しているという事は先に記した。マルチコア化が進展するとプロセッサ間の同期をどうとるかがますます重要になってくる。その実装としてスピンロックがある。スピンロックはメインメモリにフラグを用意して、そのフラグをセットできたものがロックを取得でき、セットできなかったものはセットできるまでループで待つという単純な同期方式である。

あるフラグがセットされているかを毎回メインメモリに見にいくという処理は、バスをロックして、アトミックにそのフラグをセットできるかを確認することだから非常にコストがかかる。バスをロックするので他のCPUは別の場所にアクセスしようとしてもアクセクを待たされるのでスケーラビリティもでない。(100nsから200ns位メインメモリアクセスにはコストがかかることを思い出してほしい）

マルチコアになってキャッシュに優しいロック方式あるいはロックなしの同期方法が求められている所以である。

メモリアクセスにまつわるバイナリハックの場所はまだまだいっぱいある。

ムリ、ムダ、ムラ

製造業なんかでは無理（ムリ）、無駄（ムダ）、むらを無くせなんてことがよく言われている。工程を分析して、無理な作業を無くし安全性をたかめたり、無駄な在庫を持たないようにしたり、作業を平準化してむらをなくしたりする。ソフトウェアの開発でも、ムリなスケジュールとか、ムダな作業とか、ムラとかが見られる。

作業を単純化、標準化して無理なくこなせるようにすれば、無駄な作業やむらが減って手戻りも少なくなり品質も向上する。言うのは簡単なのだけど行なうのは難しい。

しかし、プログラマの美徳として言われる楽をするために工夫をするというのは、まさに無理や無駄、むらを無くす作業に他ならない。

mixiのスケーラビリティ

mixiの生みの親“バタラ氏”が語るMySQLの意外な利用法

サービス開始から3年余りで会員数が1000万人を超えたSNSの「mixi」。そのシステムはOSSで構築されており、データベース管理システム（DBMS）には「MySQL」を使う。急増するトラフィックをさばくために負荷分散を重ねた結果、現在ではサーバ1000台以上が連なる超分散システムへ。その中でMySQLが果たす役割とは。http://techtarget.itmedia.co.jp/tt/news/0709/12/news01.html

という記事があった。

日記だけで4億件。サーバは1000台以上。アクティブユーザは6割を超える。すさまじい規模のサービスである。すべてOSSで構成されていて、自社開発のコードでサービスをささえる。

当初一人のユーザから始まったサービスも2ヵ月後には1万人を超え、さらに半年ほどでデータベースをサービスごとに分割（水平分割と呼んでいる）し負荷対策した。しかし1年4ヶ月で100万人を超える会員数の増加は、それだけでは持たず各種IDごとにテーブルを分割している。これを垂直分割と呼んでいるが、DBMS的にはテーブルを水平方向に切っているので水平分割と呼ぶのが正しい。垂直分割というのは通常は列を縦に切ることをいう。例えばあるテーブルに（ID、A、B、C）列があったとして、それをテーブル１（ID、A、B）、テーブル２（ID、C）などと分割することを垂直分割という。

それはさておき、ユメのチカラでもmixiのスケーラビリティは何度か取り上げた。昨年の7月第65回のカーネル読書会でバタラさんに発表してもらったときのレポートである。下記二つをあわせてお読みいただきたい。

５００万倍のスケーラビリティ
http://blog.miraclelinux.com/yume/2006/07/post_7ad0.html

システムを1ユーザから500万ユーザまで約2年半でスケールアップしたというお話で、苦労話満載の非常に興味深いものであった。様様な試行錯誤をへて現在のシステムにいたっているが、1ユーザから500万ものユーザをサポートするなどというスケーラビリティはあらかじめ設計されていたものではない。問題にぶつかるたびに一つ一つ問題を解決していって今に至るということである。この500万倍のスケールアップと言うのは本当にとてつもないことである。そのとてつもないことを飄々とこなしているバタラさんのお話が興味深かった。

LiveJournalのアーキテクチャ
http://blog.miraclelinux.com/yume/2006/07/livejournal_a718.html
こちらはmixiが利用している、mod_perlやmemcachedなどのコンポーネントの話で、それはLiveJournalと同様のアプローチである。

大規模Webサービスを提供するためには、様々なレイヤーでの経験が必要になって、ネットワーク、データベース、OSなどなどどんどん深堀をしていく必要がある。OSSの場合はすべてホワイトボックスなので、やろうと思えばいくらでも深堀をすることができる。それはサービス提供者にとっては価値を生み出す源泉となる。

Matzとひろゆき

ひろゆきは2chの管理人。Rubyの作成者はまつもとゆきひろ（通称Matz）。これはRubyの認定試験で出るそうである。（うそうそ）

昨今のエンタープライズRubyの流れの中でRubyのTシャツ作りなどを担当するRubyアソシエーションが発足したことは非常に喜ばしい。そのRubyアソシエーションがRubyの認定試験を�