まず、スクリプト言語におけるGCの要求を復習すると以下の通り。
1. 拡張ライブラリが書きやすい(明示的なprotectが不要) 2. 移植性が(そこそこ)高い 3. native threadと相性が良い 4. さまざまな状況でも落ちない 5. 普段の性能を維持しつつ、大量のlive objectに対応できる
Rubyの採用しているconservative mark and sweep手法は、1,2,4はクリアしているが、3,5が苦手。 以前にも書いたようにpthreadはスタックアドレスを得るAPIがないので、 conservativeの特徴であるCスタックのスキャンができない。 また、生きているオブジェクトを全部スキャンするのでlive objectが多くなると極端に遅くなる可能性がある。
一方、PerlやPythonの使っているreference count手法は、2,4,5をクリアしている。 一般的にreference countは応答性がよく、 特にオブジェクトが参照されなくなった時にすぐに解放されるのでlive objectが増えても問題は発生しない。 しかし、代入が発生するたびに参照数(reference count)を増減させる必要があるため、 拡張ライブラリのメモリ管理が面倒だ。また、参照数管理を間違えると面倒なバグの原因になる。 代入のたびの参照数管理はトータルの性能低下の原因になる。 特にthread環境下ではあらゆる代入のためにmutex_lockが必要になるので、 性能上の問題が発生する可能性がある。
それと、reference countにはサイクル(間接的に自分を参照すること)が発生すると、 誰からも参照されなくなってもオブジェクトが解放されないという欠点があるので、 多くの処理系ではmark and sweepのようなスキャンを行う他のGC手法と組み合わされている。
こういうのを見ていると結局、大量オブジェクト対策とthread対応が大きな課題であることがわかる。
大量オブジェクト対策としては、generational GC(世代別GC)が有名だ。 これは、ほとんどのオブジェクトの寿命は短いが、 中には長く生き残るオブジェクトがいて、そういうオブジェクトはあまり変化しないという性質を利用している。 新しく作られたオブジェクトは「若い世代」として頻繁にスキャンされ、 長く生き残ったオブジェクトは「殿堂入り」してたまにしかスキャンしない。 これで無駄なスキャンによる性能低下を避けることができる。
thread対応は難しい。CスタックをスキャンするconservativeなGCでpthreadにうまく対応した手法はあまりないからだ。
QSchemeというScheme処理系とBoehm GCはスレッド対応として
という方法を使っている。しかし、pthreadとシグナルは鬼門で移植性に問題がある(Boehm GCはプラットフォームごとにスレッド対応のコードを持つ、QSchemeはLinuxのみ対応)。
スレッド対応で移植性のある唯一のGC手法はKSMというScheme処理系で採用されているものだ。 これは「ある関数内で生成されたオブジェクトはregistryと呼ばれるスレッドごとのテーブルに登録され、スキャンの対象になる」というルールによって実現されている。まあ、確かにこの方法ならまだ参照されている可能性のあるオブジェクトを解放してしまうことはないわな。
だが、これはあまりにも「保守的」すぎて、関数の実行が終了しない限り、 参照されなくなったオブジェクトも後生大事にとっておくので性能上の問題がある。 ある関数の中で大量のオブジェクトを作って捨てて、としているとあっという間にメモリを使い切ってしまう。 が、発想としては面白い。
で、これらを組み合わせて理想の技法を作り出そうというわけだ(まだ引っ張るらしい)。
追記
「pthread_attr_setstackaddrで事前にスレッド用のスタックを用意しとくのでは駄目なんですか」という質問がありました。
完全に駄目というわけではないのですが、
などの理由で、満足できてません。
Curlの採用事例が増えている、とのこと。
難しい言語ビジネスの中、成功事例になってくれるのを期待している。 まあ、マーケティングから出てくる言葉をうのみにはできないんだけど。
些細な一言が結構な影響を与えたような気がしないでもない今回の特許騒動だが、 後片づけとしていくつかのリンクを紹介しておく。
<URL:http://d.hatena.ne.jp/shiranui/20050204#p1>
shiranuiさんによる解説。知財部にお勤めなのかな。
<URL:http://d.hatena.ne.jp/atsushieno/20050204#p1>
atsushienoさんによる知財法の改正案。私もこれくらいが妥当だと思う。 ベルヌ条約は廃棄だ(とかいうわけにはいかないんだろうな)。
<URL:http://benli.cocolog-nifty.com/benli/2005/02/post_1.html>
権利者商品と侵害商品との間に代替性がない場合、侵害商品の製造・販売を差し止めても、 権利者の利益を増大させることに直接繋がらない、との指摘。 侵害品の製造・販売等を差し止めることが権利者に経済的なメリットをあまりもたらさない場合に、 差止め請求を棄却する権限を裁判官に与える方向で法改正を行うことこそが望まれるのではないか、とのこと。 まったくだ。
<URL:http://d.hatena.ne.jp/shiomaneki/20050203/p1>
Macにはすでにこの種のヘルプがあったので、 1989年当時でも公知であった可能性の提示。
議論が深まることそのものは良いことだ。
今日で末の娘が産まれて100日だ。 で、食べ物に困らないようにとの願いを込めて、 鯛を用意した。
鯛の身とご飯を口に当ててやる。 あと、桃果汁を飲ましてやる。
別にこれで違いが出ると思ってるわけではないんだが、ノリだよね。
のどかな日曜日。聖餐会ではいろいろな人の経験をうかがった。知らなかったけどびっくりするような経験をしている人とか、ちょっといい話とか。
私も最後に短い証詞をした。
そういえば今月は話者が全員男性だったな。
プログラミング言語は新たな問題を解決するために誕生した。 というか、問題を解決しない言語は生き残れない。 その視点は鋭い。
で、Rubyに対して「Perl is a kludge, and Lisp syntax is scary」(Perlはその場しのぎだし、Lispの文法はおっかない)という観察もまた鋭い。
っていうか、Paul GrahamはRubyの仕様だけ見て、 私のLispへの傾倒と、その一部(S式とかマクロとか)の忌避に気づいたのかしら。 そのことについて彼と話したことはないはずだけど。
だとしたら、たいしたもんだ。
弾さんによる増補もある。
ちょっと新しい視点からの継続入門。
でも、なんか途中からわかんなくなっちゃうんだよなあ。 部分継続にいたってはサッパリ。
CPSそのものに対する理解の不足かしら。
高橋(Maki)さんによる:=オペレータへの反対意見。
まあ、わからないでもない。一応反論しておく。
社長と一緒に出雲空港へ行き、 一緒に伊丹に移動。これから長期出張だ。
伊丹からバスで関空。思ったより遠い。 どうせなら大阪の空港は関空で一本化して、 ハブ空港にしてくれたら、いろいろと便利なのに。 東京が羽田と成田でめちゃ遠いのにあきたらず 大阪まで国内空港と国際空港がこれだけ離れているというのは どういうことかと。
その後、井上社長のチケットでラウンジで過ごした後、 UAでサンフランシスコへ。
機内では『守護神』を見た。 面白くなかったとまでは言わないが、ちょっとベタな展開。 おまけに数日前にラジオで浜村淳がしゃべっていた内容そのまんま。 「ここからは言えない」、「あとは劇場で」とか言ってたけど、 結局全部しゃべってるじゃないか、あのヒトは。
我々関空勢と成田、セントレア組と合わせると 総勢18名にもおよぶ視察団。多いぞ。
サンフランシスコ空港はいままでトランジットで何度も使ったことがあるが (パスポートでスタンプ数えたら４回目だった)、 降りるのは初めて。
空港でガイドの人に連れられて市内観光。 着いて早々引き回されるのは時差ボケの解消のためだろうか。
空港から市内、ツイン・ピークスから市街を眺める。 口数の多いガイドさんによると
ふぅん。
ゴールデンゲートブリッジ。 テレビで見るのとまったく同じだが、 昭和１２年完成とは知らなかった。 うちの親父と同い年じゃん。
アルカトラズが遠くに見える。
その後、フィッシャーマンズワーフに移動。 昼食はカニ。カニはここの名物なんだってさ。 (近所の温泉宿で喰わせるような)日本的なカニよりも ずいぶん身が詰まっている。しかも、でかい。 カニまでアメリカンサイズである。
食事後、おみやげを買ったり、 (野生の)アシカを眺めたりする。
ホテルに移動。宿泊先は Crowne Plaza Union Square。 移動途中のチャイナタウンとか面白かった。 なぜかみんなピンクのプラスチックバッグ抱えてたりするのも。
インターネット接続が高い。 １日１０ドル。１週間で３５ドル。 アメリカのホテルってどうして無料でネットを提供しないんだろうか。 日本じゃ常識なのにな。
ホテルで、るびまの原稿書き。
で、夕方、みんな揃って夕食へ。 ヒルトンの1階にある日本料理店。 なんで、和食...。
でも、おいしかった。 アメリカの日本料理って言っても馬鹿にできないな。 サイズはアメリカンだけど。
一行は李白(島根のお酒)があったことに感動してた。 その後さらにスシ食いに行った人たちもいたが、 胃袋どうなってるんだろう？
私は帰って原稿書く。
今回はC++だ。最近読んだ『C++の設計と進化』に影響されたことは 言うまでもない。本当はBjarneの直筆サイン付きの原書を読みたいところだが、 ちょっと英文苦手なんで。
機内であらかた書いてたんで、あとは総称型プログラミングのところ。 ちょっと面倒なんで後回し。
Hongli LaiによるMaking Ruby’s garbage collector copy-on-write friendly, part 7にあったパッチをベースにtrunkを変更してみた。
で、このパッチがなにをやっているか、という話。
Rubyが使っているGCは古典的なマーク・アンド・スイープGCで、 基本的アイディアは 「ルート」から再帰的に参照可能なオブジェクトに「生きている」マークを付け、 最終的にマークのついていないオブジェクトは「死んでいる」と見なして回収する、 というものだ。
この「生きているマーク」を付けるという作業がcopy-on-writeと相性が悪い。
最近のほとんどの(全部の？)OSはプロセスのコピー(要するにfork)を 行った場合、仮想記憶上ではメモリ空間をコピーしない。 同じ内容なんだからコピーするのは無駄でしかない。 とはいえ、プロセスの実行に従って、メモリは書き換えられるから 書き換えをOSが検出して書き換えが起きる直前にオンデマンドでそのページをコピーする ことでコピーを最小限にしようという発想だ。
それはいいのだが、これとRubyのGCが組み合わさると せっかくページ共有してコピーを抑制しようとしたのに、 「マークを付ける」ことによってすべてのオブジェクトが書き換わってしまう。 GCが発生した瞬間に結局Rubyのオブジェクトを含む全ページがコピーされてしまう。
そこで、このcopy-on-write friendly patchだ。
マーク・アンド・スイープGCにはオブジェクトごとの「生きているマーク」は必須だが、 そのマーク(フラグ)は必ずしもオブジェクトそのものに埋めこむ必要はない。 「生きているフラグ」を別の領域(ビットマップテーブル)で持ち、 マークによってオブジェクトを書き換えないというのが このcopy-on-write friendly patchの原理だ。 GCによるオブジェクト単位での更新がないので、 forkしても本当に書き換えられなかったページはコピーされないまま共有される。
とりあえず動いているみたい。
「20%性能向上*1」とうたっていたのだが、 手元ではそんなに性能が変化するプログラムはなかった。むしろほんのちょっと遅くなる感じ。 ま、forkとか使ってないから当然といえば当然だろう。 キャッシュがとか思ったけど、考えてみればキャッシュは読み込みに効くので、 書き込みの局所化を発生させる今回のパッチは関係なさそう。
誰かforkとGCの組み合わせが原因で遅くなっていることが観測できるベンチマークとかもってないだろうか。 Ruby単体で動き、Railsとかとの組み合わせでない方がありがたい。
自分で試してみたい人はcow-friendly-gc.diffを どうぞ。
パッチを当てるためには
patch -p1 -lU < cow-friendly-gc.diff
とすると良いだろう。
*1 よく見たらpart6のパッチと比較して、だった
宣伝。
2月23日(土)に鳥取県鳥取市の鳥取環境大学で、 「セキュリティキャンプ・キャラバン with プログラミング -鳥取-」が 開催される。
残念ながら私は参加できないが(ちょうど帰国の日だから)、 斎藤先生や、wakatonoさん、竹迫さんのような有名人も来るし、 時間の都合が付けられる人はぜひ参加すると良いだろう。
ってか、なんで私の都合の悪い日にするかな(苦笑)。
私のエントリから派生していろんな人が自分の思うところの「初心者用言語」について 語っている。しめしめ。
あ、そうそう、そのエントリでひとつだけ訂正。
ここから「初心者向け言語が避けていること」言い替えれば「初心者が苦手なこと」が何であるかだいたいわかる。彼らは「抽象化」が苦手なのだ。
誰も突っ込まなかったのが不思議だけど、「初心者向け言語が避けていること」と 「初心者が苦手なこと」はぜんぜんイコールじゃない。 だから、正確には
のどれかだ。結構重要な違いだよね。
さて、いろんな人が初心者向け言語について書いてくれた中にはやや自虐的なものも見られる。
初心者こそPHPを使うべき - 行き詰まった時の気分転換日記
他の言語なら、きっと物知り顔のベテランが出てきて、あれこれ言うんだろうと思う。PHPはそれがない。だってみんな初心者ですから。
初心者には、枯れて面白みもない言語より、PHPのような激しく変化している言語の方が楽しいと思う。
PHPはそれだけ勉強しないといけない言語、まさに初心者にはもってこい。
最もタフになれる「初心者用言語」は Squeak Smalltalk！ - sumim’s smalltalking-tos
なにもそこまでいじけなくても。PHPもSmalltalkも良い言語ですよ、きっと。
そういえば、どのような言語が初心者にもっとも良いかについて、 私の意見は述べてなかった。 私の意見は、以下の通り。
言語は関係ない
ひとことに初心者といっても玉石混淆なので、なんとも言えない。 学ぶ気のある人なら、PHPから入ってもCから入ってもLispから入っても 抽象化やらオブジェクト指向プログラミングを身につけるだろう。 今３０代、４０代くらいの技術者はほぼ全員BASICとかFORTRANとかCOBOLの ような抽象化機能に欠ける言語から入門してるけど、 だからといってほとんどが抽象化を身につけてないというわけじゃない。
しかし、抽象化機能が強力だったり、使わないとろくにプログラムが書けないような言語で 入門した場合、それを身につけそこなう確率が下がるというメリットがある。 一方、現実に抽象化機能を身につけそこなっている人が数多く観測される以上、 そのような言語での入門手段しかない場合、そのような人が プログラミングそのものからドロップアウトすることになる可能性が高い。
私はそれでもいい(質の悪いプログラムを量産されるよりはマシ)と 思ってるけど、世間的にそれで合意ができるとはちょっと思えないな。
でも、「関係ない」ってのは、ちょっと卑怯な答えだよね。
先日、Microsoftで開催されたLang.NETの 結果を受けて、Ruby.NETの開発が中止されたとのこと。
今後、.NET上のRuby処理系はIronRubyに一本化される方向、らしい。
道本さんによるITPro Expoのまとめ。
どうなんだろうね。私のプログラミング人生における目標はお金持ちになることではないので、 適当な役割分担は適切だと思うし、その立ち位置は関係者にはかなり理解してもらえていると思う。 でないと、路頭に迷うわけだし。