本を読む

読書やコンピュータなどに関するメモ

「Shibuya.lispテクニカルトーク#2」に参加

 Lispコミュニティ「Shibuya.lisp」のテクニカルセミナーイベント「Shibuya.lispテクニカルトーク#2」が開催された。今回も楽しく話を聴けて、感謝。以下、受講メモ。間違いがあったらご指摘ください。

 今回は、前回の藤田さんの講演を受けてか、速度にこだわりのある発表やスピーカーが並んでいたのが印象的だった。LL言語より速くて当然、C++に負けたくない、とかそんな感じ。

開会の挨拶(naoya_t)

 Shibuya.lispの紹介。テクニカルトークのほか、逆引きCL/逆引きScheme/逆引きClosureのWikiなどの活動をしている。また、PerlのCPANのようなR6RSライブラリ集積所「spon」(仮称)を作ろうとしている。Lispの求人情報サイトLispjobs.jp(仮称)も作った。ただしまだ求人はない(笑)

 で、第3回テクニカルトークは7/4の予定(あくまで予定)とか。

Toy to Practical -- Mosh internals(ひげぽん)

 ひげぽんさんが、SchemeインタプリタMoshを、おもちゃのインタプリターから実用的なインタプリターまで改善していったという体験談。Lispインタプリタの実装の重要点を体験から語っていて、面白かった。

 まず、Lisp/Scheme処理系を作ったことがあるかどうか会場に尋ねると、半分ぐらいの人が挙手(笑)。

 IPAの未踏でMoshに応募したときのレベルは、ひげぽんさんいわく「おもちゃ」。SICPを見て作った簡単なインタプリターで、木構造を作って実行するもの。Pure C++で実装。とりあえず動くし、R5RSをほとんどカバーしていたが、とにかく遅い。fib(31)が1分以上かかるもので、実用にたえない。

 遅いとそれだけで使いものにならない、とにかくスピードが必要ということで、問題点をあらいだした。GCが遅い、再帰にネイティブスタックを使っている、環境のlookupが遅い、末尾呼び出しの最適化が不完全、算術計算が遅い、ほとんど最適化していない、など。たとえば、数をいちいちC++のNumberクラスのオブジェクトにしていたため、足し算でもnewしまくったし、それによりGCの遅さも重なった。

 対策として、木構造ベースからVMにしてみた。VMが速いらしいと聞いたぐらいの理由(笑)。有名な論文「The 3imp」を読んで実装した。3impに書かれていないところとしては、多値やトップレベル環境、Subr(外部手続き)、let(論文ではlamdaで代用しているがlet用のフレームを作って処理したほうが速い)、コンパイル時の最適化(Gaucheから借りた)などを実装した。

 このとき、いったんC++をやめてScheme(Gauche)でプロトタイプ「Mini Mosh」を作った。Schemeで作る利点、特にメモリやスタックを間違えてもSEGVしないのを生かして、50回ぐらい作り直した。VMが1400行、コンパイラが2400行。スタックレイアウトのデザインがいちばん大変で、図を書いて整理したり、作り直したり何度もした。

 Mini Moshができたとろで、C++に移植。VMは簡単だったが、コンパイラは大変。そこで、Schemeで書いたコンパイラをMini Moshでコンパイルし、そのコードをC++に1対1で変換するツールを作った。これでMini MoshとC++版で共通に使えるため、デバッグが簡単になったし、Schemeのままコンパイラの開発を進められるようになった。

 GCはBoehm GCを採用して速くなった。また、数値はタグベースのオブジェクトシステムで即値を格納するようにした。この時点でだいぶ速くなった。

 しかし、まだ「実用的」とはいえない。なぜなら、スピード狂の「ひげのお兄さんたち」2人が作った、GaucheとYpsilonがある。この2つが、ベンチマークでCやJavaに次ぐという実績を作り、基準を作った。

 そこでパフォーマンスチューニングのフェーズに。チューニングするうえで、グラフは絶対書いたほうがいい。ゴール(対Gauche、Ypsilon)が明確になるし、それに比較して変更がよかったか悪くなったのかがわかる。さらに、維持しつづけることも重要なため、一発でベンチをとってグラフを作れる仕組みを作り、グラフデータもリビジョン管理した。

 さらにプロファイラを作った。C++のプロファイラだと問題箇所がわからないので自作。mosh -pで呼び出す。LinuxのSIG_PROFから記録している。

 作ってみて気づいたことだが、起動も速い必要がある。PerlやRubyはここが速い。対策として、起動ファイルをあまり読まない、起動時に大きなメモリをアロケートしない(あとで増やす)、C++のstatic initializerを使いすぎない(コンパイラのバイナリフォーマットを決めてC++の配列として読み込むFASL方式)、というのをやった。

 あとは最適化。β変換、手続きのインライン展開(すごく効いた)、定数畳み込み(β変換との組みあわせで効いた)、ピープホール最適化、VMの命令融合、Direct threaded codeなど。

 これでもあの2つに追いつかない。そこで、GaucheやYpsilonのコンパイラが出したコードとひとつづつ比較した。その結果、ベンチマークでGaucheやYpsilonより速くなった(会場拍手)。たぶんいま追い打ちをかけられているところ。

 まとめとしては、実用的なインタプリタへの道は簡単ではなかった。あと、ひげをはやしていると速いコードが書けるらしい(笑)。

  • Q: letフレームの最適化はどこまで
    • A: let相当のlambda式もletフレームに
  • Q: 最後に速くなった要因は
    • Gloc。トップレベルのルックアップをキャッシュする

