clearstackの話

https://turingcomplete.fm/19#t=26:39 で僕のやったことに言及してくれて、「使ったスタックを消すなにかを浜地が作ったが、それは全く公開されていない」という趣旨の事が言われていました。でも実際のところなんか書いたけど、単に誰も興味を持たなかったというだけのことでした。

http://shinh.hatenablog.com/entry/20130728/1374990526

実際はclang pluginで、かつすごく適当にでっち上げただけで、効率は完全度外視だし正しく動いてるんだかもよくわからない、って感じでした。クラッシュはしなかったくらいの何か。当時の記述はすごい適当ぽいので、2点書いておきます。

当時のモチベーション

保守的GCが「やや病的なケースでポインタに見える整数値の参照先を残してしまう」てのはよく聞くわけですが、Rubyのバグかなんかで見たのは違うケースで、実際に過去にポインタだったが、もう使ってないマシンスタックに残ってるものが解放されない、というような話でした。

具体的にCレベルで考えると、VMのループてのはおおむね

switch (op) {
  case OP_X: {
    VALUE x = ...
    なんかする...
  }
  case OP_Y: {
    VALUE y = ...
    なんかする...
  }
}

とかそういう感じになっているわけです。ここで VALUE てのは tagged-pointer ですが、まあ要はポインタです。 VALUE x とか VALUE y ですが、少なくとも当時の GCC は x と y を同じスタックに割り付けるということはせず、かつ VM ループを処理する関数が結構複雑な関数だったこともあり、かなりのローカル変数がレジスタだけでは処理できるずスタックに割り付けられていたと記憶してます。実際手元で vm_exec_core を見てみると

0000000000015050 <vm_exec_core>:
   15050:       41 57                   push   %r15
   15052:       41 56                   push   %r14
   15054:       41 55                   push   %r13
   15056:       41 54                   push   %r12
   15058:       55                      push   %rbp
   15059:       53                      push   %rbx
   1505a:       48 8d 1d 00 00 00 00    lea    0x0(%rip),%rbx        # 15061 <vm
_exec_core+0x11>
   15061:       48 81 ec 28 01 00 00    sub    $0x128,%rsp

とか言ってまして、296B のマシンスタックを確保しているわけです。

でもまあスタックが上がったり下がったりしてれば、そのうちマシンスタックは適宜再利用されて、たまたま残ってた VALUE とかも消えたりすると思うんですが、その時問題になってたと記憶しているのは

def init_server
  ... なんだか複雑な処理をして初期化をして、 serving に必要なデータを集めてきて、
  ... データの大部分は捨てるが serving に必要なものだけを残す
end

def execute_server(sock, data)
  while true  # 二度と戻らない
    ... serving する
  end
end

def run_server(data)
  sock = ...ソケットとか作る
  execute_server(sock, data)
end

data = init_server
run_server(data)

みたいな、単純化するとこういうケース。 init_server はなんだか複雑な処理をするので、マシンスタック上に不要になってるはずのポインタを残し、 run_server は init_server とは別のマシンスタック領域を使ったためにそのポインタが残っていて、それで execute_server 呼んじゃうので、 init_server のためのマシンスタックは未来永劫初期化されない、というような。

当時はやや場当たり的に、Rubyのこの部分を別の関数に分離したらよくなったよ、とかそういうことが報告されていました。現段階でどうなってるかは知らないです。

Boehm GC

は、この手のスタックに残ったポインタを定期的に適当なヒューリスティクスと乱数的なタイミングで消すってことをやっていたと思います。たぶんこれ

https://github.com/ivmai/bdwgc/blob/master/misc.c#L332

スタックが頻繁に上がり下がりしてるようなプログラムではすごく有効なはずで、なるほど GC というのはミューテータのアクセスパターンにひどく依存する難しいものだなぁと思った記憶があります。ミューテータ依存というと、他にはコンパイラとかも GC 泣かせだと聞いたことがあります。最初にがばっとメモリ確保して、その部分はあまり解放しないけどその後も確保と解放が続くとかなんとか。まあそれは世代別が緩和しそうな話ですね。

もとの話に戻して適当なタイミングでスタックを綺麗にする緩和は、当然ながら現在のスタックポインタより深いところにあるスタックは消しちゃいけないので、さっきの Ruby の例のように、マシンスタックの金輪際書き換えが起きない部分に残ってるポインタライクなものに対しては無力なのです。

いう2点がモチベーションだったと思います。

ビット演算クイズを解いた時の話

http://herumi.in.coocan.jp/diary/1804.html#13

を解いた時の話。光成さんは実験的に解かれたようだったんですが、割と理詰めで解けたので、思考過程をダンプしてみます。元のコードは

