2014-06-22

追記

TODO の後者の方はやった。3倍はやくなりました。前者の方はとりあえずレジスタって概念を導入してみて、少しだけはやくなりました。次で使う場合はレジスタっていうか Befunge のスタックに残しておけるんで、そういうことをすれば少しだけ速くなるはずですが、そんなとこはボトルネックでは無い気もするのでもういいやという結論に

2014-06-22

beflisp.bef と LLVM Befunge backend

https://github.com/shinh/beflisp

Lisp インタプリタを作りました。今度は Befunge で。

https://github.com/shinh/beflisp/blob/master/beflisp.bef

コードを見ればわかりますが、手書きは諦めました。前回の sed と違って Befunge は数値演算は素直に提供してくれてるので、アドレス計算なんかをするプリミティブが提供しやすいです。ただ、 Befunge-93 は文字列とか関数コールという概念が無いので、手動でフロー管理するのは地獄でしょうね…

ということで、 C で lisp を書いて、それを clang で LLVM bitcode に変換してから、トランスレータで Befunge に変換、という構成になっています。

実装

トランスレータは任意の C コードを Befunge に変換できるようなレベルには全然達していません。例えば型は全部 32bit 決め打ちです。内部実装知ってないとどういう C コードなら通るかとかわかりにくいでしょうし、内部実装知ってる私にもあまりわかってません。ていうかなんで動いてるんだろうっていう感じ。全体的に投げ槍な実装なんで。

LLVM bitcode からトランスレートされた Befunge コードってのは、あたりまえですが割とデバッグが大変です。しょうがないので小さな C プログラムを一つずつ動くようにしていく感じでやりました。あとデバッグしやすいように元に bitcode を実行しない領域に置いてあります。

大変だったのはまずブランチとかですかね。立体的にコード配置するのはデタラメに大変に決まってるので直線的に実行したいので。スタックトップが真ならスタックの2番目を採用、偽なら3番目を採用、ってことができるプリミティブを作ってそれをあちこちで使う感じにしました。ブランチといえば当然 PHI もダルいったらありゃしない。

LLVM のバックエンドの書く作法を調べるのが面倒だし、 LLVM のバックエンド用の共通基盤が Befunge みたいな素頓狂な実行モデルにうまいこと適合するとは思いがたかったので、 bitcode 読んでからは全自力です。レジスタアロケーションだけやってもらえたりするとラクに生成されたコードを小さくできるんですが…

機能としては前回の sed と同じはずです。前回のテストコードは全部パスしてますし、 FizzBuzz on Lisp on Lisp on Befunge も動いています。すごく遅くて、半分で 1 時間とかかかってますけど。

TODO

レジスタアロケーションをやるってのと、ブランチの高速化、ってのがあります。このふたつやればもう少し実用的な速度になるんでないかなぁと。

というのは、前者は、現状 SSA の結果は全部スタックに残していっていて、スタックがまあまあ遠いところにあるんでアクセスにかかる命令数が多いということがあり。

後者はもっとひどい話で、現状どこかで jmp や call があると、必ずプログラムの一番先頭まで戻ってから次に実行する場所を線型探索してます。そうでなくてちゃんと差分だけ動くようにすれば、近くへの jmp とかが劇的に速くなるかと思います。

あとは free が実装されてないってのがひどいんですけど、当然のことながら実装するとすごく遅くなっちゃうと思われるので、だるいかなあと。

まとめ

Befunge はまともな言語

2014-06-08

sedlisp.sed

https://github.com/shinh/sedlisp

Lisp インタプリタを書きました。 sed で。

https://github.com/shinh/sedlisp/blob/master/sedlisp.sed

README に書いた通り、それなりにややこしいプログラムも動く気がします。具体的には eval.l として、 eval の無いところで eval を実装しました。で、その上で FizzBuzz なんかが動きます。これはつまり S 式のパースは省略した Lisp のインタプリタと言って良いので、 sed で書かれた Lisp の上で Lisp が動いて、その上で FizzBuzz が動いてることになります。ちなみにもう一段かますことはできませんでした。 Ruby で書いた実装でも動かないので、 eval.l がとりあえず循環できない作りになってしまってるみたいですが、デバッグできないので何が間違ってるのかよくわかってません… (追記: id:Irori さんがなおしてくれました! FizzBuzz on Lisp on Lisp on Lisp on sed が動く!)

正直疲れたんで s/// 以外の sed script 書くのやめようかと思いますね…なんか途中から ruby で等価なプログラムを書いてテストしはじめたのですが、 ruby の実装は 1 時間もかかってないのに対して、 sed の方は 40 時間くらいはかかってるんでないかなーと思います。

あとは実装について

加減乗除