Common Lisp quote unquote(黒田寿男)

(「ブログでの言及はおひかえください」とのことなので、省略。あれは要約は難しいし)

R6RS Schemeの実装、syntax-caseなどについて(藤田善勝)

 最初にYpsilonの基礎を説明。スループットよりレスポンスを重視と言ってたのは、邪推すると、ひげぽんさんへの牽制かな(笑)。

 前半は、かなりキていた前回の発表の続きとして、メモリスタベーションの対応と「スピンロックに失望」からの話。

 Ypsilonの高速化の結果、メモリスタベーションが起きるようになった。Ypsilonではマルチコアを前提としており、リアルタイムゲームの定石として画面やゲーム本体、通信などのそれぞれをスレッドにして処理する。これにより、メモリ消費は格段に数倍になるため、メモリスタベーションの可能性が上がる。

 プロファイルをとってみると、ミューテックスで回収側とアロケーション側の激しい競合が起きている。そこでスピンロックをためした。システムに制御をうつさず、ユーザースペースで空回りするタイプ。システムコールのオーバーヘッド削減を期待したが、ぜんぜん役に立たなかった(笑)。

 それどころか、明らかに遅くなるテストプログラムがあった。どうも新しいメモリブロックを確保したときにフリーリストを作成するのに時間がかかるらしい。ここで競合は起きないはずだが。

 そこでバスのロックをうたがった。スピンロックは繰り返しコンペア&スワップでバスをロックする。どうやら、x86ではバスをロックすると、すべてのメモリ書き込みが終了するまで次の命令を実行しないようだ。フリーリストの作成には、1000単位の書き込みが発生するため、そこがボトルネックになるらしい。なので、ボトルネックの部分では同期を最小限にした。スイープフェーズで、ミューテーターとアロケーターがハンドシェークしていたが、一方的に依頼するだけにした。

 ここまでやって、paraffinsベンチマークで測定。2コアでCPU利用率190%を達成し、同時にきわめて短いGC時間も達成した。

 会場ではここでベンチマークをデモが実演された。ベンチマークといっても、ゲームでの動作に近い条件にするために、ブロック崩しをオートプレイするというもの。SDLとOpenGLの上で動き、音も出て、Macで600fps、Linuxなら3000fpsという本格的ものだった。

 後半はR6RS対応の話。R6RSの大きな特徴として、ライブラリシステムがある。が、IkarusやLarcenyのcyntax-caseは実装がおかしいと思ったので、自前でsyntax-caseを実装した。そしたらえらい目にあった。実はsyntax-caseって使ったことがなかったのだが、ドキュメントが少ない。さらにportable syntax-caseというデファクトがあり、動作が違うと文句がくるので、動作をみくらべながらバグっぽいところまで合わせた。

 syntax-caseを作ったおかげでシステムの内部をすべて掌握し、コンパイル結果のキャッシュなどもできるようになった。Dead object elimination、つまりプログラムの実行に必要のないオブジェクトを判別して自動的にそれらを解放する機構ができた。コンパイラもマクロ評価器もREPLも解放できる。その結果、lighttpd+fcgiでメモリ使用量を比べて、1.3MBから64KB未満に減った。それによりGCの負担が減ったことも大きい。

 まとめとして、ここまでにかなり時間を使った、と感慨。