int calc(int a, int b, int s) {
    const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
    assert(0 <= s && s <= 16 && && 0 <= b && b < a && a < Q * 4);
    int n = 0;
    for (;;) {
        if (a < Q2) {  // A
            n = n * 2;
        } else if (b >= Q2) {  // B
            n = n * 2 + 1;
            a -= Q2;
            b -= Q2;
        } else if (b >= Q && a < Q3) {  // C
            a -= Q;
            b -= Q;
        } else {  // D
            break;
        }
        a = a * 2 + 1;
        b = b * 2;
    }
    return n;
}

という感じ。

ビット演算はゴルフと似たところがあって、まず「このコードはもっとシンプルにできる」と信じ込む必要があって、これが結構難しいと思います。今回はクイズという形で出題されたのでこの点はクリアされてて、シンプルになるという確信が無いのにたどりつかれた光成さんはすごいなあ……と思います。

しょうもない書き換え

とりあえず真ん中の4分岐 (以降上から ABCD と呼ぶ) を減らしたい。とりあえず上2つを削るとすると…と考えて

int calc(int a, int b, int s) {
  const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
  assert(0 <= s && s <= 16 && b < a && a < Q * 4);
  int n = 0;
  for (;;) {
    if (a < Q2 || b >= Q2) {
      n = n * 2 + ((a & Q2) >> (s + 1));
      a -= a & Q2;
      b -= a & Q2;
    } else if (b >= Q && a < Q3) {
      a -= Q;
      b -= Q;
    } else {
      break;
    }
    a = a * 2 + 1;
    b = b * 2;
  }
  return n;
}

という感じになった。2つの分岐を一緒に扱って、 a & Q2 が 0 なら分岐A、 0 で無ければ B という感じで分けてみた。とかやってると3つ目の分岐も結局 a, b の値域がちょうどいいところ (Q = 1 << s の倍数の地点) で分岐してるわけで、整理してみるべきだな、と思う。

分岐を整理する

a も b も常に 0 以上でかつ Q*4 以上になることはない。分岐は Q より小さいか、 Q*2 より小さいか、 Q*3 より小さいか、だけで行なわれてるので、分岐に対して a と b が持ちうる状態はそれぞれ4つ。 a/Q を an として b/Q を bn として、分岐 ABCD のどれを選ぶべきかを整理すると

bn\an 0 1 2 3
 0    A A D D
 1    N A C D
 2    N N B B
 3    N N N B

となる。 N というのはありえない組み合わせで、これは常に b < a であることから。まず D の分岐はループを止めるという特殊な動作をするので、先に処理してやる。この条件は少し考えると

  if (an - bn >= 2)
    break;

でうまくあらわせる。 D を忘れてよいという気持ちで上の表を眺めると、分岐 ABC はもっとシンプルに a と b がそれぞれ Q*2 より小さいかだけで表現できる。 a/Q/2 を ab として b/Q/2 を bb とすると

bb\ab 0 1
 0    A C
 1    N B

これだけの話だ。 ABC それぞれの分岐で起きるべき変化で共通でないものは

• A: n = n * 2
• B: n = n * 2 + 1 ; a -= Q * 2 ; b -= Q * 2
• C: a -= Q ; b -= Q

n から考えていくと、 n を 2 倍しなければならないのは A, B のケースでこれは (ab ^ bb ^ 1) で表現できる。その後 n に 1 を足さなければならないのは B だけで、これは単に bb で良い。というわけで n は以下のように分岐なく処理できる。

  n <<= ab ^ bb ^ 1;
  n |= bb;

a, b は A, B, C の時にそれぞれ 0, Q * 2, Q を引けば良い。なんとでもなるけど Q << bb で B の時だけ Q * 2 にすることができて、 (Q << bb) * ab とかすれば A の時だけ 0 にすることができる。というわけで a, b の変化は

  int sub = (Q << bb) * ab;
  a -= sub;
  b -= sub;

などとシンプルになった。以上まとめると

int calc_mine1(int a, int b, int s) {
  const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
  assert(0 <= s && s <= 16 && b < a && a < Q * 4);
  int n = 0;
  for (;;) {
    int an = a >> s;
    int bn = b >> s;
    int ab = an >> 1;
    int bb = bn >> 1;

    if (an - bn >= 2)
      break;

    n <<= ab ^ bb ^ 1;
    n |= bb;
    int sub = (Q << bb) * ab;
    a -= sub;
    b -= sub;
    a = a * 2 + 1;
    b = b * 2;
  }
  return n;
}

ループ内の分岐は無くなったけど、まだこの計算の本質がなんなのかとかがわかるような形ではない。もうちょっとシンプルにしないとなあと考える。

状態遷移を把握する(より道気味)

an, bn の組み合わせが10種類あって、うち3種類はループから脱出するけど、残り7種類はもう一回以上ループすることになる。それぞれの状態から、次の an, bn が何になるかを考えてみる。というのは、 an, bn になされてる演算は Q か Q*2 を引いてから2倍なり2倍プラス1する、ってものなので、割とシンプルな状態遷移をするはずなんです。