加算減算は何度か書いたのでやるだけ作業です。動作の説明は

http://shinh.skr.jp/slide/mederu/048.html

などにあります。

乗除はめんどくさいので Lisp で組み込み関数として書きました。 neg? という関数だけ sed で実装して、割り算の実装に使っています。

次に実行する場所

関数しか無ければ、中から実行すればいいので、最左にある、その中に括弧の無い括弧の組を実行すれば良いです。正規表現で書くと ([^()]*)

大変なのは special form というやつです。 if とか defun とかは、中を先に実行しちゃまずくて、外から実行していく感じになります。これは最左の括弧の組を一旦 @ に変換しておいて、 @ より左に special form があれば、そっちを先に実行、という方式でやりました。

 (+ 2 (if t (+ 3 4) 5))

みたいな式があると、 (if t (+ 3 4) 5) だけを取り出す必要があるわけですが、これも正規表現ってやつはご存知の通りネストした括弧の組を取り出すとかできないので、かなりめんどくさいです。

具体的には (if の中の括弧の組を @ で取り出していって、 (if の中に括弧が無くなれば @ を復元、というようにやりました。

この方式では defmacro の実装はありえないくらいめんどくさいことになります。当然実装してません。

スタック

次に実行する場所を切り出せたら、切り出した以外の場所をスタックに保存しておかなければなりません。これは以前にもやったことがあって、切り出した部分を @ に置換しておいて、その @ を含んだ式をスタックに置いておきました。

さっきの if 文なら

 (+ 2 @)

のようなものがスタックに積まれて、 (if ...) の評価が終わると結果を @ と置換して実行を続けます。

sed にはスタックなどという便利なものは無いんで、ホールドスペースの末尾に一行ずつ書いていくことにしました。

define と defun

define で変数を定義すると、ホールドスペースの先頭の変数を置く空間に書きます。

 (define foo 42)

は

 ;foo;42;

などと定義されます。

変数の展開は、変数一覧をパターンスペースに持ってきてから、正規表現の後方参照でやります。

 s/^\([^\n]*[ ()]\)\?\(\S\+\)\([ ()\n].*\n;\2;\([^;]*\)\)/\1\4\3/

というような感じで…と言ってもなんのこっちゃわからんかもしれませんが、

$ echo '(func foo)@;foo;42;' | sed 's/^\([^@]*[ ()]\)\?\(\S\+\)\([ ()@].*@;\2;\([^;]*\)\)/\1\4\3/'

などとすると foo が 42 に置換されるので、そういうもんです。 (\n は @ に置換しておきました)

defun は単に define と lambda のシンタクスシュガーです。

quote と lambda

このコードの全域で値の区切りとして空白を使っているので、 quote や lambda にある空白は厄介、というかそのままでは全く取り扱えないです。あと括弧も残ってると絶望的です。

しょうがないので、内部的に括弧と空白を別な文字に置換して取り扱ってます。 (quote (4 5)) は [4,5] に、 {lambda_{n_m}_{+_n_m}}$ に置換してあります。 lambda の末尾についている $ は、 lambda を関数適用する時に lambda が引数として渡されたりすると大変なことになるので、ターミネータが必要だと気付いて足したものです。

lambda の適用は、特に引数の処理はだいたい変数の展開と同じです。

print 関数はこのへんをそのまま出力するので、

 (print (lambda (n m) (+ n m)))

などとすると内部表現が見られます。

まとめ

他にもいろいろハックでごまかしてる部分などがあって、大変でした。 evalify した sort とかよくうごいてるなーという感じ。

2014-06-01

失敗ロック例いくつか

なにかあまりスレッドとか得意でない人のコードを見ていて、いくつかダメな予感がするパターンがあるよね、ってことで適当に集めてみました。どれもこれも小さな例にすると、こんなミスしねーよ、って感じなんですけど、複雑なコードの中にあると結構ミスるもんかな、と。私自身マルチスレッドはたいへん苦手で、実際私がやらかしたケースもいくつか。

ひとつめ: ロック順序逆転

// そこらじゅうで確保されてるグローバルなロック
pthread_mutex_t g_mu = PTHREAD_MUTEX_INITIALIZER;

// このクラスを使うところは全域 g_mu でロックされてるとします
class C {
public:
  C() {
    pthread_mutex_init(&mu_, NULL);
  }
  void doSlowOperation() {
    pthread_mutex_lock(&mu_);
    // この処理は重いから先にロックを解放しておこう!
    pthread_mutex_unlock(&g_mu);
    // Slow operation.
    pthread_mutex_lock(&g_mu);
    pthread_mutex_unlock(&mu_);
  }
private:
  pthread_mutex_t mu_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock1.cc

このコードは thread A が出口付近で g_mu を取ろうとする時に、他のスレッドが入口付近で mu_ を確保しにいくと、デッドロックします。

教訓としては、複数ロックがネストする時はとりあえずデッドロックを心配すると良い気がします。ネストする場合は、二つのロックを取る順序は必ず同じ順序で取るようにするべき。ロック1とロック2がある時に、ロック1,2両方取られている時間と、ロック1だけが取られている時間と、ロック2だけが取られている時間があると、まぁだいたいやばいです。

まぁ、この場合は本当に g_mu を外さにゃいかんのかをまず考えた方がいい気がします。あちこちで確保されてるロックが一つだけ、って状態は性能に問題が出るまでは割と安心な状態です。

ふたつめ: 同じ変数に別のロックを使う

// そこらじゅうで確保されてるグローバルなロック
pthread_mutex_t g_mu = PTHREAD_MUTEX_INITIALIZER;

// このクラスを使うところは全域 g_mu でロックされてるとします
public:
  C() {
    pthread_mutex_init(&mu_, NULL);
  }
  void doSlowOperation() {
    // この処理は重いから先にロックを解放しておこう
    // ひとつめではデッドロックしてしまったから先に外しておく
    pthread_mutex_unlock(&g_mu);
    pthread_mutex_lock(&mu_);
    for (int i = 0; i < 5; i++)
      vals_.push_back(i);
    pthread_mutex_unlock(&mu_);
    pthread_mutex_lock(&g_mu);
  }
  void doFastOperation() {
    // g_mu が取られてるから大丈夫!
    vals_.push_back(42);
  }
private:
  pthread_mutex_t mu_;
  std::vector<int> vals_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock2.cc

doSlowOperation を見る限り、 vals_ は mu_ で守られてるべきっぽいですが、 doFastOperation では g_mu に頼ってます。普通に race condition があるので、この場合普通にクラッシュしました。

教訓としては、なにかロックしてるから大丈夫、ではなくて、適切なロックを使ってるかどうかを常に意識すると良いです。どのロックに守られてるか、ってのは C++ の所有権並に重要なことだと思うんで、 mutex をメンバに持たせる時は、その mutex がどの変数をガードするかどうかをコメントするようにするとやや良い気がします。

みっつめ: ロック順序逆転してない?

class C {
public:
  explicit C(int val) : val_(val) {
    pthread_mutex_init(&mu_, NULL);
  }
  int add(C* c) {
    // 必ず mu_ => c->mu_ の順序でロックするよ!
    pthread_mutex_lock(&mu_);
    pthread_mutex_lock(&c->mu_);
    int r = val_ + c->val_;
    pthread_mutex_unlock(&c->mu_);
    pthread_mutex_unlock(&mu_);
    return r;
  }
private:
  pthread_mutex_t mu_;
  int val_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock3.cc

C::add はぱっと見首尾一貫した順序を守ってるように見えるんですが、 this と引数 c が逆転すればひとつめの例と同じで、ロック順序が逆転しているのでデッドロックします。

具体的には、 c1->add(c2) と c2->add(c1) があったとして、前者が c1 のロックを取る→後者が c2 のロックを取る、という順序で起きると次のロックはどちらも取れません。

これはこのクラスの使い方によっては、問題無い場合もあります。必ず一定の法則に従って add のレシーバと引数を選んでいれば大丈夫で、たぶん、

assert(c1 != c2);
c1 < c2 ? c1->add(c2) : c2->add(c1);

とかしていれば大丈夫…な気がします。自信がないですが。

がまぁ素直になんとかした方がいいと思います。パフォーマンスに問題が無ければ mu_ を static にしてしまうのがラクチンです。

よっつめ: 狭義のレースは無いのだけど

class C {
public:
  explicit C() {
    pthread_mutex_init(&mu_, NULL);
  }
  void setVals(std::vector<int> vals) {
    pthread_mutex_lock(&mu_);
    vals_ = vals;
    pthread_mutex_unlock(&mu_);
    // Update the cache.
    setSum(calcSum());
  }
  int getSum() {
    pthread_mutex_lock(&mu_);
    int sum = sum_;
    pthread_mutex_unlock(&mu_);
    return sum;
  }
  void setSum(int sum) {
    pthread_mutex_lock(&mu_);
    sum_ = sum;
    pthread_mutex_unlock(&mu_);
  }
  void check() {
    pthread_mutex_lock(&mu_);
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    assert(sum == sum_);
    pthread_mutex_unlock(&mu_);
  }
private:
  int calcSum() {
    pthread_mutex_lock(&mu_);
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    pthread_mutex_unlock(&mu_);
    return sum;
  }
  pthread_mutex_t mu_;
  std::vector<int> vals_;
  int sum_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock4.cc

vector を持っていて、その合計値がよく欲しくなるので、合計値をキャッシュとして持っておく、というような想定で書かれたコードです。ロックが一つしか無くて、 vals_ も sum_ も mu_ にしっかりガードされてるので安心…ではないです。

たしかに vals_ や sum_ に同時アクセスするケースは無いのですが、 sum_ が vals_ の合計でない値になってしまう場合があります。というのは setVals が calcSum や setSum でいちいちロックを外してしまっているので、例えば、 calcSum が 30 という結果を返す→ setVals が別スレッドで呼ばれて sum_ が 50 にアップデートされる→元のスレッドに戻って sum_ に 30 を代入する、のような。

この手のレースはなんと呼ぶのか知らないのですが、一つの変数へのアクセスはちゃんとガードされてるので、 thread sanitizer なんかの race detector にかからず、 annotation をしっかり書いても見つけてくれないはずです。 QuickCheck なんかがこういうのを探してくれる、って話だったような。

この手の、メンバ変数 A が○○なら B は必ずこれを満たさなければならない…みたいな条件があるクラスはマルチスレッドでなくてもあまり嬉しくないですね。パフォーマンスに問題なければそもそもキャッシュしたくないわけですが、まぁこの例ではパフォーマンスに問題があったから calcSum を private に移してキャッシュすることにしたんだなぁ、という流れが透けて見える感じです。 check みたいな関数を用意してやたら呼びまくるのは安心感があっていい方法ではあると思います。

ちなみに修正例:

class C {
public:
  explicit C() : sum_(0) {
    pthread_mutex_init(&mu_, NULL);
  }
  void setVals(std::vector<int> vals) {
    pthread_mutex_lock(&mu_);
    vals_ = vals;
    // Update the cache.
    sum_ = calcSumLocked();
    pthread_mutex_unlock(&mu_);
  }
  int getSum() {
    pthread_mutex_lock(&mu_);
    int sum = sum_;
    pthread_mutex_unlock(&mu_);
    return sum;
  }
  void check() {
    pthread_mutex_lock(&mu_);
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    assert(sum == sum_);
    pthread_mutex_unlock(&mu_);
  }
private:
  int calcSumLocked() {
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    return sum;
  }
  pthread_mutex_t mu_;
  std::vector<int> vals_;
  int sum_;
};

こういう hogehogeLocked みたいなのは、こういうクラスだとよく必要になる気がします。

いつつめ: rwlock

最後ふたつは mutex よりは使用頻度が低いもので。

class C {
public:
  C() : val_(3) {
    pthread_rwlockattr_t attr;
    pthread_rwlockattr_init(&attr);
    pthread_rwlockattr_setkind_np(
        &attr, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
    pthread_rwlock_init(&mu_, &attr);
    pthread_rwlockattr_destroy(&attr);
  }
  int calcSomething() {
    pthread_rwlock_rdlock(&mu_);
    // getVal の中で同じロックを取るけど、 reader lock だから大丈夫!
    int r = 42 + getVal();
    pthread_rwlock_unlock(&mu_);
    return r;
  }
  int getVal() {
    pthread_rwlock_rdlock(&mu_);
    int r = val_;
    pthread_rwlock_unlock(&mu_);
    return r;
  }
  void setVal(int val) {
    pthread_rwlock_wrlock(&mu_);
    val_ = val;
    pthread_rwlock_unlock(&mu_);
  }
private:
  pthread_rwlock_t mu_;
  int val_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock5.cc

以前書いた話です。 calcSomething の中でヘルパ関数 getVal を呼んでいるのは、 glibc のデフォルトの pthread_rwlock_t なら大丈夫なんですが、この場合 writer starvation を回避する rwlockattr をつけてるのでデッドロックしてしまいます。また、 pthread の実装によってはデフォルトのでデッドロックするそうです。

writer starvation とは、 reader がたくさんいて、一つのロックに常に複数の reader lock を reader が取ってしまっていて、全然 writer がロックを取れない状況を言うそうです。これを回避するために、 writer が待ってる時は新規 reader を受け付けない、という処置がされているロックがあって、まぁこれつけないとパフォーマンス上使いものにならんケースが多いようです。

ただ、このタイプの rwlock を使うと、 thread 1 が calcSomething の reader lock を取る→ thread 2 が setVal の writer lock を待ちはじめる→ thread 1 が getVal の reader lock を取ろうとするが、 writer が待ってるので取れない、という形のデッドロックになります。

教訓としては必要がなければ rwlock をそもそも使わない、ってのがあるかと思います。あとまぁ普通に reader lock だろうと nest させてると良くないなっていう。普通のロックに変えれませんし。