More Effective C++ ー 読むならC++を何万行も書く前に読みましょう。

有名な「Effective C++」の続編の本です。未踏の期間が終わったこともあり、読む時間を作ることができました。

この本は英語版で、一応日本語版もあるのですが、訳の評判はあまり良くありません。英語版の方も非常に読みやすい英語で、JavaDocレベルの英語が読めればなんとかなると思います。気のきいたジョークに使われる日常単語がいまいち分からなくて全部調べてたので、いまいち笑えませんでしたが…(ーー;

 Effective C++に比べて枝葉の話が多い

続編ということもあり、前編であるEffective C++では言語の根本的な部分のと比較して、Moreの方では細かい話が多いです。

前著の方では、例えば

  • コピーコンストラクタやデストラクタ、operator =を定義しないと勝手にコンパイラが定義してしまいますよ
  • 値渡しよりconst参照渡しを考えた方がいいですよ
  • newしたものはdelete、new [] したものはdelete[]、と対応させないといけません。
  • private継承や多重継承は注意深く使ったほうがいいですよ

といった内容が多く、他言語を使っていたプログラマがC++の世界を理解するには丁度良かったと思うのですが、今回のMoreの方では、

  • 関数の引数で暗黙的な変換が起こるのは値渡しかconst参照渡しの時だけで、しかも変換は一度しか起きません
  • 参照カウントなスマートポインタ
  • デストラクタは例外が起こってもちゃんと実行されるのでリソースリークを避けるのに使えます。
  • 多重継承・virtual継承する時のオブジェクトのデータフォーマットはこうなっている(事が多い)ですよ

といった内容です。最後の項目はvtableやvptrの実態がよくわかったので参考になったのですが、その他の項目は今ではインターネット上のC++に関する文章や、STLをある程度使っていると「そらそうよ…」「せやな…」と思ってしまう内容が多く、Effective C++を読んだ時に感じた、あの驚きをもう感じることはできませんでした。Effective C++を読んで少しC++を書き始めた時期に読めばもっと参考になったのでしょうが、数万行書いた後となると…。

改訂が繰り返されているEffective C++と違い、Moreは95年から一度も改訂されていません。STLは出たばかりの時期だったようです。

本を読むよりソースを読んで書いてWebのリソース読むのが好きな人は、まあ読まなくても…。

この本の中で特に一番大きく扱われているのは、参照カウント・スマートポインタです。sharedされている値そのものが参照カウント数を管理する、boostでいうところのintrusive_ptr相当のものをじっくり実装したあと、階層を一個上げてshared_ptr相当のものを実装します。が、相当のものがある事からも分かる通り、どちらも既に有名なもので、いまいち読んでも驚きがありません。しかもweak_ptrを扱っていませんし、参照カウントで問題になる「自分へのshared_ptrを基本的に持てない」という問題も扱っていません。

もしも読むなら、Effective C++を読んでちょっとC++を書いたらすぐに読むことをお勧めします!

JavaScriptのTypedArrayで高速にmemsetするには

JavaScriptでパフォーマンスを出すことを…強いられるんだ!!!(カッ

で、今回はその関係で色々試したことの一つについて、昔やった結果を纏めたのを書きました。

TypedArray

最近のJavaScriptにはTypedArrayというのがあります。通常のJavaScriptの配列は、要素にどんな型でも入れられる上、厳密には配列ではなくハッシュであるため効率が悪いのですが、このTypedArrayでは配列の型を指定した本物の配列であるため、高速・効率的に処理できます。

もともとはJSでOpenGLを使うWebGLという技術向けに策定された仕様なのですが、別にWebGLでなくても使用できて、以前開発したJSのファミコンエミュレータでも、ファミコンのRAMやフレームバッファをこれで表現しています。

さて、このTypedArray、色々とメソッドが定義されていて、よく使う処理は大体網羅されているのですが、memset(メモリ全体を特定のデータで塗りつぶす)を行うようなメソッドがありません。結構使う処理だと思うのですが、無いのでなんとかJSで塗りつぶさないといけない、という事になります。

今回はTypedArrayのmemset処理について色々と試してみた結果を書きます。

条件

  • Let’s note SX-1 SSD Edition CF-SX1GETDR
  • Intel Core i5-2540M
  • Windows 7 64bit
  • Firefox 18 x86

方法1:普通にループで回す

var memory = new Uint8Array(1024*1024);
log("normal: "+cycloa.probe.measure(function(){
    var m = memory;
    for(var i=0;i<5000;++i){
        for(var j=0;j<1024*1024;++j){
            m[j] = i;
        }
    }
}));

一番遅そうですが、一番オーソドックスな方法です。5000回、1MBのデータを0で埋めてみると、5回試行してそれぞれ
5008ms, 4950ms, 4955ms, 4949ms, 4957ms
になりました。

ということで、5000ms前後がベースラインということになります。これから遅くなったらむしろ逆効果ということでです。

方法2:小さい配列をループで初期化してsetで回す

setというメソッドがあって、これを使うと複数の要素を一気に上書きすることができます。

var mem = new Uint8Array(1024*1024);
var another_mem = new Uint8Array(1024);
var offset  = 100;
mem.set(another_mem, offset);  -> 100バイト目から1,024バイトがanother_memの内容に上書きされる

さらにこのanother_memの作り方として、上のようにnewで作る方法とsubarrayを使って元の配列を部分的に共有したものを使う方法があります。

ver another_mem = mem.subarray(100,100+1024); -> memの100から100+1024バイト目までを共有したメモリ配列を作

全部ネイティブで0にするより、一旦小さな配列を0で埋めてからsetでセットしたほうが速い気がしませんか。私はそう思いました。

全部JSのループで回すのは遅いというのがわかりましたし、かといってあんまり小さな配列を使って何度もsetを呼び出してもネイティブ呼び出しのオーバーヘッドが重いだろうと思われるので、このバランスをどうするかが問題になります。今回は、1KBから1MB(意味なし)まで変化させて測定しました。

new Uint8Arrayで配列を作ってコピーする方法

for(var z=10;z<=20;++z){
    log(""+cycloa.probe.measure(function(){
        var m = memory;
        var bsize = 1<<z;
        var copy_times = 1024*1024/bsize;
        var buff = new Uint8Array(bsize);
        for(var i=0;i<5000;++i){
            for(var j=0;j<bsize;++j){
                buff[j] = i;
            }
            for(var j=0;j<copy_times;++j){
                m.set(buff, j*bsize);
            }
        }
    })+",");
}
1 2 3 4 5 平均
1024 557 559 547 553 543 551.8
2048 399 397 395 399 398 397.6
4096 340 343 340 342 342 341.4
8192 322 319 319 328 331 323.8
16384 367 369 373 369 372 370
32768 477 480 478 483 482 480
65536 630 630 631 632 638 632.2
131072 919 928 926 929 939 928.2
262144 1598 1583 1584 1589 1619 1594.6
524288 2854 2831 2821 2834 2935 2855
1048576 5624 5396 5326 5437 5418 5440.2

subarrayを使って小さな配列を作る方法

for(var z=10;z<=20;++z){
    log(""+cycloa.probe.measure(function(){
        var m = memory;
        var bsize = 1<<z;
        var copy_times = 1024*1024/bsize;
        var buff = m.subarray(0, bsize);
        for(var i=0;i<5000;++i){
            for(var j=0;j<bsize;++j){
                buff[j] = i;
            }
            for(var j=1;j<copy_times;++j){
                m.set(buff, j*bsize);
            }
        }
    })+",");
}
1 2 3 4 5 平均
1024 640 564 553 565 557 575.8
2048 417 404 401 405 404 406.2
4096 343 348 342 347 341 344.2
8192 319 320 319 320 318 319.2
16384 369 377 367 362 369 368.8
32768 468 471 470 467 465 468.2
65536 611 614 610 610 607 610.4
131072 891 882 873 876 888 882
262144 1516 1502 1498 1493 1520 1505.8
524288 2678 2653 2652 2667 2658 2661.6
1048576 4993 4934 4922 4972 4923 4948.8

 グラフ

new Uint8Arrayで配列を作ってコピーする方法

20130129_01

subarrayを使って小さな配列を作る方法

20130129_02

やっぱり小さな配列を作ったほうが速い

と、いうわけで、8192くらいの配列を作ってsetで回したほうが大体17倍くらい速いです。subarrayの方が配列生成コストが変わってくるのかなぁ、と思ったのですが、あんまり変わらないようですね。

ただこの8192という数字は2013年のFirefox18のWindows7でCore i5(Ivy Bridge)というひっっっっっっじょうに限られた環境での値なので、あんまり鵜呑みにしないほうがいいと思います。もし、JSの実行速度がネイティブ関数呼び出しのコストに対して相対的に速い環境があればこの値は大きくなるかもしれませんし、ネイティブ関数呼び出しのコストがJS実行速度よりも相対的に安い環境があれば、この値は小さくなってくると予想されます。

結論

  • HTML5のTypedArrayでは、メモリの内容を特定の値で塗りつぶすとき、subarrayでも新しくつくるのでも、他のTypedArrayを用意してそれを特定の値で塗りつぶしてからsetを繰り返す方がとても速い
  • 8192bytesの配列を用意すると一番速かったけど、他の環境では分からない。
  • ターゲットの環境で調べれば良いのでは(クロスプラットフォームを無視した言い方)

JSは大変ですね…。

GoogleTestでマクロを使ってテストを自動生成するバッドノウハウ

C++のテストフレームワークのGoogleTest、活用してますか!!私は大好きです!!(何

テストフレームワークを使ってると、マクロを使って似たようなテストをまとめたくなる時があると思います。前後のセットアップだけ同じで型名とテストする値だけが違うとか。できればテンプレートを使ったほうがいいと思いますが、そうもできない場合もあるでしょう。

#define _MY_TEST(TYPE, VALUE, EXPECTED) \
{ /* plus */\
TYPE result;\
ASSERT_NO_THROW( result=do_sth<TYPE>(VALUE) );\
ASSERT_EQ( EXPECTED, result );\
}\
{ /* minus */\
TYPE result;\
ASSERT_NO_THROW( result=do_sth<TYPE>(-VALUE) ); /* マイナス */\
ASSERT_EQ( EXPECTED, result );\
}

TEST(MyTest, TEST_A)
{
_MY_TEST(int, 0x7fffffff, 0x80000000); // do_sthは何するんだろう…
_MY_TEST(unsigned short, 0x7fff, 0x8000);
...
}

でも、コレは動かないのです。こんなエラーメッセージが出ちゃいます。

****.cpp: In member function ‘virtual void MyTest_TEST_A_Test::TestBody()’:
****.cpp:719:1140: error: duplicate label ‘gtest_label_testnothrow_719’
****.cpp:720:1171: error: duplicate label ‘gtest_label_testnothrow_720’

さて…GOTOのラベルがかぶっているようです。なんでなのかは、ASSERT_NO_THROWの先を見ればわかります。

#define GTEST_TEST_NO_THROW_(statement, fail) \
 GTEST_AMBIGUOUS_ELSE_BLOCKER_ \
 if (::testing::internal::AlwaysTrue()) { \
 try { \
 GTEST_SUPPRESS_UNREACHABLE_CODE_WARNING_BELOW_(statement); \
 } \
 catch (...) { \
 goto GTEST_CONCAT_TOKEN_(gtest_label_testnothrow_, __LINE__); \
 } \
 } else \
 GTEST_CONCAT_TOKEN_(gtest_label_testnothrow_, __LINE__): \
 fail("Expected: " #statement " doesn't throw an exception.\n" \
 "  Actual: it throws.")

というわけで、GOTOのラベルに__LINE__マクロで取得した行数を使っているのですが、関数風マクロで展開するソースは一行で展開されるので、先ほどの_MY_TESTの複数のASSERT_NO_THROWで同じ__LINE__が使われてしまい、GOTOのラベルがかぶるのでさっきのようなエラーでコンパイルエラーになってしまったのでした。

むー。困りましたね。

マクロ内でマクロのディレクティブは使えない

たとえばこんな事はできません。

#define _MY_TEST(TYPE, VALUE, EXPECTED, x) \
 { /* plus */\
 TYPE result;\
\
#line (x*1000) /*lineディレクティブで書き換えてしまえばよいのでは!? */\
 ASSERT_NO_THROW( result=do_sth<TYPE>(VALUE) );\
 ASSERT_EQ( EXPECTED, result );\
 }\
 { /* minus */\
 TYPE result;\
#line (x*1000)+1 /*上とは違う番号を使っている */\
 ASSERT_NO_THROW( result=do_sth<TYPE>(-VALUE) ); /* マイナス */\
 ASSERT_EQ( EXPECTED, result );\
 }

#lineというディレクティブを使うと__LINE__での行番号がこの行以降差し替わるので、これで変えてあげればかぶらなくなるのでは?と思ったのですが、やはり一行に展開されてしまうので、このように展開されてしまい…

{.... #line (x*1000)+1 ASSERT_NO_THROW(.... /*←改行なし*/

これでは文法エラーにしかなりません。

 仕方ないのでファイルを分ける

何かいい方法無いのかなーと考えていたのですが、プリプロセッサには関数風マクロ以外にもソースの繰り返しを行う方法がありました。includeです。

さっきのマクロの内容そのものの別ヘッダファイルを作り…

/* inc.h */
#define _MY_TEST(TYPE, VALUE, EXPECTED, x) 
 { /* plus */
 TYPE result;

 ASSERT_NO_THROW( result=do<TYPE>(VALUE) );
 ASSERT_EQ( EXPECTED, result );
 }
 { /* minus */
 TYPE result;
 ASSERT_NO_THROW( result=do<TYPE>(-VALUE) ); /* マイナス */
 ASSERT_EQ( EXPECTED, result );
 }

それをincludeして繰り返しすれば…

TEST(MyTest, TEST_A)
{
#define TYPE int
#define VALUE 0x7fffffff
#define EXPECTED 0x80000000
#include "inc.h"
#undef TYPE
#undef VALUE
#undef EXPECTED
}

別ファイル内でのgoto扱いになるので、さっきのエラーは出なくなります。若干不恰好ですが、手動で繰り返すよりは…。

できればテンプレートを使う方が良いと思う

マクロではなくテンプレートを使ってテストをパラメータ化すれば、このような問題は起きません。テンプレートではマクロの##(シンボル連結)とか#(シンボルの文字列化)みたいな機能は使えませんが、もっと安全だし楽なので、出来ればテンプレートで出来ないか先に考えるほうが良いと思います。。。

FirefoxでJITコンパイルの「正しさ」を担保する”Invalidation”

なかなか感動した次の記事を翻訳しました。翻訳とか初めてなので、意訳とかがところどころあれかも知れません。

The Ins and Outs of Invalidation | JavaScript

Firefox18で追加されたJITコンパイラ「IonMonkey」で、どうやってJITコンパイル時の型についての仮定を守りつつ、効率的にJITコンパイルを行うかの話です。「型推論w どうせJSのJITコンパイルとか、『大体Intが来るっぽいからInt向けにコンパイルしとこう』、みたいな感じでしょ?w」って思ってませんか?もっともっと、凄まじいですよ。

この記事のライセンスは元記事と同じ、「Creative Commons Attribution Share-Alike License v3.0 or any later version.」となります。

The Ins and Outs of Invalidation

動的言語のJITエンジンの主な目的の一つは、高水準な言語を効率的な機械語にコンパイルすることだ。しかしながら、コンパイルされたコードはすべて、元のJavaScriptのコードがインタプリタで実行されたときと同じように振舞わなければならない。つまり、コンパイルされたコードの「正しさ」を保つことがJITコンパイラに求められる基本的な問題なんだ。

しかし、効率的かつ正しいコードを生成するのは難しい。なぜなら、JavaScriptは非常に高い多態性を持つからだ。すべての変数はどんなタイプの値でも持つことができるし、一般的に言って実行時にどんな型の値が代入されるかを事前に知ることは出来ない。たとえば、常に2つのintegerを足し合わせるようなコードがプログラム上のどこかにあったとしても、実行エンジン自体はintegerじゃない値が来ることを許さなければならないんだ。

この問題に対処するためのテクニックが、大まかに言って2つある。ひとつは「guarding」だ。実行エンジンが実行前に型について仮定したことが守られているか実行時にチェックするようなコードを生成するんだ。さっきの例で言えば、JITコンパイラは2つのintegerを足し合わせる機械語を生成するけど、そのコードが実行される前に本当にそれらの2つの値がintegerであることを確かめるような機械語も追加する。もしそのチェックが失敗してしまったら、機械語は処理を明け渡し、稀なケースを処理するための、汎用的で遅い方法で実行を続ける。もしチェックが成功すれば、高速な(あるいは最適化された)機械語が実行される。このチェックは大体成功するから、速い方法がたいていは実行される。

このguradingはよい方法だけど、パフォーマンス上のペナルティがある。仮定が守られてるかのチェックには時間が掛かるし、何度も実行されるコードではそれがパフォーマンス上の重大な損失になってしまう。もうひとつの効率的なコードを生成しつつ正しさを守る方法は、invalidationだ。それが今回の記事で私が話したいこと。これからSpider Monkeyの新しいJITであるIonMonkeyを例として使うよ。でも、細かい点を除けば全体的な戦略は殆どのJITに適用できる。

Invalidation at 10,000 Feet

Invalidationの鍵となるアイデアは「毎回仮定が守られているかチェックする機械語を生成する代わりに、その仮定が正しく無くなったら生成した機械語を無効化(invalidate)してしまう」ということだ。ただし無効化された機械語が決して実行されないようにするために、型に対するガードとは別のガードを追加しないといけない。まずは簡単な例を見てみよう。ここにいくつかの点の間の距離の和を求める、簡単なJavaScriptプログラムがある。

function Point(x, y) {
    this.x = x;
    this.y = y;
}

function dist(pt1, pt2) {
    var xd = pt1.x - pt2.x,
        yd = pt1.y - pt2.y;
    return Math.sqrt(xd*xd + yd*yd);
}

function main() {
    var totalDist = 0;
    var origin = new Point(0, 0); 
    for (var i = 0; i < 20000; i++) {
        totalDist += dist(new Point(i, i), origin);
    }
    // The following "eval" is just there to prevent IonMonkey from
    // compiling main().  Functions containing calls to eval don't
    // currently get compiled by Ion.
    eval("");
    return totalDist;
}

main();

このプログラムを実行するとき、dist関数は大体10000繰り返し実行された後、IonMonkeyによってコンパイルされる。その時の中間言語(intermediate representation; IR)はこれだ。

[1]   Parameter 0          => Value     // (pt1 value)
[2]   Parameter 1          => Value     // (pt2 value)
[3]   Unbox [1]            => Object    // (unbox pt1 to object) 
[4]   Unbox [2]            => Object    // (unbox pt2 to object)
[5]   LoadFixedSlot(x) [3] => Int32     // (read pt1.x, unbox to Int32)
[6]   LoadFixedSlot(x) [4] => Int32     // (read pt2.x, unbox to Int32)
[7]   Sub [5] [6]          => Int32     // xd = (pt1.x - pt2.x)
[8]   LoadFixedSlot(y) [3] => Int32     // (read pt1.y, unbox to Int32)
[9]   LoadFixedSlot(y) [4] => Int32     // (read pt2.y, unbox to Int32)
[10]  Sub [8] [9]          => Int32     // yd = (pt1.y - pt2.y)
[11]  Mul [7] [7]          => Int32     // (xd*xd)
[12]  Mul [10] [10]        => Int32     // (yd*yd)
[13]  Add [11] [12]        => Int32     // ( (xd*xd) + (yd*yd) )
[14]  Sqrt [13]            => Double    // Math.sqrt(...)
[15]  Return [14]

上のコードは本当のコードじゃなくて、分かりやすくしたものだ。本当の、詳しい低レベルのコードが見たかったら、ここをクリックしてね

命令の[3]と[4]で、Ionは引数をオブジェクトへのポインタであり、プリミティブでない事を一切チェックすることなく、値からオブジェクトのポインタを取り出し(unbox)てしまう。命令[5][6][8][9]では、オブジェクトからロードしたxとyをInt32に変換してしまう。

(注意:”unbox”っていうのは、この場合は汎用的なJavaScriptの値を、生の具体的な値、例えばInt32とか、Doubleとか、Objectポインタとか、Booleanとかにデコードすることだ。)

もし私達が仮定が守られていることをチェックするgurdingを使っていたら、次の余計なチェックがコードに現れていただろう。

  1. 2つの型チェック:[3][4]で生の値を取り出す前に「引数がオブジェクトポインタであること」を確かめる追加のチェック
  2. 4つの型チェック:pt1.x, pt2.x, pt1.y, and pt2.yがすべてInt32であることを確かめるチェック

でも、このIRではこの6つのチェックをスキップしていて、とても詰まったコードになっている。ふつうなら、こんなことは出来ない。もしこの仮定が守られなかったら、コードは「間違った」ものになってしまうからだ。もしdist関数がオブジェクトでない引数で呼ばれてしまったら、このJITコードはクラッシュしてしまう。もし、distがxとyのInt32プロパティをもつPointのインスタンスを引数にして呼ばれなかったら、やっぱりクラッシュしてしまう。

この生成された効率的なコードを実行を正しさを保ちつつ使うために、仮定が無効(invalid)になったら実行しない事を徹底しないといけない。そのために、SpiderMonkeyの型推論システムが必要だ。

型推論

SpiderMonkeyの型推論(type inference; TI)は動的にJavaScriptのソースとオブジェクトの型情報と、コードの所々でどういったタイプが現れるかを追跡する。このTIによってメンテナンスされてアップデートされていくデータは、プログラムについての型の知識を表している。そのデータが変更された時、実行エンジンは特定の(型に対する)仮定が壊れてしまっていないかをチェックするトリガーを発動させる。

次の図は、先述までのプログラムの、非常に単純化した型モデルに関する略図だ。

上のTypeScriptはdist関数に関する型情報を持っている。一つ目と二つ目の引数(pt1とpt2)に関連付けられた型の集合などだ。

下のTypeScriptは、Pointに関連付けられた型の情報を持っている。xとyのフィールドに関連付けられた型の集合などだ。

このデータはTIによって必要に応じてアップデートされる。たとえば、dist関数がPointのインスタンスでない引数に対して呼ばれたとすると、TIはTypeScript上の引数に対する型集合を正しくアップデートする。同様に、もしPointがInt32以外のxとyで出来たインスタンスが作られたら、TypeScript上のフィールドに対する型集合は正しくアップデートされる。

Ionが関数をJITコンパイルして、型に関する暗黙の仮定を行う時、無効化フック(invalidation hook)を適切な型集合に対してセットする。こんな感じ:

新しい型が型集合に追加されたときはいつでも、関連した無効化フックが実行され、JITコンパイルされた機械語は無効化される。

Ionで実験

上のコードを書き換えて、実験的にこれらの無効化を発生させてみよう。私はこれから、Mozillaのソースからビルドされた、スタンドアローンのJavaScriptシェルを用いる。あなたも自分でJavaScriptシェルのデバッグバージョンをビルドすることで、以下の実験結果を実際に試すことができる(詳しくはthe SpiderMonkey build documentationを見て!)。

はじめに、簡単なのからやろう。上にスクリプトを実行して、無効化が一切起こってない事を確かめるんだ。

$ IONFLAGS=osi js-debug points.js
[Invalidate] Start invalidation.
[Invalidate]  No IonScript invalidation.

(これから出てくる、余計な嘘の「Start invalidation」は無視してほしい。これはガベージコレクションの開始によるもので、GCによって起こされる可能性のある無効化を実行エンジンがチェックするものだ。今回の記事とは関係ない)

環境変数にIONFLAGS=osiを渡すことで、Ionにすべての無効化や関連するイベントの発生を実行中にコンソールに出力させることができる。出力が示すように、このプログラムでは一切無効化が起こっていない。何一つとして型に関する仮定がコンパイルされた後に壊されていないからだ。

例 2

二番目の実験として、「dist関数の引数はすべてPointのインスタンスである」という仮定を壊して、何が起こるか見てみよう。これが新しいmain関数だ。

...
function main() {
    var totalDist = 0;
    var origin = new Point(0, 0); 
    for (var i = 0; i < 20000; i++) {
        totalDist += dist(new Point(i, i), origin);
    }
    dist({x:3,y:9}, origin); /** NEW! **/

    // The following "eval" is just there to prevent IonMonkey from
    // compiling main().  Functions containing calls to eval don't
    // currently get compiled by Ion.
    eval("");
    return totalDist;
}
...

このプログラムでは、ループ内でdist関数を何度も呼び出して「ホット」にすることで、distがJITコンパイルされるようになっている。また、dist関数に渡される引数はループ内では常にPointのインスタンスであるので、「この関数は必ずPointのインスタンスに対して実行される」という仮定でコンパイルされることになる。ループが実行されたら、もう一度dist関数が呼ばれる。しかし、今度は最初の引数はPointのインスタンスではないので、JITコードでの仮定が壊されてしまう。

$ IONFLAGS=osi js-debug points.js
[Invalidate] Start invalidation.
[Invalidate]  No IonScript invalidation.
[Invalidate] Start invalidation.
[Invalidate]  Invalidate points.js:6, IonScript 0x1f7e430

(もう一度言うけど、最初のStart invalidationはGC実行によって引き起こされたもので、今回の記事とは無関係)

おお!dist関数(points.js, line 6)に対しての無効化を起こせたね!すばらしいことだっ。

下の略図は何が起こったのかを示している。dist関数の最初の引数に対するTypeScriptが変更され、新しい型のTypeObjectに対する参照が追加されている。これが無効化フックを発動させ、IonScriptが無効化された:

例3

3つ目の例として、Pointのインスタンスが必ずint32の値を持っている、という仮定を壊してみよう。今度のmainはこんな感じ:

...
function main() {
    var totalDist = 0;
    var origin = new Point(0, 0); 
    for (var i = 0; i < 20000; i++) {
        totalDist += dist(new Point(i, i), origin);
    }
    dist(new Point(1.1, 5), origin); /** NEW! **/

    // The following "eval" is just there to prevent IonMonkey from
    // compiling main().  Functions containing calls to eval don't
    // currently get compiled by Ion.
    eval("");
    return totalDist;
}
...

それで、これがその結果だ:

$ IONFLAGS=osi js-debug points.js
[Invalidate] Start invalidation.
[Invalidate]  No IonScript invalidation.
[Invalidate] Start invalidation.
[Invalidate]  Invalidate points.js:6, IonScript 0x1f7e430

次の略図が何が起こったのか示している:

Invalidation vs. Guarding

Invalidationとguradingは与えられた操作に対してJITコードを生成する、はっきり異なったアプローチだ。与えられた任意の関数に関してJITコードを生成することについて、どちらのテクニックが使われたとしても、どちらかが必ず優っているわけではない。

今回のInvalidation-basedな最適化のアドバンテージは、仮定が守られているかの毎回のガードがなくなることでhotなコードをかなり速く実行できることだ。しかしながら、もちろん欠点もある。仮定が壊れたとき、その壊れた仮定に頼っているJITコードはすべて無効化され、実行できなくなってしまう。これはつまり、新しい仮定の元で再度JITコンパイルされるまで、遅いインタプリタで実行することになる。もし不幸にも頻繁に型に関する仮定が壊されてしまうような環境でInvalidation-basedな最適化を行なってしまった場合、悲しい事に逆に高い実行時コストがかかってしまう。

Gurad-basedな最適化であれば、生成されるコードのパフォーマンスを犠牲にするかわりに、仮定の変更につよい機械語が生成される。仮定が壊れてしまってもJITコードを捨てなくてもいい。その場合、単に遅い方法で実行されるだけだ。無効な仮定で関数が呼ばれる回数が少なければ(でも0よりは大きければ)、gurdingはinvalidationによる方式よりもよい選択だ。

どちらの方式を使うべきかという問題には簡単に答えることはできない。仮定がたびたび壊れて、高いコストを払って再コンパイルされるとしても、何度も何度も実行されるのでInvalidation-basedな最適化の方が速いかもしれない。もちろん、そうでないかもしれない。どこかの点を超えると、この2つのアプローチのどちらを選ぶかは経験とチューニングの問題となるだろう。

On-Stack Invalidation

今回の記事では無効化の基本的な原理に関する一般的な考え方を書いた。とはいうものの、すべてのJITエンジンが気をつけないといけない、たまにしか起きないが非常に重要なケースがある。

それはon-stack invalidationと呼ばれるものだ。それはコールスタック上にある関数(=今実行中の関数を呼び出している関数)がちょうど無効化されてしまうケースだ。これはつまり、今の関数の実行が終了した後、すでにもう安全に実行できない機械語の実行に戻ろうとする、ということだ。

このケースにはすこし曲芸めいた対処が必要で、発生する可能性のある沢山の捉えづらいエラーを考慮する必要がある。続く記事でこれらに関してさらに書くことにする。


感想

なんというか凄まじいですね。ここまで型を追跡してるとは…。ちなみに最後の「これらに関してさらに書くことにする」の記事は現状ポストされてないようです。読みたいなぁ。

無効化の仮定が壊れてしまったとしても、別の型に対する新しいJITコードを作って使い分ける、とか出来ないですかね。例えば、例として出てきたdist関数ですが、int32に対してJITコンパイルしたバージョンと、floatに対してコンパイルしたバージョンの2つを作って、使い分けるとか。C++のテンプレートみたいな感じ?ここまで徹底的に型を追跡してるなら、やれてもおかしく無い気がします(適当な事を言っています)。

この仮定が壊れてしまった事のメッセージを、ブラウザで書いてる最中からも見れると嬉しいのですが…。上のdistでdoubleが指定されるのはたぶん仕様の範囲内ですが、例えばファミコンエミュレータでint32ではなくfloatで実行された場合、ただのバグなので、それは教えてほしいです。。。

gitリポジトリを公開するための☆過去書き換え☆テクニック

また時間操作か!

githubにリポジトリ公開したいお…でも

       ____ 
     /      \ 
   /  _ノ  ヽ、_  \ 
  / o゚((●)) ((●))゚o \  ほんとはgithubで公開したいんだお…
  |     (__人__)    | 
  \     ` ⌒´     / 

       ____ 
     /      \ 
   /  _ノ  ヽ、_  \ 
  /  o゚⌒   ⌒゚o  \  でもMySQLのパスワードとか
  |     (__人__)    |   公開できない情報が入ってるんだお…
  \     ` ⌒´     / 

       ____ 
     /⌒  ⌒\ 
   /( ●)  (●)\ 
  /::::::⌒(__人__)⌒::::: \   だから過去を書き換えるお!
  |     |r┬-|     | 
  \      `ー'´     /

 と、いうわけで、書き換えです。

githubにソースコードを置きたい…でも公開できない情報が…。ありそうなのはこんなケース?

  • MySQLのパスワードが書いてある…
  • 完全に非公開で遊ぶために書いてたから著作権上アレゲなコンテンツが…
  • 残念な感じのコミットログが…

今更その部分を隠してコミットしたって、昔のコミットログを辿られたら意味ないじゃない!んじゃあ、修正済みのやつだけコミットログ無しで公開?もっと意味ないじゃん

そこで過去の書き換えです。gitはもうぶっちゃけ何でもできるので、過去のコミットを再度やりなおして全部書き換える事ができます。以上のケースについて、修正してみましょう。

 MySQLのパスワードが書いてある…

こんなサンプルリポジトリを考えてみましょう(github)。

ファイルの一部分に公開したくない情報があるケースです。たとえばパスワード。ためしにこんなファイルを考えてみましょう。

// 以下のコードはあくまでサンプルであり、何の意味もありません。

var db = /* なんか初期化処理 */ null;

db.init({password: test}); /* パスワードを追加しちゃった! */
// データベースに何か値を突っ込む
db.save({id: 1, name: "ちさ"});
db.load(); // 何かロード処理的なもの
db.close();

db.initの行でパスワードをハードコーディングしてしまいました。公開するのには問題があるかもしれません。繰り返しますが、この状態からパスワードを隠してコミットしても過去のファイルはそのままなので、意味がありません。

さて、git logはこんな感じです。

commit e236c0d55d0d7fc4744dd5f7edc34b9c22d8cada
Author: psi <ledyba@users.sourceforge.jp>
Date:   Fri Feb 22 11:05:50 2013 +0900

    ロード処理的なものを追加した(という想定)

commit e27ea6a1cf49021b9686c7e757fbf9adf60afb3f
Author: psi <ledyba@users.sourceforge.jp>
Date:   Fri Feb 22 11:05:10 2013 +0900

    パスワードを追加しちゃったコミット。取り消したい。

commit 7c132ae20f6c1db1bff876e8d0626d41e07a8294
Author: psi <ledyba@users.sourceforge.jp>
Date:   Fri Feb 22 11:04:30 2013 +0900

    最初のコミットです。

この「パスワードを追加しちゃった」コミットで、ソースコードに直接パスワードを書いてしまっています。

git diff-tree e27e -p
e27ea6a1cf49021b9686c7e757fbf9adf60afb3f
diff --git a/sample.js b/sample.js
index 0a2fa57..9c892d8 100644
--- a/sample.js
+++ b/sample.js
@@ -2,7 +2,7 @@

 var db = /* なんか初期化処理 */ null;

-db.init();
+db.init({password: test}); /* パスワードを追加しちゃった! */
 // データベースに何か値を突っ込む
 db.save({id: 1, name: "ちさ"});
 db.close();

password: testの部分をpassword: xxxxに変えて、隠しましょう。

そのために、まず新しいブランチを用意します。

git checkout -b rewritten

として新たなブランチをつくった上で、

git rebase -i <修正したいコミットの一個前のコミット>

を実行して書き換え開始です。rebase -iでインタラクティブモードを使うと、コミットを直接書き換えることができるようです。するとインタラクティブなので、こういう感じでエディタが現れます。 →notepad++でgit logを編集したいとき

20130222-01

これで、テキストの上のほうに

pick e27ea6a パスワードを追加しちゃったコミット。取り消したい。
pick e236c0d ロード処理的なものを追加した(という想定)

とあるので、改変した「pick e27ea6a」を「edit e27ea6a」に書き換えてエディタを終了します。すると…

git rebase -i 7c132
Stopped at e27ea6a... パスワードを追加しちゃったコミット。取り消したい。
You can amend the commit now, with

        git commit --amend

Once you are satisfied with your changes, run

        git rebase --continue

と指示が出てくるので、書き換えましょう。書き換えたソースがこれ。

// 以下のコードはあくまでサンプルであり、何の意味もありません。

var db = /* なんか初期化処理 */ null;

db.init({password: xxxx}); /* パスワードは隠しておいた */
// データベースに何か値を突っ込む
db.save({id: 1, name: "ちさ"});
db.close();

ちゃんと隠しました。

指示されたとおり–amendでコミットします。その前にgit addを忘れないように

git add sample.js
git commit --amend
[detached HEAD 6a7b87a] パスワードを追加したコミットだったけど、取り消しておいた
 1 file changed, 1 insertion(+), 1 deletion(-)

これで書き換えられましたとさ。で、残りのコミットをgit rebase –continueで再度適用しなおします。

$ git rebase --continue
Successfully rebased and updated refs/heads/rewritten.

gitk –allってやって全コミットを可視化すると…

20130222-02

ちゃんと枝分かれしてます。masterを消してrewritteをmasterにrenameすれば、完全に書き換えたことになります。

ここで注意しないと行けないのが、「ロード処理的なもの~」というコミットが2つ存在することです。rebase -iして書き換えると、その時点以降のコミットはすべて別のコミット扱いになるので、注意が必要です。

最初のコミットはどうするの?

上では修正したいコミットの一個前のコミットを指定しましたが、じゃあその一個前のコミットがない、最初のコミットはどうすればいいの?その場合のサンプルも用意してみました→github:ledyba/__sample__RewriteGitHist2

この時は若干面倒くさいです。

まず、テンポラリなブランチを作って…

git checkout -b tmp

reset –hardで一番最初まで戻ります。

git reset --hard <一番最初のコミット>

この状態で、消したい部分を修正して、コミットを修正しちゃってください!

vi <修正したいファイル>
git add <修正したいファイル>
git commit --amend

こうすると、tmpブランチはmasterブランチとは一切つながりのない孤立したブランチとなります。よく見てみてください。線が繋がってません。

20130222-03

ではここからどうするかというと、この新しい孤島のtmpに、書き換え以前のmasterのコミットを適用しなおします。

そのためにmasterの最初のコミットに、oldrootというタグをつけて、rebase –ontoを使います。

git rebase --onto tmp oldroot master

すると(うまくマージが動けば)修正済みのmasterブランチが出来上がってくるはずです。

20130222-04

昔の書き換えたいコミットである、oldrootが今度は孤島になりました。

過去コミットのAuthor/Comitterを書き換えたい

以前適当に使っていたので、設定する名前とメールアドレスも適当でした。マシンごとに違った設定だったり、セットアップしなおすたびに適当に違うメールアドレス入れたり。

$git config --global user.name fuga
$git config --global user.email hoge@gmail.com

でもそうすると、誰がコミットしたのか訳がわからなくなってしまって、困ってしまいます。ので、公開するときにはこれを統一したい。そう思いました。

その方法ですが、stack overflowに書いてあるのでそのまま受け売りすると、filter-branchを使うと書き換えられるようです。

 git filter-branch --commit-filter '
        if [ "$GIT_COMMITTER_NAME" = "<Old Name>" ];
        then
                GIT_COMMITTER_NAME="<New Name>";
                GIT_AUTHOR_NAME="<New Name>";
                GIT_COMMITTER_EMAIL="<New Email>";
                GIT_AUTHOR_EMAIL="<New Email>";
                git commit-tree "$@";
        else
                git commit-tree "$@";
        fi' HEAD

とやって、コミット時にいろいろ書き換えられます。このcommit filterのなかに書いてあるのはシェルスクリプトで、sedを使ってファイルを書き換えることもできますし、上記のように環境変数を指定することで、メタデータも書き換えられます。書き換えられるメタデータは以下:

  • GIT_AUTHOR_NAME
  • GIT_AUTHOR_EMAIL
  • GIT_AUTHOR_DATE
  • GIT_COMMITTER_NAME
  • GIT_COMMITTER_EMAIL
  • GIT_COMMITTER_DATE

特定のファイルを全部除去したい

今度は例えば、画像処理プログラムのサンプルで、著作権的によろしくない画像を使ってた…みたいなケースです。ありそう(過去を思い出しながら)

上記のfilter-branchではコマンドラインを使うと任意のシェル・コマンドが使えますので、

git filter-branch --commit-filter 'rm -f <消したいファイルとか>' HEAD

ってやれば、ファイルとか全部消せます。examplesにいろいろかいてあるので試してみてね

おわり

rebaseの話はあんまり見ないので、そちらを重点に、以前やったことがある書き換えについて書いてみました。gitのブランチを詰将棋みたいに書き換えるゲームもあったりするようで、gitのこの辺の機能は強力であると同時に少し難しいですね…。

Snap@Haskellでファイルアップロード時にenctype指定を忘れるとエラーも出ずに動かない

悲しい話

情弱でもSnapでファイルアップロードしたい!

HaskellのWebフレームワークSnap、使ってますか!最近ちょっと触ってて、ファイルアップロードがしたいなぁと思ってこんなハンドラを書きました。Snapでは、URLに紐ついたハンドラ(結局モナド)を登録して、特定のURLにアクセスされると、そのハンドラが実行されます。

こんな感じ:

handleUpload :: Handler App App ()
handleUpload = method GET (redirect "/") <|> method POST handlePost
    where
        process part = continue (\a -> (yield (partFileName part) a))
        handlePost = do
            ret <- handleMultipart defaultUploadPolicy (\p -> process p)
            writeText $ T.pack $ show ret

ふーむ。この状態でこんなフォームを書いて送信してみます。

<form method='post' action='/upload'>
  <table id='info'>
    <tr>
      <td>file: </td><td><input type='file' name='image' size='20' /></td>
    </tr>
    <tr>
      <td></td>
      <td><input type='submit' value='send' /></td>
    </tr>
  </table>
</form>

よくみるとformでのenctype指定がないのですが、最初私は気づきませんでした。さてブラウザからアクセス。

20130218-01 アップロード。

20130218-02うーん、acceptできるハンドラがない、ねぇ…。最初、ルーティングがうまくいってないのかな、と思ったのですが、GETで/uploadにアクセスするとちゃんとリダイレクトがかかるので、そこは間違ってないだろう、となると、このPOSTのハンドラが変みたいだ、と目星をつけました。

finally catch try ->どれも動かない

handleMultiPartを消してreturnにするとちゃんとレスポンスが表示されるので、どうやらここで例外?が発生してる模様。じゃあ`catch`だ!とやってみても…

handleUpload = method GET (redirect "/") <|> method POST handlePost
 where
 process part = continue (\a -> (yield (partFileName part) a))
 handlePost = do
 ret <- (handleMultipart defaultUploadPolicy (\p -> process p)) `catch` (\(e :: SomeException) -> [show e])
 writeText $ T.pack $ show ret

こうしても、さっきとまったく同じ、「No handler accepted.」。すべての例外をキャッチできるはずのSomeExceptionを使ってもだめ。例外がキャッチできてないからか、finallyを使っても何も起こりません。tryを使ってもEitherが帰ってこず、処理がスキップされちゃいます。

これ、C++で-fno-exceptionした時となんか似てます。例外処理が動いてないのでは?…もっとも、C++の場合はもっと不思議なことが起こったりですが…。

Multi-Partのチェックとその失敗処理は例外と直行している

中身を見るしかないので読みましょう。まぬあるにて、どうぞ。 HaskellのドキュメントシステムHackageでは、rdocみたいにソースが読めます。すばらしい。

長いのですが、今回エラー処理が起こされているのはここでした。

    -- not well-formed multipart? bomb out.
    when (ct /= "multipart/form-data") $ do
        debug $ "handleMultipart called with content-type=" ++ S.unpack ct
                  ++ ", passing"
        pass

passというので実際に処理を抜けているようですね。このpassのドキュメントはこれ。Exception関係のものがシグネチャにあらわれていないのを見ればわかるように、例外とは一切関係なく処理をスキップ致します。finallyを使っても何も起こせないのは、こういう事だったのですね。

debugを有効にしたほうがいいかもしれない

環境変数にDEBUG=1を指定するとデバッグモードが有効になります。

すると、こんな感じのエラーログがひたすら出力されます。

 [       8] handleMultipart called with content-type=application/x-www-form-urlencoded, passing
 [       8] Server.httpSession: finished running user handler
 [       8] Server.httpSession: handled, skipping request body
 [       8] httpSession/skipToEof: BEGIN
 [       8] httpSession/skipToEof: continue

これならコンテント・タイプがおかしいんだな~ってすぐ気づけますね…。開発中はずっとこれをつけといたほうがいいかもしれませんね!

ちなみにうまくいくと

20130218-03Justでファイル名が帰ってくるだけの簡単なサンプルプログラムでした。ファイルは扱ってないです…。

ネタもと

ぼんやりと「Haskellのエラー処理とMonadCatchIOの落とし穴 – 純粋関数型雑記」を見てたら思い至った話です。

「例外、失敗」を処理する方法がたくさんあるのは柔軟で良いと思うのですが、ルールをちゃんとあわせておくか、あるいは別種の「失敗」があることをちゃんと把握しておかないと意図しない挙動になっちゃうのは、悲しいですね…。

明日「未踏事業 成果報告会」@秋葉でしゃべります

こんにちは!

ここ一ヶ月で「時を司るスクリプト言語 ど~なっつ」やそれを使った出前授業について書いて来ましたが、実はそれらは全て国の機関IPAの未踏事業の支援を受けて行なってきたものだったのです!

で、ついにその支援期間も終わりまして、その成果を報告する成果報告会が明日、秋葉のUDXで行われます。もちろん支援を受けた私もその中で喋ります。

11 17:35-18:10 「CPUの理解を容易にするシステムと解説サイトの構築」

秋葉のUDX、しかも17時半ですので、仕事や学校の帰りにすこし時間のある方はぜひいらして下さい!

みどころ?

ど~なっつで開発された教材を使って今月中旬に行われた、出前授業についてレポートします。特設サイト~。

時を司るスクリプト言語 ど~なっつについて、実際のデモを交えながら、「時を司る」さまをデモります!

【備忘録】boost1.52をソースからインストール

毎回毎回どうやるんだっけ…とか検索してて不毛なので自分用にまとめました

私はboostをWindowsのMinGWでC++11のスレッド・アトミックサポートがうまく動かないのでその代替として使っています。環境の組み合わせは:

  • Windows 7 x86_64
  • mingw32 x86
  • gcc 4.7.2 x86

ダウンロード

boostの公式サイトからソースのtarballをダウンロードしてどっかに保存してtar xvf。

boost::atomicの追加

採択されたらしいのになぜか入ってないboost::atomicを手動で入れる

公式サイトからダウンロードして中身を全部boostのフォルダにマージすればOKな模様。とりあえず使えたのでこれいいのかなと…。

bjamのブートストラップ

解凍したディレクトリに入って

cmd
bootstrap.bat gcc

するとb2.exeが出来て、これがboostのビルドシステム。bjam.exeっていうのもできてるけどこれはどうやら古い(?)ビルドシステムの模様。折角なのでb2を使いました。

b2の設定&ビルド&コンパイル

b2 --help

で設定が見れる。

b2 --show-libraries

でライブラリの一覧が見える。後で–without-****するときにこの名前が必要。

今回使った設定

これらを使って今回紡いだオプションがこちら

b2 --prefix=<install先> --build-type=complete \
--toolset=gcc --variant=debug,release \
--without-python --without-graph \
--without-graph_parallel --without-mpi \
link=static threading=multi runtime-link=static \
release debug stage -j4

これでちゃんと動くようなら上記の最後に install を追加したb2を走らせてインストール。

終わり

お疲れ様でした。

ど~なっつ、時を司るプログラミング言語。

あけましておめでとうございます!!今年は友人のサークルで売り子をしていたのですが、なんと完売御礼でした!!やったねたえちゃん!(謎

さて元日も過ぎて餅にも飽きてきた頃かと思いますので、半年間掛けて未踏IT人材育成事業で開発していたもののうち、なんとか外に出せそうなスクリプト言語部分について紹介します!

ど〜なっつ、時を司るスクリプト言語

20120102

ど~なっつは

  • 処理系とその外界の状態を過去に戻し、未来に戻せ、
  • 任意の時点でのセーブデータを書き出し、後で実行を再開できる、

ちょっと変わった「時を司るプログラミング言語」です!

時を司るプログラミング言語

普通、プログラミング言語って上から下に実行されて、起こった事は元に戻りません。副作用ってやつです。覆水盆に返らず。

int main(){
    int x = 10; //このときxは10。
    printf("x is %d", x);
    x = 20; //これ以降、ずっと20で、以前10だった痕跡は一切残らない。
    printf("x is %d", x);
    return 0;
}

タイムリープでフロー制御。

でも、戻りたい時だってあるかもしれません。例えば、ユーザーのログイン処理なんかそうでしょうか。普通のプログラミング言語、例えばRubyだと、こんな感じでパスワード認証を書くでしょうか?

while true do
    puts "パスワードを入力して下さい!"
    passwd = gets
    if passwd == "正しいパスワード" then
        puts "認証完了"
        break
    end
    puts "間違ったパスワードです"
end

puts "こんにちは、正しいユーザーさん!"

すっきり書けました。

でも…。やりたい事は

  • 正しいパスワードが入力されるまで繰り返し

ではなくて、

  • 正しいパスワードが入力されたらログインしていいけど、そうじゃなかったら門前払い

なのではないでしょうか?「ど~なっつ」では、こんな感じで同じプログラムを書けます!

//このあとの命令を使って、この時点まで時を戻せるようになります。
save_time=Homura.tick();

System.print("パスワードを入力してください。");
//パスワードを読み込みます。
passwd=System.readline();

if(passwd == "abcdef"){
  //パスワードの認証に成功しました。
  System.println("こんにちは!正しいユーザーさん。");
} else {
  // 上で記録した時間まで、スクリプトエンジン全体を戻します。
  System.println("パスワードが間違っています!");
  Homura.seek(save_time);
};

「Homura」というオブジェクト1を使って、パスワードが間違っていたときはログイン処理前にまでタイムリープさせてしまいます。変数、コールスタック、全ての「環境」が文字通り「戻ります」。

これで不自然な繰り返しを使わずにユーザーログイン処理が書けてしまうのです!(ドヤァ

私は何度でも繰り返す。

gotoでも同じように書けますが、変数も全て巻き戻されるので、安全に巻き戻す事ができます。この事を利用すると、「時が戻る事を利用したループ」がつくれます。普通に起こすと無限ループになりそうですが、ほむらオブジェクトに突っ込んだ値はタイムリープ前の事を覚えているので、コレを使います。交わした約束忘れないよ

//普通の変数は、時間操作の影響を受けますが…
tabeta=0;

//Homuraは時間操作前の事を覚えていて、時間操作の影響を受けません。
Homura.counter=0;

//このあとの命令を使って、この時点まで時を戻せるようになります。
save_time=Homura.tick();

if(Homura.counter < 10){
  // ドーナッツを食べましょう。
  // この足し算の結果は、時間操作で戻ってしまいます。
  tabeta++;

  // ドーナッツを食べた回数を表示しましょう
  System.println(tabeta, "番目のドーナッツを食べた!");

  // Homuraに入った値は時間操作の影響を受けないので、
  // 時間操作を行なってもこの足し算の結果は戻りません。
  Homura.counter+=1;

  // 上で記録した時間まで、スクリプトエンジン全体を戻します。
  Homura.seek(save_time);
} else {
  //ど~なっつでは、else節を省略することはできません。
};

これを実行すると、

% donut time_op.donut
 1番目のドーナッツを食べた!
 1番目のドーナッツを食べた!
 1番目のドーナッツを食べた!
 1番目のドーナッツを食べた!
 1番目のドーナッツを食べた!
 1番目のドーナッツを食べた!
 1番目のドーナッツを食べた!
 1番目のドーナッツを食べた!
 1番目のドーナッツを食べた!
 1番目のドーナッツを食べた!

このように何度ループをめぐっても1番めのドーナッツを食べ続けることができますが、Homuraは時間操作の影響を受けないので、無限ループには陥らずに済みます。

「継続」と違って スクリプト外部への副作用も制御できる

こういったループはSchemeのcall/ccやRubyのFiberような「継続」を使えば記述することができます。しかし、「継続」のアプローチでは戻せないものがあります。それは、言語処理系の環境です。

つまり、Scheme内から外界(たとえばウィンドウシステム)に、「ウインドウを表示する」と言った副作用を起こしていた場合、「ウインドウを表示する」以前の継続に戻っても、戻るのはSchemeの中でだけであって、ウインドウは表示されたままになってしまいます2

「ど〜なっつ」では言語処理系外に起こした副作用も、「副作用」に対応した「反副作用」みたいなものを登録して管理させることができます。時間操作が行われた瞬間にその「反副作用」を用いて副作用を打ち消させることができます。

でも、「反副作用」を作れない場合もありますよね?例えば、ネットワークでデータを送信するような操作は絶対取り消せませんから、「反副作用」は作れません。そのときにその時刻以前には戻れないようにする機構も作られています。コンソールへの出力も取り消せませんから、今回使ってるSystem.printlnなども本当は取り消せないメソッドとして登録すべきなのですが、副作用のないメソッドとして登録されています。HaskellのUnsafeIOみたいな感じです。

普通にスクリプト言語

関数も使えますし、関数はクロージャーですし、第一級オブジェクトです。JavaScriptのような感じで使えます。

f = func(idx, acc){
    if( idx <= 0 ){
        acc; //最後に評価された値が戻り値になる
    }else{
        return f(idx-1, acc+idx); //戻り値を明示することもできます。
    };
};
System.println(f(10, 0)); // prints 55

またプロトタイプ型オブジェクト指向言語で、__proto__にオブジェクトを指定するとJSのようにプロトタイプを巡ってくれます(この辺のドキュメントも書かなきゃ…)。全体的にはJavaScript: The Good Parts ―「良いパーツ」によるベストプラクティスを参考に設計されています。

 

まだまだ開発中で、リポジトリも未踏でのプロジェクトと同じリポジトリに入っていて大変使いづらいとは思うのですが、テンションを上げるために公開してみました。

ダウンロード

ダウンロードはど~なっつのサイトからお願いします!githubでのソースは本体プロジェクトの「ちさ」と同じ所に入ってます。

ライセンス

ど~なっつのライセンスはGPLv3となっています。

他に開発中のもの

他に開発中の本体プロジェクト「ちさ」は、このど~なっつをネイティブで使用して、時を司り、さらに任意の時点での実行状態を保存できるGUIツールキット兼電子コンテンツエンジンです。が、まだあんまり出来てないので公開はまだしません。

Thanks

ど~なっつはIPAの未踏IT人材発掘・育成事業に採択された「CPUの理解を容易にするシステムと解説サイトの構築」の一部分として開発され、支援を受けています。

 

  1. もちろんアレです []
  2. もちろんアドホックに実装した場合は除きます []

クリスマスはNoiz2saをChromeで遊ぼう!

Native Clientは死んだんだ
いくら呼んでも帰っては来ないんだ
もうあの時間は終わって、君も人生と向き合う時なんだ


弾幕の海にたゆたう、アブストラクトシューティングNoiz2sa。

ChromeにNoize2saを移植してみた

Google ChromeにNoiz2saを以前移植して公開してあったのですが、こちらでは書きそびれてたので、クリスマスというタイミングに書くことにします。

ABA GamesのSTG “Noiz2sa”をブラウザで遊べるようにしてみました。

20121224

Chrome ウェブストア – noiz2sa

 ChromeのNative Clientという仕組みを使っていて、これを使うと比較的簡単にネイティブのゲームをブラウザ上で動かすことが出来るようになります!

GamepadのAPIがうまく動かないので残念ながらゲームパッドでは動く動かないのですが、キーボードでならガリガリ動くのでJoyToKeyでも使ってやってみてください!…だったら普通にWindows版で遊ぶ?そ、そうですよね…。

特に何もしてないけどクロスプラットフォーム

NativeClientは、何もしなくてもクロスプラットフォームに対応していて、今回の拡張もLinux/Windows/MaxOSXで動きます。ちょうべんりー。ちなみに開発自体はLinuxでやってます。

NativeClientのしんどいところ

NativeClientはセキュリティ上の要請から、色々制限があります。普通に計算をさせる分には困らないですし、グラフィックやサウンドの出力も、NaCl Portsがあるお陰で普通に使う分には困りませんが、ファイルアクセスやネットへの接続などでは独自のライブラリを使わなければなりません。

今回ゲームということでネットワークは使っていないのですが、タイトルの「noiz2sa」のロゴ画像(ビットマップ)や弾幕の定義データ(XML)、BGMや効果音のファイルなど、比較的数は少ないもののファイルアクセスがあり、これに対処する必要がありました。

ファイルはすべてゲームバイナリ内に

Native ClientにはURLLoaderというクラスがあるので、これを使えば任意のURLの内容を取得できます。これをローカルファイルの代わりに使えば良さそうです…が、今回はゲームなのでローディングを避けたいのと、大した容量でもない(8MBくらい)なので、全部バイナリ内に入れてしまうことにしました。

具体的にいうと…

struct FileEntry{
const char* filename;
const size_t size;
const char* data;
};
extern const struct FileEntry gFileImages[];
extern const size_t gNumberOfFileImages;

Noiz2saNaCl/nacl/file_data.h at master ・ ledyba/Noiz2saNaCl ・ GitHub

というような構造体をつくって、

static const char ImageData[8810309] = [具体的なデータ>];
const size_t gNumberOfFileImages=96;
const struct FileEntry gFileImages[96] = {
{
.filename="boss/forward_3way.xml",
.size=818,
.data=&ImageData[0],
},
(ファイルのエントリをたくさん)
};

Noiz2saNaCl/nacl/file_data.c at master ・ ledyba/Noiz2saNaCl ・ GitHub

として全データを格納します。

これを読み書きするためのfopen、fread、fcloseなどの関数を独自に定義して

extern size_t nacl_ftell (FILE *file);
extern int nacl_fseek (FILE *file, size_t offset, int whence);
extern FILE *nacl_fopen (const char *filename, const char *modes);
extern size_t nacl_fread(void *ptr, size_t size, size_t nmemb, FILE *stream);
extern size_t nacl_fwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream);
extern int nacl_fclose(FILE *fp);
extern int nacl_feof(FILE *stream);
extern int nacl_ferror(FILE *stream);
extern void nacl_rewind(FILE *stream);
extern int nacl_fgetc(FILE *stream);
extern int nacl_fflush(FILE *stream);

最後にマクロで普通のfopenを乗っ取ります

#define fopen(n,m)  nacl_fopen(n,m)
#define fclose(f) nacl_fclose(f)
#define ftell(f) nacl_ftell(f)
#define fseek(f,o,w) nacl_fseek(f,o,w)
#define fread(p,s,n,f) nacl_fread(p,s,n,f)
#define fwrite(p,s,n,f) nacl_fwrite(p,s,n,f)
#define feof(f) nacl_feof(f)
#define ferror(f) nacl_ferror(f)
#define rewind(f) nacl_rewind(f)
#define getc(f) nacl_fgetc(f)
#define fgetc(f) nacl_fgetc(f)
#define clearerr(f) nacl_clearerr(f)
#define fileno(f) -1
#define fflush(f) nacl_fflush(f)

Noiz2saNaCl/nacl/storage.h at master ・ ledyba/Noiz2saNaCl

ソースコードを改変できるので別に乗っ取る必要はないのですが、NativeClientの元の記事がそういう感じで乗っ取ってたのでそうしときました。

ディレクトリ内のファイルを列挙するAPIであるreaddirなどもおんなじ感じで乗っ取っております。

この方法はGoogle先生謹製の記事を参考にしていて、ソースも一部拝借してます。Case Study: Porting MAME to Native Client – Native Client — Google Developers

さてどうしたものか

NativeClient、ファイルが絡むと一気にめんどくさくなります。既存の技術(Flashとか)を置き換えるには少し不便ですね。