分岐 A は a, b を2倍なり2倍プラス1するだけなので、遷移前の an か bn が 0 なら次の an/bn は 0 か 1 になり、遷移前の an/bn が 1 なら次の an/bn は 2 か 3 になる。

分岐 B は2倍する前に Q*2 を引くので、 an/bn が 2, 3 ならそれぞれ 0, 1 に変換してから、分岐 A と同じ遷移をする。

分岐 C は an == 2 かつ bn == 1 の時だけ。まず Q を引くので、 an == 1 かつ bn == 0 になってから 2 倍なので、 an は 2, 3 のどちらか、 bn は 0, 1 のどちらかになる。

まとめると

• <元のan>, <元のbn> => <次のanの候補>, <次のbnの候補>
• 0, 0 => (0, 1), (0, 1) (A)
• 1, 0 => (2, 3), (0, 1) (A)
• 1, 1 => (2, 3), (2, 3) (A)
• 2, 2 => (0, 1), (0, 1) (B)
• 3, 2 => (2, 3), (0, 1) (B)
• 3, 3 => (2, 3), (2, 3) (B)
• 2, 1 => (2, 3), (0, 1) (C)

うーん、だからどうした？と思うのですが、 (2, 3), (0, 1) に遷移した場合、 C の分岐に入るかループ終了の2択で、かつ C の分岐は (2, 3), (0, 1) に遷移するので、一度 C に入ると出てこない、ということがわかります。

さらに都合が良いことに、 C は返り値であるところの n を変更しないので、なんのことはない、 C は D 同様即座にループを出て良いということがわかります。となると分岐のテーブルは

bn\an 0 1 2 3
 0    A A D D
 1    N A D D
 2    N N B B
 3    N N N B

で良いことがわかって、これは ab/bb だけで十分に表現できるので

bb\ab 0 1
 0    A D
 1    N B

と最初からこれだけやれば良いとわかります。

分岐Cを消す

以前のコードから C の分岐用のコードを消していきます。まずループ終了条件

 if (an - bn >= 2)
   break;

は、 ab != bb の時に終了すれば良いので、例えば

  if (ab ^ bb)
    break;

となり

  n <<= ab ^ bb ^ 1;
  n |= bb;

は、 n は 常に 2 倍すれば良く、2行目はそのままで

  n <<= 1;
  n |= bb;

となり、 a, b については

 int sub = (Q << bb) * ab;
 a -= sub;
 b -= sub;

だったのですが、単に B の分岐の時だけ Q * 2 を引く、としたいだけなので

 int sub = (Q << 1) * ab;
 a -= sub;
 b -= sub;

とすれば良いです。まとめると

int calc_mine2(int a, int b, int s) {
  const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
  assert(0 <= s && s <= 16 && b < a && a < Q * 4);
  int n = 0;
  for (;;) {
    int ab = a >> s + 1;
    int bb = b >> s + 1;

    if (ab ^ bb)
      break;

    n <<= 1;
    n |= bb;
    int sub = (Q << 1) * ab;
    a -= sub;
    b -= sub;
    a = a * 2 + 1;
    b = b * 2;
  }
  return n;
}

a, b に起きていることを考える

 int sub = (Q << 1) * ab;
 a -= sub;
 b -= sub;

について考えると、 B の分岐の時だけ Q * 2 を引いていて、 B の分岐というのは a, b が共に Q * 2 以上の時であり、そうでない時、つまり A の分岐というのは a, b が共に Q * 2 より小さい時です。

となるとここでやってる処理というのは、 Q * 2 が 1 << (s + 1) であることを思い出すと、 Q * 2 - 1 でマスクを取る、つまり下位 s bits より上の bit を捨てているだけです。つまり

  const int QM = (1 << s + 1) - 1;
  a &= QM;
  b &= QM;

まとめると

int calc_mine3(int a, int b, int s) {
  const int QM = (1 << s + 1) - 1;
  int n = 0;
  for (;;) {
    int ab = a >> s + 1;
    int bb = b >> s + 1;
    if (ab ^ bb)
      break;

    n <<= 1;
    n |= bb;
    a &= QM;
    b &= QM;
    a = a << 1 | 1;
    b = b << 1;
  }
  return n;
}

というようなコードです。

ループいらなくね？

上のコード、 a と b に対して、 s + 1 bit 目の値によって分岐して、 s + 1 bit 目を捨てて、 2 倍してる。要するに上のビットから順にチェックしていってるだけなんで、 a, b をいじくる必要は全くないです。例えば

int calc_mine4(int a, int b, int s) {
  int n = 0;
  for (s++;; s--) {
    int ab = (a >> s) & 1;
    int bb = (b >> s) & 1;
    if (ab ^ bb)
      break;

    n <<= 1;
    n |= bb;
  }
  return n;
}