私がLispでプログラムを書く理由(和田英一)

 和田英一先生による、エッセイ風の講演。ニコニコと楽しそうに話していた。タイトルを出したあと、「最初に結論を言ってしまうけど、慣れているから、好きだから。どう考えてもこれだから」と(笑)。

 まず有名なコンピュータ科学者たちによるLisへの称賛の言葉を引用。そのあと、自身のLispとの長いつきあいを紹介した。1958年のMcCarthyの論文から、60年に「Lisp 1.5 Programmers Manual」を冬の軽井沢にこもって読んだ話、1964年にIBM計算センターでLispが使えるようになった話、1965年にLisp処理系を開発した話、1973~74にMITでMacLispやFranzLispに触れた話。あと、2000年ごろにSICPの翻訳でSchemeをやった、ALGOL60が好きなのでSchemeも好き、という話(会場限定ネタ)。

 ここでLispの長所と短所の話。ここでは論点より、近山先生の1文字Lisp(carを矢印とか)や、evalquote in simple fortranという論文とかのエピソードが面白かった。あと、いわく「再帰を嫌う人もいるけど、こんなに気持ちがいいものはない」「長所にくらべれば短所はたいしたことではない」と(笑)。

 自身がLispを使う場面として、PostScriptのプログラムを生成するプログラムをLispで書く、と。インタビュー記事にもあった、PSで絵を描くという話で、端末に向かうと「%!」と打つ(笑)。が、PostScriptもいいけど、「似たようなパターンはLispで生成。ホモサピエンスなので」(笑)。

 ほかには、KnuthのTAOCP(The Art of Computer Programming)のアルゴリズムをLispで実装してみて本質をつかむ。ときどきは間違いをみつけて報告したり。

 ここで、正十二面体の絵を描くPSプログラムを生成するSchemeプログラムを紹介した。最初の1点から点と線、面を生成。全体を傾けたり、面の法線を求めて隠面消去したりして描画。「こう話すとなんでもないみたいですけど、試行錯誤して大変」と言ってたけど、いや先生、それじゃ「ボブの絵画教室」です(笑)。

 次に紹介したのが、KunuthのAlgorithm 7.1.2「Find normal lengths」をSchemeで実装する話。元の値から組み合わせをぜんぶ作ってコストを求め、コストごとに何個解があるかを求める。

 次は具体的なネタで、iPod Touch用に作った逆ポーランド電卓プログラム「Happy Hacking Calculator」をiPhone simulatorでデモ。泣く泣くObjective-Cで作ったのだけど、同じことをするプログラムをGauche上でも作った。Gauche版はサブルーチン定義などいろいろできて、いわくチューリングマシンぐらいの機能があるとか。「僕は冬休み中はこればっかりやっていた」と楽しそうに話していた。

 最後に、「Think recursively, write functionally」という言葉とともに、高階関数を使って偶数と奇数を分ける例を示していた。

  • Q: うまくやりかたが浮かばないときは
    • 考えて考えて、だめなときはやめる。気分しだい
    • けっこう電車の中で考えている
  • Q: 十二面体の例のコードで、点の生成が並んでいる箇所は、もうすこし抽象化できないか
    • 僕としては非常にきれいにできていると思う(笑)。解析幾何学の基礎に忠実
  • Q: いままでいちばんおもしろかった機械は
    • もちろんパラメトロン計算機。あれほどおもしろいものはない(笑)

LT:Schemeでbluetoothスタックを書く(奥村ゆうき)

 ここからはライトニングトーク。

 Wiiリモコン震度計をデモ。加速度センサーの値をMoshで読むというもので、通信プロトコルをすべてShemeで実装した。

 問題点として、SchemeのrecordはSchemeの外に持ち出せず、パケットの定義には使えない。そこで、define-packet-typeを定義した。マクロで展開しているが、プリミティブとして提案したい、と。そうすればUSB制御もTCP/IPもぜんぶSchemeでできる、という話。

LT:この木 なんの木 木になるS式 ~FUSEでS式ファイルシステム~(源馬 照明)

 FUSEを使ってディレクトリ構造とS式にマッピングした話。オートデモか動画だかで、次々にディレクトリやファイルを作ってS式になるところをデモしてみせた。同じディレクトリでの順番はnnn%を前置。Gaucheで評価もできる。実装はOCaml FUSEを参考にした。

 FUSEでやるコツとしては、ファイルを仮想的に作るのじゃなくて実際に作るほうが楽、というのと、openとcloseが対応するとはかぎらない、と。