としても良い。 ab ^ bb は a > b という条件から、必ずどこかのビットで 1 になるはずなんで、終了条件はこれで良いです。で、こうなっちゃうと「n は ab と bb が共通してる限りビットを上から立てていって、 ab と bb が異なった時点で終了」というものなので、 ab と bb が異なる地点を探して、そのぶん a を右シフトすれば望みのものが得られる……ということで

int calc_mine(int a, int b, int s) {
  return a >> (32 - __builtin_clz(a ^ b));
}

となります。 __builtin_clz は左から0の数を数えるやつです。

お天気プロコンと圧縮アルゴリズムについて

https://beta.atcoder.jp/contests/wn2017_1/standings

むっちゃ僅差で2位。残念。この212点差がどのくらい僅差かというと、最後にいじってたところにもう2行変更を入れることを思いつけていれば、軽く2000点は差がついて勝ててたと思いますし、そうでなくても後30分もあれば実装できた細かいヘッダの圧縮で逆転できた量です。自分に悔しがる気持ちというのがこれほど残ってたのか、と驚くほど悔しいです。でも勉強になったし楽しかったです。

やったことを書きつつ、そもそも圧縮アルゴリズムについて、私としては感動的だった知見を得られたので、書いてみようかと思います。

今回のコンテストは、チャンネル1つの(RGBじゃなくてグレースケールだと思えば良い)画像を64枚を可逆圧縮するというものでした。その64枚の画像は同じ座標について光の波長と時間を変えて気象衛星が観測したものなので、互いに相関があり、相関を利用しない普通の画像圧縮だけでは上位の成績にはなかなか追いつかないと思っています(後述しますが汎用画像圧縮で7位は取れていたと思います)。

次のピクセルを予測する

圧縮についてある程度の知識があれば、色んな情報から次のピクセルの値を予測して、当然予測は外れるので外れた分についてエントロピー符号、という方法を考えるかと思います。エントロピー符号はデータに偏りがあればあるほど圧縮率が上がるため、問題のドメインについての知識を利用して、データを偏らせることができれば圧縮率が高くなります。例えば、普通の画像は一般的に直前のピクセルと近い値を持っていると考えられるので、直前のピクセルと次のピクセルの差分を保存すれば値が0に近い値に偏るので良いのです。すぐ左のピクセルだけでなく、左と真上のピクセルの平均値であるとか、付近のピクセルを適当なわりあいで混ぜた数値であるとか、予測の精度を上げる方法は色々と考えられます。

今回の問題の場合、同じ波長を別の時間に観測した画像や、同じ時間に違う波長を観測した画像からもパラメータを拾ってくることができて、さらにこの予測の精度を上げることができます。これは、パラメータが複数あって一つの値を推定するので、普通にある種の機械学習と言えます。

私が使った方法は、参照画像からピクセルの値を推定して、その推定した値がさらにどれだけ現実とずれているかということを近傍のピクセルから推定する、という方法と、参照画像と近傍の両方からピクセルを推定する、という両方のアプローチを、かつ色んな参照画像に対してやってみて良かったやつ、という方法です。機械学習で忌み嫌われていると思っている ensemble 的な話です。本当は一気に推定する方法だけで行きたかったのですが、一気推定は当初の時間制限だと割とギリギリだったのと、参照画像との相関が低い画像で成績が悪い(特に全体の半分以上を占める一番大きい画像4枚で良くない)ので、最後まで残ってメンテナンスを困難にしていました。

実際のモデルは、単にパラメータ(つまり近傍や参照画像のピクセル値)を重みつけて線形和したもので、重みの推定は単なる最小二乗法でやりました。パラメータの二次以上の項を入れるのはほぼ逆効果で、まあそれは冷静に考えるとピクセルの値を2つかけ算した値に意味があるとは思えないわけですが、もう少し複雑なパラメータを入れることはありえたかと思います(例えば med(x,y) のような)。

最小二乗法は微分可能なおかげで解析解があって、お手軽高速に計算できるというのは大変良いのですが、後段のエントロピー符号的には無視しても良いはずの外れ値に優しい、という特性を持っているので大変よろしくないという認識でした。なるべく多くのピクセルをゼロ付近の極めて近いレンジの値に押し込むことによって圧縮したい、というモチベーションなので、稀に予測が大幅に外れる値がどういう値を持っているか、はたいして興味がないのです。実際ぐぐってみると、ロバストな最小二乗法というのが色々あって、やってみると良かったりもするのですが……実装が面倒だったり遅かったり、そもそもここがよくなることで得られるメリットが少なかったりとあって、放棄しました。要研究。

さてこの線形和のパラメータは画像の位置によって多少違うはず、ということで適当に大きめのブロックに分割したりしています。また、余分にパラメータを保存することを考えると、ほんの少しの差ですが、参照画像のピクセルの値によって使うパラメータを切り替えたりもしています。

予測から外れたぶんをエントロピー符号にかける

で、予測からのずれの量をエントロピー符号にかけることになります。エントロピー符号というやつは、ハフマン符号が一番有名で、例えば0012というデータを圧縮するなら、0は1と2よりよく出てくるので"0"という1ビットで表現して、1と2は"10"と"11"を使って表現しよう、というものです。ハフマン符号では各文字を整数ビットでしか符号化できませんが、算術符号やその一種のレンジコーダでは概念的に小数ビットを割り振ることができる……ような感じです。出てくる文字の確率分布で割り当てるビット数を決めるわけですが、その確率分布を動的に変えるものがadaptiveなやつで、ヘッダなどに確率分布を埋める必要がない、データの特徴の変化に対応できる、などの良いところがあります。ですが、何故か私は最終日前までadaptiveなやつを使うことを考えてなかったのでadaptiveじゃないやつを使ってます。まあadaptiveなやつはそれはそれで不利なところもあると思います、たぶん。

これ以上偏りが顕在化できない状態になったデータは、ハフマン符号でだいたい理論限界寸前まで圧縮できます。レンジコーダだとさらに進んで、まあもう理論限界だろってとこまで行きます。でこの理論限界てのがシャノンの限界というやつですね。となるとやること無さそうな気がするのですが、やれることがあります。前段で適当に予測したくらいではまだまだ偏りが顕在化しきっていないのです。

残ったデータは、まあおおむねゼロに近いところに頑張って叩き込まれてはいるのですが、部分部分で見ると、うまい具合にゼロ近辺に集まっていてくれているところと、予測器が苦戦して値がバラけまくっているところがあります。参照画像も現画像もほとんどデータが無くて動きが無いところとかは、ゼロ近辺の値に短いビット列を割り当てても良いし、逆に動きが激しいところはもう少しまんべんなくビット列を割り当てないといけません。

というわけで、画像をブロックに区切った上で近くの予想からのズレの量に応じて、使うレンジコーダを分けています。近辺の予想からのズレで使いわけるのは、近辺がズレてなければ次の値もあまりズレてないだろうという仮定があり、逆に近辺がズレているのなら次の値もゼロから遠い値の可能性が高いだろう、ということからです。これは私の理解ではLZMAが似たようなことをしているはずです。

区間で区切るのもまたこういう分類の効果を発揮してくれるというわけです。私の場合、単にゼロからのズレっぷりの平方根の和で得点をつけて、その得点が高いものほどバラけたデータに使う符号器、というようになっています。二乗和だとさっきも書いた通り外れ値に従ってしまうため、絶対値どころか平方根くらいが良いようでした。

圧縮 == 機械学習

で、なんかこういうことをやっていると、まるで機械学習なわけです。前段はいくつかの値から次のピクセルを予測する回帰をやっていて、後段は似た素性のデータには同じエントロピー符号器を選択するように、データをなんとなく分類するわけです。回帰と分類てモロに機械学習ですよね。

このコンテストの最初の頃は、「うーんこの最初二乗法で予測するとかなかなか面白いアイデアじゃないの？」とか思って、ぐぐってみると10年以上前のどうでも良さそうな論文が出てきます。まあ私が考えるようなことは普通に誰でも考えるよな、と思ってました。

そのうちに「これなんか本当に機械学習そのものじゃないの？そういえばオートエンコーダとか割と初歩的な深層学習よね」とか思いはじめてきました。で、そういうワードでぐぐってみると、色々と出てきます。そんなこんなしていて気付いたのが、FLIFというデータフォーマットで、これは実際圧縮が難しいデータに関しては私の圧縮といい勝負をするレベルの汎用圧縮でびっくりしました。それで特に感銘を受けたのが、FLIFの説明スライドでした。

http://flif.info/slides/FLIF_ICIP16/assets/player/KeynoteDHTMLPlayer.html#36

特にこの上記の KEY INSIGHT というページでは、モロに「Compression = Machine Learning」と言っていて、そうだよそう、その通りなんだよ、と思って感動しました。その次の "If you can (probabilistically) predict/classify,
then you can compress" も、まさにその通り、という感を受けました。しかし今にして思うと別に感動的でもなんでもなくて、当たり前だよなあという気がしてきてしまうんですけどね。最近の圧縮ではニューラル使うのもあるようですし。まあこの「なるほど！」→「当たり前じゃん」のプロセスを成長ということにしたいです。

機械学習といえば特徴量をプロが頑張って自力抽出、というのはオワコンで、なるべく特徴量も含めてメタな学習をするようなモデルを選ぶというのが主流という理解で、その現在での完成形の一つが深層学習という感じだと思います。FLIFでは深層学習では無いものの決定木を使って使うべき符号器を選んでるようです。