LT:Lisperは怠け者の夢は見ないの?(山下伸夫)

 自動進行するスライドで、関数型プログラミングとLazy Evaluationを解説。関数型プログラミングはつまり、欲しいものをあることにしてとりあえず書くという、夢の記述。これをGaucheでやってみるとうまくいかない。Eager評価しないようにするため、lazySというLazy Evaluationのしくみを実装した。

 例としてエラトステネスのふるいやパスカルの三角形、シェルピンスキギャスケットをデモ。現実を見ろと言われても、夢と現実の区別なんてあったんだ(笑)、と。最後は「遅延評価はtaraiのためにある(わけではない)」。

LT:Cyanの現状と、これから(林 拓人)

 竹内郁雄先生の紹介で話題になった、Cyan言語を作った高校2年生が登場。自己紹介でいわく、言語マニア。

 Cyanは、Lispのエッセンスを多くとりいれた言語。インデントでブロックを表現(HaskellやPythonを意識)し、ブレースをもちいた記述も可能(Rubyを意識)。クラスをもたないオブジェクト指向で、すべてオブジェクトのメッセージ式。予約語が0個。

 S式ではない構文木がファーストクラスのオブジェクトで、Lispと同様のマクロもある。ファーストクラスの継続も持つ。

 ただし、実行が遅く、Hello Wordが4秒かかる(笑)。ちゃんとプログラムを書けるための言語にしたいと思うが、実は言語処理系しか作ったことはなくて(笑)、まず普通のプログラミングの勉強をするので、しばらくCyanは休みということだった。すごいなぁ。

LT:cl-irregsexp - the fastest regular expression library on the planet(John Fremlin)

 高速で理解しやすい正規表現システム「cl-irregsexp」を紹介。S式で正規表現を書く。ほかの言語の正規表現より速いというベンチマークを見せた。

 ただし、名前が問題で、s*xってのはどうかと思うので、名前募集中と(笑)。

LT:流行るLisp用Webフレームワーク(Gauche on Railsから学んだ事)(吉田裕美)

 肩書はGaucheファンクラブで、昨日考えました、と(笑)。

 Gauche on Railsを作った話を紹介。その後、公開したきり(笑)。ただし、Web媒体で記事を書いたらShiroさんなどに指摘をもらって、テンプレートエンジンなどは進化した。

 Railsは、メタプログラミングなどLispの影響のもとにある。次回Gauche.nightでGuche on Rails 2.0を発表したいと思うけど、みんなも自分で作っちゃったほうがいい、勉強にもなる、という話だった。

LT:よりよいLispプログラムを目指して(冬)(yhara)

 いわく「ライフハック」。プレゼンツールは自分の作ったBiwaScheme上のもので、S式で書いている。ほかにも、いろいろな言語を混ぜて使えるUnbabelで、どんな言語の仕事でもLispが使えるよと(笑)

 本題は、Lisperにいちばん重要な図形は「平行四辺形」だという話。初心者のLispコードは横にとびだすが、熟練者のLispコードは平行四辺形になる(笑)。

 そのため、ソースが平行四辺形になっているかどうかスコア付けするプログラムを作った(笑)。調査対象は、ひげぽんさんの日記(笑)。本当に時系列でそれっぽい感じのグラフになった。でも実は、Lisp以外のコードもある(笑)

 まとめは、このプログラムはRubyとLispで書いたけど、Unbabelで一つにできるね、と(笑)。

修正2009-03-01:誤字修正。ココサブさんありがとうございました。

コメント

些細な指摘ですが、

> Q: 最後に速くなった要因は
> * Glok。トップレベルのルックアップをキャッシュする

Glok -> Gloc

ココサブさんありがとうございます

ご指摘いただいた点を修正しました。改めて勉強になりました。ありがとうございました。

コメントの投稿

管理者にだけ表示を許可する

トラックバック

http://emasaka.blog65.fc2.com/tb.php/564-c7aebccc

[shibuya.lisp][Gauche] Shibuya.lisp テクニカルトーク #2 に参加してきた

昨日の Shibuya.lisp テクニカルトーク #2に参加してきたました。 国産3大Scheme 処理系のYpsilon, Mosh の発表に続き、いつものように黒田トーク炸裂の黒田さん、そして今で現役の和田先生の話と非常に楽しい本編。LTも面白いものばかりでした! 出演者の方、スタッフの方

 | HOME | 

Categories

Recent Entries

Recent Comments

Recent Trackbacks

Appendix

emasaka

emasaka

フリーター。
連絡先はこのへん

Monthly


FC2Ad