2週間ほどあれこれと人間の直感を駆使して特徴量を探しては圧縮率に一喜一憂する、という全くスケールしない(けど実は結構楽しい)作業に従事していた私としては、この知見には実になるほどなあというところで、最初からこの知識があれば、もっとadaptiveなアプローチを最初から指向していた(そしておそらく大失敗していた)ように思います。何故失敗するかというと、この手のマラソンでは最終的には一般的すぎる解より人間全力チューンが勝ちがちという経験則があるからです。ただ実際問題としてパラメータ増えすぎてコード整理や調整をしきれなかったという面があって、実際最後の方はパラメータ調整だけが実質的な伸びしろだったので、反省点とも言えます。

まとめ

楽しかった、勉強になった、しかし本当に悔しい

Deep Learning Acceleration 勉強会

https://connpass.com/event/64632/

すごく面白かった。最近こういう会に行って感心することは多いのだけど、しかしなんか書きたいと思うレベルになかなか来ない、まあそれなりに年喰ったしな、とか思ってたんですが。低レイヤとか、自分がある程度既に知ってるところの話を聞くのも楽しいけど、自分が最近勉強してて理解しはじめたことの話を見聞きする方が楽しいよねえということかと思いました。まさににわかほど語りたがる現象で、実際懇親会とかで間違ってること結構言ってそうな気がする。

ジャンルとして、他のCSのジャンルとかと違って、深層学習はとにかく論理的に確定できない話が多くて、あの論文はあやしいなあ、あれは説得力あるなあ、というような、口コミベースの情報が回してる面が、良くも悪くもあるのかなあ、という印象を持っています。

つーわけで口コミレベルの適当なことを、以下、書きます。(定型句)間違ってることが普通にいっぱいあると思います。(定型句)所属企業とは関係なく勝手に書いてます。定型句と書いたけどグーグルとしての感想では本当にないです。ちなみに僕はRNNしかいじったことないです

モデルアーキテクチャ観点からの高速化

僕はこれとても興味があったドメインだったので、早速すごい俺得と思いながら聞いてました。 factorization, squeeze, pruning とかの話の一部は自分でも試したことがあったのですが、自分のやった範囲ではうまくいかなかったという感想です。僕なりの考えを箇条書きにすると

• このジャンル、まずトレードオフを明確にするべき(こういうのはハードウェアとかの人の方が得意であると思う)
• 少なくとも、クォリティ、学習スループット、推論レイテンシ、の3値があることは考えるべきで、どれか1つを狙うアプローチを他と混同すべきでない
• もちろん上記3つ以外にもいろいろ考えることがある。例えばパラメータサイズは学習推論両方のメモリ使用量に効く、とか
• あとこの発表はメインのターゲットはCNNだったと思う。CNNは正直よく知らないので間違ってたらホントすいません
• conv WxH を factorization で別のに落とす、てのは意味的に別モデルを作ってる感があって、他のFCやらRNNでやるfactorizationは同じモデルだと思う
• RNNだとfactorizationは悪くなるという印象。パラメータの数も減るし学習も早くなるのだけど、少なくともRNNだとembeddingの後の次元はほぼ完全に自由に決められるので全体の次元を落とすことは簡単で、それで同じパラメータ数で比べると余計なことしない方が計算量的に有利だった
• なんかこの手の論文見てると正直、単にデータに対してパラメータ数過剰な状況で学習したモデルをベースラインとして、それに対して工夫するとクォリティ落とさずにパラメータ数減らせましたよ、というのがあると思った印象があります。そういうもののいくつは特に工夫しなくても単にオリジナルのモデルの次元を落とすだけでもっと効率良くパラメータを減らせるものがある印象
• ただCNNてそんなに簡単にパラメータの数調整できるのか知らないので(画像サイズとかに依存するのかなと思いつつも単に平均色出してりゃいいんじゃねえのという感もあり)知らんす
• この手のやつでは distillation の汎用性が高いという印象
• 正解データも一緒に入れるという話があるのだなあと知りました。過学習しそうというイメージがある

Convolutionの数理とアルゴリズム

なんかこの人すごい人だなあとなんとなく思ってたけど、なんかその思いが強くなった。数学強い人無条件に尊敬しちゃうよね。。。大学で数学で絶望していった時の感じ

まあまあマジメに聞いてたつもりだけど、正直きちんとわかってなかった。FFTに関しては、まあその場ではわかってないのだけど、「これはFFTするとこうやってオーダーが落ちますー」なるほどー、というのを数回やってるので、「もうなんかかけ算が足し算に変わるんやろわかったわ」、くらいでゴマかせました。中国なんとかは聞いたことあるけどはてさて、という感じだった

ウェブブラウザ向け深層学習モデル高速実行フレームワーク「WebDNN」

これはもう本当にプロジェクトのモチベーションが完全に正しいと思ってます。トレーニングしたグラフとモデルをさっさとデモできる環境がある、てのは完全に正しいモチベーションだと思う。

しっかしこんなのいくつかあるDNNプラットフォームの最大公約数を探してどうこうするのたいへんだよなあ(つまりTFで書こうがChainerで書こうが同じグラフIRに落ちてるという理解)…と。ぼんやり僕が唯一知ってるTFまわりをながめてると、 tf.while_loop の対応が無さそうだなあ、と思って聞くと、無いのは TF の設計思想のせいであると。すいませんという感じであった…

そういえば、最適化の方について結構語られてたけど、後で雑談した時は、もっとフロントエンド側に力を入れるべきというようなことをおっしゃっていたように思って、それもまた正しいなぁとか思いました。多少は遅くてもいいから、あまりいじらずに動く方が嬉しい、というか。

Using Raspberry Pi GPU for DNN

このひとゴルフ以外の話もすんですねえ…と思いました。しかしスキの無い簡潔十分な発表。僕が遊んだことがあるものでは、CellのSPEに近そうだなあとか思いました。

しかしラズパイの重要性をわかってない僕にとっては、うーんゴルフがんばったんだろうなーくらいの感しかなくてすいません。まあこの業務たまにやるぶんには楽しそう

TensorFlow XLAの可能性

この発表が僕的には目玉でした…というかXLAてのは正直社内でもかなりよくわからんので、誰かざっくり解説書かないかなーと思ってたら発表者の方が別の資料で説明を書かれていたというのもあり。

とはいえさすがに一応知らない話はあまし無かったような気がする。TF時代に入れたけどXLAになると使えなくなったりするのがあったりするのが微妙ではありますね。

今まではTFグラフをStreamExecutorていうタスクランナーで動かしてた。visitorパターン的な感覚で巡回してOp::Compute関数を実行してまわる感じ。

XLAだとグラフの一部なりグラフ全体なりをvisitorパターン的に巡回して、今度はOp::Compile関数を実行してコンパイルして、ノード群をコンパイルしたものに変えた上でStreamExecutorで実行する、て感じだと思う。

Googleが開発したニューラルネット専用LSI「Tensor Processing Unit」

一応つきあったことがあるというか現在進行形なので、言いにくいなあとかなんとか。とりあえず何喋っていいかはっきりしたのはありがたかった。

ChainerMN による分散深層学習

個人的な感覚だけで喋るなら、非同期学習オワコンは割と観測範囲の強そうな人たちが同期でいい感があると言ってる感があります。もっと言うならなるべくなら分散すらしたくないという雰囲気もあるような気がする。

後で話していたのですけど、分散すると弊社の場合、コンテナがある程度制御してるとはいえ、同じマシンで動いてる他のタスクの影響がどうしても出てしまって、同期+分散は遅いやつに性能がひっぱられがち、ということはあるとも思います。

TFが遅いとディスられてて、最初は使いかたが難しいせいかな？と思ったけど、まあそもそもTFのオープンソース版インターコネクトとマトモな感じじゃないよね、て話を思い出しました(たぶんgrpcを使っていて、この用途ではオーバーヘッドが許せる量が無いと思う)。

まとめ

まあとにかく勉強になった。なんか翻訳チームにうつってから1年ちょいたって、さすがに右も左もわからんということもない感じではあるけど、まだまだにわかほど語りたがる感じの状態です。

10年ほど後のBinary Hacks

https://twitter.com/nalsh/status/869086098177146881

を見て、今ならどういうネタが書かれるかなぁとざっくり考えてみます。

perf

@nlashさんに指摘されていた通り、perfは重要だと思うんですが、書かれていたperf_event_openはptraceなんか目じゃないくらい使いこなしがムズいと思うので、素直にperfそのまま使えって感が強い気がします

ptrace

PTRACE_SYSCALL以外はあまり変わってないと思うんですが、PTRACE_SYSCALLはPTRACE_O_TRACESECCOMPでやるとずいぶん速くなるのでオトク

asan/tsan

valgrindのbinary translationでのinstrumentationてのはカッコいいけど、普通に考えるとコンパイラに手を入れる方が常識的ですよね……という

ELF

特に変わりが無い気がする

DWARF

よく知らないけど割と変わってて、-gsplit-dwarfとか-gzあたりは知っててもいい気がします

セキュリティまわり

mitigationは気休めなんで、ちゃんと2レイヤ以上セキュリティ機能使いましょう的な

angrとかqiraとか

CTF/セキュリティ系の人が作ったツールは色々面白そうだけどあまり知らない

glibcのrandomization

そういえば気がついたらプロセス内の関数ポインタ全部ランダマイズされるようになってたけど、たぶんここ10年な気がします

inotify

便利だと思う。特にinotifywaitコマンドが……fanotifyが何が違うかは忘れました

madvise

元々書いてなかった気がするとふと思い出しました

コンテナ

コンテナベースの仮想化とかは色々ありすぎて。cloneのオプションとかすごく増えた気がするけど、今見るとそうでもないか

x86の命令

_mm_cmpXstrYは使いどころ多いし使いやすいし良いものだという気がします。あとまぁAVXとかTSXとか？

ARMの命令

スマホの台頭を考えるとARMについてもなんか。thumbとか。

Android/iOS

スマホという意味ではこのへんで違うところとかも。これらだとglibcのローダと違って名前空間がフラットじゃないとか

まとめ

なんか結構あるなということと、最近知識がアップデートされてないから知らないだけで面白いことが起きていることがまだまだありそうだなぁということを思いました

Very symmetric JavaScript code

だいぶ前に左右反転させてもだいたい同じに見えるコードを書いたのですが、もうちょっと進化させて、上下反転と、180度回転してもだいたい同じように見えるコードを書いてみました。

デモサイト: http://shinh.skr.jp/obf/very_symmetric_js.html

コード: https://github.com/shinh/hack/blob/master/very_symmetric_js/very_symmetric.js

普通のJS記号ゴルフと比べるとクォートが無いのが多少めんどくさく、あとは左右は一行コメントがあるから簡単なんですが、上下反転と180度回転のコードをコメントですっとばすのがパズルという感じでした。何も考えずに実行するコードの最後に /* と入れただけだと、180度回転した部分に */ が現れてしまってコメントが終わってしまうという。

drdr

オレオレワークフローエンジン作りたくなる病というのがあって、例えば make 系なんかだと Wikipediaに色々書いてあったりします。ワークフローエンジンと総称するのが正しいのか知りませんが、依存グラフを順ぐりに並列に実行していくようなもの、色々あるわけですけど、目的も粒度もバラバラですが以下のようなものは割と似たようなものに見えてます。

• thread pool
• Tensorflow
• make
• Digdag

閑話休題。なんか微妙に10秒程度待ち時間があるような処理があって(クラウドストレージに対する例えば ls とか)、その ls の結果全てに対してまた10秒程度時間がかかるコマンドをまとめて実行、終わったら結果を集計、みたいなことをしたりすることが最近多いです。1週間から1ヶ月ほど10回とか100回使うんだけど、でもそのうち捨てる系のコード。私の場合、よくやる解決と問題点は

• shell script で並列化したいところはバックグラウンド実行+waitで散らして、最後の部分は ruby かなんかで書く: shell script と ruby の2つを管理するのがうっとうしい。多少ややこしいパイプラインを作るの大変
• ruby かなんかでスレッドプール作ってやる: 分散部分のコードがめんどくさい。多少ややこしいパイプラインを作るのがかなりめんどくさい
• make を使う: 動作は理想的なことが多いけど、コードがめんどくさくて、あと宣言的な記述になって、シーケンシャルな記述じゃなくなるので、読みにくく編集しにくい

欲しいことを考えると

• CPU並列は無くても良い
• パフォーマンスは最適でなくて良い
• コマンドが手軽に実行できると良い
• コマンドが失敗したら即座に止まると良い
• shell はミスりやすいから嫌だ
• 処理の後半部分のやりなおしとかのためにチェックポイントを仕込めると良い

で、まあなんか作りはじめてみましたというのがこれ。

https://github.com/shinh/drdr/

あまり良い例が思いつかなかったのですが、自分のスライドのディレクトリにあるスライド全部に対して、それぞれページ数を集計するサンプルがこんな感じ。

URL = "http://shinh.skr.jp/slide/"
drdr {
  # スライド一覧のところを読んできて、 list.ckpt に保存しておく
  # これ以降のスクリプトに書き損じがあっても、再度ネットワークアクセスは発生しない
  cmd("curl #{URL}", ckpt: 'list.ckpt') | task{|l|
    # ここから list.ckpt に依存した処理で、 Apache の directory index を適当にパース
    l.scan(/href="([a-z].*?)\/"/).map do |m|
      name = m[0]
      # スライドのページ数を適当に取ってくる。このコマンド実行は並列に走る
      cmd("curl #{URL}#{name}/ 2> /dev/null") | task{|l|
        last_page = 0
        l.scan(/(\d+)\.html/) do
          last_page = [$1.to_i, last_page].max
        end
        [name, last_page]
      }
    end
  } | task{|a|
    # 全部終わったら CSV として出力
    a.each do |name, max_page|
      puts [name, max_page] * ","
    end
  }
}

などなど。妄想したほど使い勝手良くなってない気がするのですが、しかし自分が使える程度のものにはなってるような気がします。しかし一般的にこういうのはどういう感じで処理してるもんなんでしょうか。なんかいい方法あったら教えてください。。

あと Guild が実装されると計算も並列に走るようになっていい気がしますね