開発イテレーション偏重
開発イテレーションを早くすれば、かなりの問題が勝手に解決される、と信じています。なんか最近、他の要素を軽視しすぎていたり、特にイテレーション速度に影響しなさそうなことすらしている気がしていて、信仰とかのレベルかもしれない、という気がしてきたので、ちょっと書いてみようかなと。主に C++ の話です。
仕事とかしてると良い判断力が求められたりしますが、判断というのは結構難しいですよね。アプローチ A と B で悩んだ時に、手が速ければ両方できたりします。開発イテレーションを無限に速くすると、必要とされる判断力はゼロに漸近していきます。やったね。
2手で変更の正当性を高速に確認できるようにする
make (かその他のビルドコマンド)てやったらビルドができて、 make check (かその他のテストスクリプト)てやったら遅くないテストが全部走る、という体勢が好きです。試すためにはあっちのディレクトリで make してこっちで build.sh を走らせて、それで bin/test foobar とかするとできる……みたいなのはとても良くない。単純に新しくチームに入る人とかにとっても厳しいですしね……
そのためには(正直どうかと思うけど)テストの網羅性を捨てて良いとさえ考えてます。まあ理想的には CI では網羅的なテストが走るけど、手元でイテレーション回す時のテストはそのサブセット、みたいなのが良いのでしょう。 CI といえば CI の時間ちょっと削るとかも好きで、好きなんだけどその時間たぶん本来の作業に回した方が良いケースも多いと思うので、信仰だなあと思うゆえんでもあります。
イテレーションを高速化するためならどんな努力でもするので、ちゃんと複数プロセッサ使って並列にテストが走る仕組みを整えたりもします。
細かいユニットテストを避ける
ユニットテストをちゃんと書いていても、なんか結局それを使っている main の部分とか、 Python インターフェイス生やしていたらその接続部分にバグが出たりするので、なんか結局 end-to-end で起きる挙動でテストするのが一番確実だと思っています。 Ruby なんかはほとんど (全部だっけ？) のテストが Ruby で書かれてると思うんですが、そんな気持ちです。
なんなら、これもどうかとは思うのですが、細かすぎるユニットテストを書かないようにしています。細かいテスト書いてるとコケた時にその場所の特定がラクになるなどのメリットがあるのですが、テストがコケる確率ってそんなに高くなくて、コケた時にかかる時間の節約に対して、ちゃんとユニットテストを書くコストの方が高いということは結構あるように思う。 Ruby の例のように、 end-to-end のテストの方が、細かいユニットテストを書くより楽なケースは特に。 AST を自分で構築するより、テストしたい AST になってくれるであろうコードを書いた方がラク、という話。
ヘッダを最小化する
ビルド時間を最小化したくて、ヘッダサイズって結構効くという信仰を持っているので、なるべくヘッダを小さくしています。昔はヘッダ書くと最低1つはクラスがあったのだけど、最近は関数2,3個宣言されてるだけ、みたいなことが多い。
信仰なので本当に効いてるのかはわかりませんが、ヘッダオンリーライブラリとか使った時に、その部分だけ明らかにコンパイルが遅かったりするので、世の中の人もっとヘッダをシンプルに、できればヘッダで template 使わない、など気をつけてくれるとなあ……とよく思っています。
あとまあよく言われることですが、過剰な抽象化とかですね。 YAGNI!
やたらチェックする
イテレーションを最速化したいのであって、タイピングを最速化したいのではないので、割とやたら assertion 相当のコードを入れます。例えば
CHECK_LE(0, i); CHECK_GT(x_.size(), i); return x_[i];
のようなコードを書きます。 x_.at(i) をすればチェックした上で失敗したら throw してくれるのはもちろん知っているのですが、例外が起きた時に、どこで起きた例外かをバックトレースから特定して、 gdb で i の値がどうなってるか、などをするのが結構手間なので、呼び出し元の行数と、比較している値を表示してくれる、上記の(glog由来の)マクロがお気に入りです。
また、 CHECK_EQ(x, y) << z みたいなことができて、 z は x != y の時だけ評価されて表示されるのですが、この時 operator<< が x, y, z の全てに定義されていないといけないので、めんどくさいけど、積極的に stringify するコードを書くようにしています。
最適化オプションつきで開発
これはケースバイケースで、特に初期の頃はむしろ -O はつけずに作業しますが、テスト時間が増えてくると、基本的に常に最適化オンで作業して、たまに起きる gdb でのデバッグ作業がつらくなるのは我慢する、というスタイルにすることが多いです。上記マクロでそこらじゅうにチェックが入っているはずなので、 gdb が必要な可能性を落としている……はずです。
あと、大きいプロジェクトなら -g も切って、イテレーションを最速化して printf 入れまくった方がデバッグしやすい、とする時もあります。 LLVM で遊んでる時とかはそれが結局一番良いように思いました。
あと、リリースビルドで消える assertion 、という概念が嫌いです。ほぼ 99.9% パフォーマンスに影響しないくせに、副作用のある式の記述が面倒になり、それを解決すると参照されない変数ができることがあって嫌い。 NDEBUG 時だけ起きるコンパイルエラーとかで時間を消費させられるのが嫌い。
なるべく auto を使わない
auto 、書いてる時はラクなんですが、読んでる時にかかるコストが増えるので、損益分岐点は 20 文字くらい、かなあと思っています。 iterator なんかはめんどくさいし文脈から自明なことが多いので、 auto 使う、みたいな気持ちでいます。
auto に限らず、ループ内包や std::transform 、三項演算みたいなやつも、書くのがラクになるかわりに、単なる純朴なループや分岐の方が可読性が高いと感じることが多くて、他の人より使う頻度が低いなあ、とよく感じます。
一方で using namespace はあまり実害が無くてコスパ良いと思っている(特に std はスタイルが違うので無くても明白)のですが、コーディング規約で許されてないので諦めています……
まとめ
なんか他にもある気がするのですが、他と見比べてて、自分のスタイルが違うと感じることが多いところを並べてみました。他の人の工夫とかも気になるところです。
20%ルールについて
20%ルールという仕組みの雑談になって色々考えていたことを思い出しました。
僕はこう、20%ルールがあまり好きじゃない。まず、時間が細切れになって効率が悪い問題というのがある。「20%ルールのおかげでイノベーティブなプロダクトが生まれた」というのは、イノベーティブなアイデアにも関わらず100%の時間をそこに費やすことができなかった、ということなんじゃないか、と思ってしまう。1ヶ月で実現できたはずのアイデアに、単純計算で5ヶ月かかるわけで
ここで、僕の好きじゃないスタイルの20%ルールは、金曜日は20%、他はメインのプロジェクト、というスタイルのやつに限定している
好きなスタイルとして、 http://shinh.hatenablog.com/entry/2016/03/11/142748 に書いた「半年メインプロジェクトに集中してた僕ですが、なんかやってみたいことができました、1ヶ月時間これに集中する時間を下さい、うまくいかなかったら捨てます」てやつ。集中できるのが良いし、1週間に1日スタイルより、失敗した時に捨てやすいというのも良いように思う
次に最初のやつより嫌いなやつとして、自分磨きやおよそ会社に関係ないことに20%を使うやつ。これはなんか、僕から見ると、スプラトゥーンやってるのと区別が全く無い。使わないと損な勢いになって、不公平感さえでかねないように思う。これを認めるのであれば、単純に、福利厚生として週休3日、とする覚悟がほしい
もう一個好きなスタイルとして、言い訳としての20%というか、5%ルールとでもいうか。今直近の仕事では必要ないけど、長期的に見たら役に立ちそうな知識を仕入れるとか、便利スクリプトを整備するとか、 zshrc を充実させるとか、なんか、そういう全然イノベーティブじゃないやつ。会社でこれをやりましょう、みたいなタスクがある時に、そういうことを突然やりたくなる時があって、そういうことに時間を使うのはちょっと気がひけるのだけど、「まあ20%てことで」みたいに適当に言い訳できるのは良い
ここまでは前職の話
今だと、エンジニアが10000人とかいないので、必然として、一人あたりが関わるプロジェクトの数が増える。そうなると、「このプロジェクトは重要だが、1人アロケーションするのですら多い」みたいなプロジェクトが出てくるんだなぁ、ということに気付く。そうなってくると、0.2人をアサインできる、金曜日は20%ルール、という、最初に否定したスタイルの20%すらアリかもしれないなあ……とか思えてくる。ただ、金曜日は○○、というスタイルは僕には効率が悪いように思うので、1週間ごとにどっちかに倒す、みたいなのを試してみることにしてみました。
20%のことだけでもそうだけど、前職で正しいとされていたことが、当たり前のことなんだろうけど、違う規模違う文化の会社で適用してうまくいくとは限らず、もちろん逆もあるなあと思います。色んなことについて、違いに思いを馳せながら、ケースバイケースな感じで最適なありかたはどうなんだろうなぁ……とか考えるのは結構面白いな、と思います。
転職してからやってること
転職してからやってるプロジェクトについて何か書いてみようかと思います。
https://github.com/pfnet-research/chainer-compiler/
公式ぽいブログも書きました。
あまり綺麗にまとまった文章を書ける気がしないので、つらつらと時系列で思い出して行こうかと思います。
転職前、 define-by-run とかについて考えていたこと
まだ前職にいた時、転職活動中に、 ChainerX の存在や、 Python からコンパイルして実行できると良いなと思っている、みたいな話を聞いたような気がします。これは結構、具体的かつ無茶ぶり感がある話で、まあ楽しそうだなと思ったし転職先を決める理由になったような気もします。
機械学習、どんな計算してるかというとおおむね行列のかけ算ばかりしている、とかよく説明します。とはいえ非線型な要素も必須だし、計算結果をどうつなぐか、みたいなのでなんかうまくいく方法が発見されたり、ブロックの接続をこねくり回してるような感覚があると思います。
で、そういう接続をごにょごにょする機械学習フレームワーク、色々あるわけですが、 Chainer 以前は、ブロックの接続を作る DSL があって、接続ができたら、誤差逆伝播の計算を考えて、ハイ実行、と実行する形式だったと。 tf.add(A, B) とかすると、 A + B を実行するんじゃなくて、足し算するための計算グラフ内のノードを返す、みたいな感じ
で Chainer は、 chainer.functions.add(A, B) とかすると、そのタイミングで実際に実行する。実行すると同時に、誤差逆伝播する時に必要なグラフも作っておく。コンパイラに対するインタプリタという趣きで、問題が起きた時に問題のある行で止まるので、デバッグがしやすい、分岐などを含むようなフレキシブルなモデルを普通に記述できる、などのメリットがあります。ただ、欠点が2つあります
- Python 無しのデプロイができない。計算グラフを作る DSL という形式であれば、そのグラフをエクスポートしてしまえば Python 無しのアプリから使えるわけです。
- 速度的にオーバヘッドがある。これは、 CUDA の関数実行が遅延されているおかげで、単純なモデルでは GPU 律速になって Python+CPU でグラフ作ったりしてるコストは隠れることが多いです。 cupy てセンスいいものだなあとつくづく思います。が、自然言語モデルや、小さいモデルだと CPU 律速になったりするし、 GPU が高速化し続けてることも相対的に問題を大きくしていっています。
ですが、まあ、研究者のイテレーション速度の方が重要だと考えていて、 define-by-run 良いなあと思っていました。ループがあるモデルを扱ってたことによるバイアスもあると思いますが。
そんな時になるほど！と思うものが現われました。 Swift for TensorFlow というやつです。 Swift for TensorFlow は、 define-by-run 、つまりモデル定義を実行時に行なうことが重要なのではなく、モデルがデータでなく、コードで定義されていることが重要なのだ、と主張しました。当時、 tf.while_loop じゃなくて Python の普通のループを使わせてくれ〜と思っていたので、このコンセプトが大変気にいりました。この図もなるほどーという感じでしたね
グーグルの作ったもので Native Client の次くらいに好きなものといえると思います。つまり成功する気がしないのですが。 Swift 本当に使うようになるのか？？という普通の疑問がまああるわけです。
で、そういうタイミングで、転職活動中に、具体的にどういう計画かよくわからないけど、 Python コンパイルしよう、という話だったので、本当にできるのかはよくわからないけど、それは関われるものなら挑戦してみたい話だな、と感じました。
このへんの DL フレームワーク話は 退職直後、入社前の間の時期にも書いたりしました。
入社してみた
入ってみると、何も決まってないから、なんか IR をデザインして、 Python をそれに変換して、 ChainerX で実行するのやってくれ、という趣旨のことを言われたと思います。もうちょっと具体的に計画や実装が既にあるかと思ってたので、ずいぶん無茶振り来たなぁ、と思ったように思います。同日にインターンの人が入ってきて、その人には Python を ONNX という業界標準のモデルシリアライゼーションフォーマットに変換するタスクをやってもらおうと思っている、という話も聞きました。
いや似たような Python から変換するタスクを別々にやってどうすんねん、ということで、 ONNX をざっと眺めたところ、これを拡張したら十分にやっていけるだろう、と感じたので、インターンの人には Python => ONNX の部分、私の方は ONNX を実行するものを ChainerX を使って作る部分、と分担しようと考えました。これはなかなか良い決断だったんじゃないかなと思っています。実のところデザインとか全く自信が無いので、 IR とかうまく作れる気がしなかったし、ある程度考えられたデザインにタタ乗りできたのはおいしかった。あと、 ONNX のエコシステムまわりの他の人たちが作ったツールが使えたり、社内の ONNX 関係の別のツールとの協調とかも視野に入るのも良かったです。
このあたりで ChainerX についての理解も深めていきました。 Chainer は行列計算とかの重い計算は numpy/cupy というのに投げてるわけですが、 numpy とコンパチな ChainerX array というのを C++ で作って、 C++ 側に、従来 Python で実装されていた誤差逆伝播を持ってくる、というコンセプト。
前章でデプロイができない、速度が遅い、という問題に触れましたが、 ChainerX はこれらの問題を大幅に軽減するものです。 ChainerX array は C++ で書かれているので、 Python 無しのデプロイの道が開かれてくるし、速度が遅い一番の原因だったらしい、誤差逆伝播が Python で書かれているという問題もなくなるのでした。
作ってみた
とりあえず世の中にある、ある程度大きいネットワークを動かせるようにしていきました。 ChainerX に基本的に必要な関数があるので、基本的には ONNX と ChainerX 関数を対応づけていくだけです。最初は ChainerX を使う C++ コードを生成していたのですが、テストのイテレーションが遅くなるのを嫌って、 ChainerX の関数を次々呼んでいくだけ、みたいな VM を定義して、それを使うようにしました。 ResNet50 くらいは割とすぐ動いたような気がします。
時系列は覚えてないですが、このへんで誤差逆伝播のグラフを生成するコードもでっちあげたのではないかと思います。最適化やらなんやらを実装したいとすると、計算グラフを編集するライブラリとして機能できる必要がどうしてもあるので、そのあたりの proof-of-concept として、自動微分ができる、というのは最低限の機能担保という感があったのでした。
そうこうしているうちに、インターンの方が同じく ResNet50 くらいのシンプルなネットワークを ONNX 化できるようにしてくれて、実際にそのグラフを入力としてトレーニング用のグラフを生成して ImageNet という、 224x224 の画像データを 1000 種類に分類、みたいな使ってトレーニング、みたいなことができはじめていたように思います。
このへんからは時系列曖昧ですね
EspNet を end-to-end で通そうとする日々
EspNet というのは、音声認識や音声合成、その他もできるツールキットで、これのまあまあ複雑なコードパスを通そうと努力してました。とりあえず、ツールチェインの上から下までで、ループなどをちゃんと扱えますよ、という状態にしたいという気持ちがあったので、これをターゲットとした感じでした。 Conv + NStepLSTM + CTC + デコーダーは attention ついてるからループ回して LSTM やる、みたいな感じになってて、色々なものに対応しなければならないのです。
元々の ONNX の Loop や Scan といったオペレータは、固定長の ndarray 的なものの入力が入ってくる前提だったので、これは可変長の Python list とかが扱えるようにしたいなあ、と考えて、ここは結構大幅に拡張した部分でした。
インターンの人が、無茶ぶりにも関わらず、まあまあややこしいループなども動くように作ってくれていた感じでした。実際、ループ動かすための仕様みたいなのもキチンと決めず、かなりダメダメなメンターだったはずなのに、ちゃんとそれなりにそれぽかったのでとても感謝でした。それを引き継いで EspNet で必要な、かなりややこしい変換などをできるように努力していきました。 __init__ で self.x = None しておいて、後で if self.x is None: self.x = ... とかする、遅延初期化みたいなのがなかなか面倒でした。
それが通ると、次はループや if の微分というか誤差逆伝播を頑張って、あとは Python list まわりも逆伝播実装して、これらもなかなか大変でした。
このあたり、ループをちゃんと動かすとか、 Python の list を扱える、とかにこだわっていたのは、 Chainer のフレキシビリティを損ないたくないなあ、と思っていたことがあります。 dynamic shape とか可変長 list 扱うとかすると、どうしても最速が出ない局面は出てくるとは思うのですが、とりあえずフレキシビリティの方が重要かなと。あと dynamic shape を扱いつつも、 static に決まる部分は決める、みたいな方針でやってるので、次元が決まったところは高速化…みたいなこともできるのではないかと思っています。実装が追いついてないですが、 TVM のコード生成使う実験とかは shape がわかってる前提でやっていました(というか TVM は dynamic shape に関して結局なんか計画あるのだろうか)。
EspNet をまともな速度にしようとする日々
動くようになった最初はなんか、素の Chainer より圧倒的に遅い！みたいな状態でした。で…何したんでしたっけ。ちゃんと cuDNN の LSTM を使うようにしたり、 elementwise op の fusion したり、定数伝播やったり、などなど。 Python からグラフ生成してると、なんかゴミみたいなノードができまくるので、定数伝播みたいなのが重要なのですよね…
でまあ、まともな速度になって、 CPU heavy なケースでは Chainer に勝つなあという感じになりました。ただ CTC とかいう処理を実装してなかったので、実際に end-to-end で訓練することができなくて、しかしそんなの実装するのかったるいので、 Python インターフェイスを追加して、モデルの一部分だけを chainer-compiler で処理する、みたいなこともできるようにしました。
でまあそれぽくなりました。 Python コードに多少の、気持ち悪い変更が必要なのが、なんともはやな部分ではあるのですが…
TVM で遊ぶ
年末あたり、 TVM で遊びました。 LSTM は、会社としては直接そんなに重要でないということもあり、ちゃんと Conv とかを良くできるポテンシャルはそなえておかないとかなあ…と。
結果としては、色々面白いけど、 Python と C++ 行ききしまくりのコードがつらいというのがまず感想でした。あと、特に普通の Conv とかだと、伸びしろがそもそもあまりなくて、投下労力に対して得られるものがなあ…という気持ちもありました。
で、とりあえず保留することにしました。いずれにせよ、フレキシビリティという観点などから、自力でカーネルを生成できるオプションは中期的にはあるべきだと考えていて、どこかの段階で戻ってくることになると思っています。
オープンソース化
これやること無限にあるから、一人でやってると崩壊以外見えねえなあ…と思ってたので、人が欲しいです、みたいなことをわめき始めてました。これグーグルだと、人が増えるかあるいはお前のそれやってるそれ意味ないからやめろや、て言われる二択でわかりやすかったのですが、小さい会社でみんなそれぞれ忙しくて、人も増えないがお取り潰しにもならない、という雰囲気でした。
で、どうも社内で取ろうとするんじゃなくて、外から拾ってこい、という文化だと学びました。確かに、個々人で拾って来させるってのは、なるほどベンチャーの成長方法として理に適っているなあ、と思いました。というわけでツイッターでわめいたりしてみました。
ただ、なんかやっぱコミュニケーションがしづらいということを思っていて、ユーザ向けリリース、という感じではなくて、こういうことやってますよ、仲間募集、ということでオープンソース化したいと思って、しました。とはいえ、それなりには、色々整える必要があって、それなりにはめんどうでした。
これから
適当に風呂敷を広げて、結構広い範囲で実装してみたけど、とりあえず、という感じの仮立て付けぽい状態の部分が多い状態で、まだまだやることが無限にあるなあ、と思っています。
基本的に、 chainer-compiler にこだわらず、 Chainer まわりで静的なグラフを扱うシーンのエコシステムを、全体として整えていきたいな、と思っています。最近ちょっと onnx-chainer に手を出してみたりもしていたり、とか。このへんキチンとしてないことがデプロイの大変さみたいなことにも直結してしまっているので。
不完全な部分がそこらじゅうにあって、どこから手をつけても良いような感じだし、やっぱ社内需要を満たすところを優先するのが良いよねえ、と思っているので、社内需要満たす努力をしつつ、汎用的なツールチェインとして少しずつ育てていけると良いなぁ、とか思っています。
あと例のごとく一緒に働きたい人募集中です。うまくいくかは不明ですが、ある種の人には、楽しくはあるんじゃないかと思います。少なくとも僕は大変楽しんでいます。
ONNX はチューリング完全だよ、という話
シクシク素数列 Advent Calendar 2018 向けです。
ONNX はニューラルネットのモデルをエクスポートして、別の実装でインポートできたりする、相互運用のためのフォーマットです。複雑なモデルをサポートできるようにと、 Loop とか If とかがあるので、チューリング完全です。ただまあ実際にえぐい使われ方してる例は見たことがなかったので、やってみました。
https://github.com/shinh/test/blob/master/onnx_gen_4949_prime.py
が、4か9を含む素数を出力する ONNX モデルを出力するプログラムで、
$ wget https://raw.githubusercontent.com/shinh/test/master/onnx_gen_4949_prime.py $ wget https://raw.githubusercontent.com/shinh/test/master/onnx_script.py $ python3 onnx_gen_4949_prime.py $ ls gen_4949_prime model.onnx test_data_set_0
とかで ONNX ファイルが出力できます。実行は、 ONNX のループとかをサポートしている処理系があまりないと思いますので、 ONNX runtime とかを使ってください
$ python3
>>> import numpy as np
>>> import onnxruntime
>>> sess = onnxruntime.InferenceSession('gen_4949_prime/model.onnx')
>>> input_name = sess.get_inputs()[0].name
>>> output_name = sess.get_outputs()[0].name
>>> sess.run([output_name], {input_name: np.array(104)})[0]
array([ 19, 29, 41, 43, 47, 59, 79, 89, 97, 109, 139,
149, 179, 191, 193, 197, 199, 229, 239, 241, 269, 293,
347, 349, 359, 379, 389, 397, 401, 409, 419, 421, 431,
433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
499, 509, 541, 547, 569, 593, 599, 619, 641, 643, 647,
659, 691, 709, 719, 739, 743, 769, 797, 809, 829, 839,
859, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971,
977, 983, 991, 997, 1009, 1019, 1039, 1049, 1069, 1091, 1093,
1097, 1109, 1129, 1193, 1229, 1249, 1259, 1279, 1289, 1291, 1297,
1319, 1399, 1409, 1423, 1427], dtype=int64)入力で指定しているのが 104 なのは、 8 の倍数じゃないと ONNX runtime がクラッシュするぽかったからです。他にもいくつか ONNX runtime のバグらしきものを見つけた気がするので、適当に報告しておきます。
チューリング完全ということで、 ELVM のバックエンドを作っておきたいのですが、 TensorFlow モデルバックエンドが遅くて実用にならないという問題があって、 ONNX も似たような感じなので、どうしたものかと思っていたのでした。ただ、なんか最近手っ取り早く高速化する方法を思いついた気がしたので、今度やってみようかと思います。
ICFP programming contest 2018
無職なこともあり、とても楽しい問題だったこともあり、久々にほぼガチで参加してる会になりました。いや楽しかった。順位表が凍結された段階での最終順位は2位で、1位は絶対に無理、その後にできた変更はしょうもないので、おそらく7位とかそのあたりの、5位強みたいなところに落ちついているのでないかと想像してます。暫定2位といっても特に良いところはなく、得点を決める式のおかげで、大幅なとりこぼしが無いだけで、推定1位のウナギに対して全順序がついて負けてる形のはずで、大変くやしい。が、まあ僕的には頑張ったとは思う。
初動
パーサやシミュレータを実装して、簡単なシングルスレッドAI、下から順に塗っていって、既にあるブロックとつながっていないところに置かざるを得なくなると、 Flip する、というものを Ruby で書く。デフォルトよりは大幅によくなることを確認して、いい問題だなあ……と思いつつ、寝る。
シミュレータについて、 SML 的ななにかからコンパイルされた JS だから、単純な方法でこれ切り出せるでしょ……と思ったけど、それに時間を使う余裕は最後までなかった。それに限らず、時間的余裕は最後までなかった。
起きて、 Flip のコストがとてもでかいこと、並列化が大変嬉しいこと、を再確認して、スケジューリングは賢くなくて良い(つまり無駄な動きをしても良い)から、 Flip はできればしない、かつスケールし、できればヘッドのMoveとFillの比が良い方針を考える。
思いついたのは、やはり下からスケジュールして行くのだけど、自分の左右と真下を塗る、という方針。Move:Fill比が最大1:3で、なんとなく良さそうに思ってた。
# B がボット、 O が担当する Fill する範囲 # 右方向が Z 軸、上方向が Y 軸、奥が X 軸で進行方向 OBO _O_
でも実装してみると最初の戦車ぽい形のやつすらダメで、理由は説明しずらいけどとにかくこの方針で Flip 無しはできないのでした。もう少しちゃんと考えてから始めるべきだった。
エレベータ
次に考えたのは、上方向から見た X-Z の平面を 3x3 の区間に分割して、並列に動くボットは、その空間の中で一回以上塗ることが可能などこかにアサインされる。イメージとしてはエレベータなのだけど、その 3x3 の中心を下って上がって、途中で塗って返ってくる。 3x3 の中央は、ロボットが作業用なので、まだ塗っていない領域が下の方にある場合は底の蓋をしてしまわない。
この方針でたいていの問題が Flip 無しで塗れる感じになり、 3x3 のグリッドの作りかた9種類をそれぞれ試すと、どれかは Full Division の問題を解けるようになりました。
最初に間違った方針で時間を浪費してしまったこともあり、 Lightning Division 中には全部の問題にたいしてまともな点数の結果を返すことができませんでした。見積りをあやまったな、と。
Lightning Division が終わった後も、このコードはバグバグだったので、それを修正しまくって、一通りバグが取れて、一通り FA の問題に適用し終えて提出すると、 FA に対しては全て1位が取れている感じになっていました。潜伏していた人もいたかもですが、これが Lightning Division に提出できていればなあ……と残念。
さてこのエレベータの方針は、
という2点の TODO がありました。 Full Division のルールを検討するまでは、これは結構面白い課題だと思ってたので、是非やりたいなーとか思っていました。ですが、構築はそれなりにうまくいっているので、まだ実装してない解体を優先しました。最終的にもこれらの TODO は手つかずのままだった。
役割が無くなったボットは、とりあえず天井まで移動して、それから次に行きたい場所をアサインする、という流れだった。そういう感じでやると、当たり前だけど x=1 z=1 にいるやつは x=5 z=1 に移動しようとして、 x=5 z=1 にいる子が x=1 z=1 に移動しようとする、いわゆるデッドロックが頻繁に起きていた。これはまあ、定期的に全員が Wait を発行している場合、ランダムなタスクの担当者を入れ替える、という雑な方法で解決した。まあこの問題は頻繁に起きることではあるけど、しかしスコアに大幅な影響を与えるほどの問題ではないであろうとそのままにした。
解体して良いかという判断
解体は、構築と違って、この座標のブロックを消して大丈夫か…という判定が自明じゃないので、そこをまずあれこれと考えました。最終的に、近似的な方針でやることにした
- 最初に地面から幅優先探索する
- とあるブロック X に幅優先で辿りついた時、 X に同時に辿りついた元のブロック群が、ブロック X を支えている、と仮定する
- ブロック Y を消して良いかを考える時、 Y が支えている全てのブロックをチェックし、そのいずれかが Y によってのみ支えられている時、そのブロックは消してはいけない
例えば
ＡＢＣ Ｄ Ｅ
だと、依存関係は
Ａ→Ｂ→Ｃ ↑ Ｄ ↑ Ｅ
となるので、Ｃしか破壊できないと正しく判定される。
ＡＢＣ ＤＥ Ｆ
だと
Ａ→Ｂ→Ｃ ↑ ↑ Ｄ→Ｅ ↑ Ｆ
なので、Ｃに加えて、ＡとＥも、どちらかなら破壊して良い。何故ならＢはその両者から支えられているから。
保守的になりすぎて消せるブロックを消せないと判定するケースがあって、
ＡＢＣＤＥ Ｆ＿＿＿Ｇ Ｈ＿＿＿Ｉ
だと、どれを消しても大丈夫なはずだけど、Ｃしか消せないと判定されてしまう。
Void による解体
解体可能判定が上記で決まった後も、特に良いアイデアが無かった。よって、よく覚えてないけど、おおむね構築時の 3x3 に分配するアルゴリズムを使いまわす感じの、しょうもない実装で実現した。
解体時は構築時と違って、 Void によって移動範囲が減ることは無いため、あまり大変なバグは起きることはなくて、まあほどほどのタイミングでこれは完成した。ただ 3x3 に切っていくという方針はそもそも解体にとって良い方法ではないため(特に上述の解体可能判定が正しくないため)、かなり遅いものになってしまったという感じ。
感想戦で twitter で見た方法として、解体は構築の逆再生をすれば良いというのを見て、なるほどこれをやっていれば解体について使った時間の多くの人的時間を節約できたなあ……と思った。
平面 GVoid による解体
明らかに構築に比べて解体で得ている得点がイマイチだったので、解体をもう少し考えることにした。
結果、解体は GVoid でまとめてやるのがやりやすく、依存解析をすっとばせる部分がたくさんあるのもあって、むっちゃいいじゃん、となった。とはいえ、 3次元 GVoid はこの段階では「管理大変そうだなあ…」という感覚があり、2次元 GVoid で上から順に切りとっていくソルバを作った。
これはコード量はおおくはないし、このソルバ自体は前述のソルバと違って全ての問題を解く汎用性はないけど、多くの問題に関しては前述のソルバを凌駕するものとなった。こういう、問題によって違うソルバが有効になる問題は一人チームだとキツいんじゃよーと思いつつ、だがうまくいったのでよしよしと思いつつ次へ。
最高記録管理、あるいはインフラ
今回一人チームきっっつい、と思った部分はいくつもあったのですが、一番きつかった部分でした。今回の問題の場合、単一のプログラムがベストの解を出す必要はなく、複数の似たようなプログラムがそれぞれ出した解の最高の物を提出すれば良い形式で、かつ、その最高の解が必ずしも最終バージョンのプログラムによって生成されている必要はない、という形式でした。
そのため、提出できる解のうち最高のものを管理し、かつその最高のものを越えた解があればそれでアップデートする必要がありました。これは2種類のめんどくさいタスクを追加しました
- 開発中のシミュレータはおそらく正しくないため、現段階でのシミュレータで実行してみて、たしかに一番良い結果が更新された、と判断すれば最高記録として記録する仕組みを作りました。0点を取ると死ぬ今回のルールでは、これは安全で良いアプローチだと思うのですが、問題はシミュレーション自体が大変遅いものであったということでした。おかげで、常に「なんだかもう覚えてないけど、なんかの計算結果を(おそらくムダに)検証している、という状態になりました。
- 3D モデル X を別のモデル Y に変換する、というタスク(FR)は時間が足りなかったこともあり、単純にそれが一番効率だと考えられたこともあり、 X を完全に解体してから Y を完全に構築する、という方針で解きました(たぶん他のチームもそうやっているかと思います)。これは X を解体する最高記録を残しつつ、 Y を構築する最高記録も残して、んでその二つの最高記録をマージしなきゃだということになります。めんどくさい
- 当時の段階では、 FR なモデル(つまり解体&構築なやつ)は、ものによってはひょっとすれば解体+構築より効率的な実装ができるかもなあ……と思っていたので、解体+構築を同時にやるようなアルゴリズムが後でできるかも、という仮定の元、2日目寝る段階では、 FR は単に FA+FD をまとめてやる物を計算して寝たのでした。よって FR 解から FA 解と FD 解を切り出してきて、一番良い FA & FD を切り出す、というような余計なタスクが発生しました
などなどやってるうちに、結構な時間が溶けました。結果として、 FA+FD よりも FR を効率的に解く方法を考えられる問題はぱっと見見つからず、 FA+FD を効率的に解けることを期待したインフラも完全に無駄になりました。
今にして思えば、アルゴリズムで作った手順が、シミュレータで間違ってることは基本的に無いため、再確認は特にせず最高記録を更新する手順にすれば良かったなあ……と思う。
まとめて 3D GVoid
この段階でもう一度リーダーボードを眺めて、構築も解体もほどほどに良い解は提出できている(Flipも無いし並列化もされている)ので、特に「こういうタイプの問題で弱い」みたいなのは無く、単に全て弱いことがわかっていました。そこで、複雑な問題は再計算する時間が無いため、単純な問題に対して単純でかつ有効な解は無いか……ということを考えました。
すると、単純な問題での解体がイマイチな点数であることに気付いたので、あれこれ考えました。あれこれ考えた結果、単純な問題は問題全体を GVoid で消してしまえるのでは……と気付きました。
で、最初に8体に分裂して、全体を消して、終了、みたいなやつを作りました。あたりまえでしたが簡単な問題については劇的な効果がありました。今にして思えばこのロジックをさらに良くして、一回で消し切れない問題に対しても 3D GVoid を使う解を生成する価値があったと思っています。
たしかこれをやってるあたりでリーダーボードが凍結されました。
GFill を使ってみたい
このあたりで、「やりたいことは無数にあるけど、期間内で実際にやれて、かつスコア的に劇的に有効な手が思い当たらんなあ…」と思ってました。その結果、 GFill 使ってないのはムダすぎるよね、と思いました。
で……ごくシンプルな 1D GFill と Fill で解ける問題だけを解くソルバを作りました。序盤の方の問題はこれで全部解けるだろ……という気分で作ったのですが、実際見てみると壊滅的で、 FA 3問くらいの最高記録を更新できただけで終わりました……
まとめ
すごく楽しかった。まじですごかった(低語彙力)。問題をぱっと見た時に、「なるほどこれ俺もできそうだ」と思うにも関わらず、いざやってみるとすごく簡単なことですらクッソ大変、というのがすごく良かった。大変明確に動くヴィジュアライザなども用意されていた。
例年と比べてもノンゼロの点数が少なかったらしい。敷居が高かったのでは、という観測もあるみたい。ごくごく個人的な感覚では、今回の問題の敷居は高くなかったと思う。常に Flip on の状態で動く解が主催から与えられているので、その中にある移動命令いくつかをつなげるだけでノンゼロの点数は簡単に得られる。単に、今までノンゼロを得ていたチームの中でほとんど実質参加してなかった層が、自明なノンゼロ解を発見できなかった、もしくは ICFPC 自体の参加者が減っている、そのあたりが理由じゃないかなあ……と思う程度には、今回の問題は弱いチームに配慮されている問題だったのではないかと思う。
個人的には、 Full Division で追加されたルールは全て必要なかった。今思えば、全ての追加ルールが、単純にゲームをシンプルにする方向に変わった気がする。当初の問題で、勝てたかっていうと今よりもっとひどい負け方をしていると予想されるのだけど、ただどっちが楽しめたかっていうと、 GVoid/GFill の無いルールだったんじゃないかな。というか、最初に考えたエレベータ方針をもっときっちり詰めたかったな。
いやでもまじで当たり回だったとおもってますマジで
転職について
6月14日がグーグル最終日でした。8月からPFNに混ぜてもらう予定です。退職や入社も重要イベントなんでしょうけど、転職活動それ自体が大変に楽しい体験だったので、入社したからって突然次の会社についての知見にあふれているわけでもなし、このタイミングでなんか書こうと思いました。どうせ暇だし。
前回との差分
http://shinh.hatenablog.com/entry/2016/03/11/142748 が前回までのあらすじ。このちょっと後で、「ニューラルトランスレートすげー」とか思って Google Translate のチームに入れてもらって、自然言語/機械学習研究入門+プロダクショナイズ+TensorFlowまわりのあれこれおもしれーとか、その他いろいろをやってた、というのが現在との差分です。
機械翻訳というのは、他の機械学習応用分野と同じく、ニューラルさんによってすさまじく簡略化されてしまったとのことです。とはいえ、機械学習初心者が10年選手に囲まれている状態で、学ぶこともすごく多くて、咀嚼するより早く新しい話題が現れている感じで、まだまだやってみたいことあるな、という感じでした。
でもやめるという話
じゃあなんでやめるかというと、飽きたのでした。グーグルでは色々新しいことが起きてて、そういうのは楽しいわけです。最近だと Swift for TensorFlow とかすげー楽しいと思いました。グーグルの外だと X 社の A と Y 社の B と Z 社の C を組み合わせて……みたいな感じでやってることを全部自社で持ってるみたいなこと多いですしね。
じゃあ何に飽きたかというと、プロジェクトとかじゃなくて、環境に飽きたということかな、と思います。
グーグルというのはやはりすごい会社で、個々の技術的な判断もそうですが、プロセスなんかもすごく合理的にうまく回ってると思います。そしてそのプロセスを改善するメタなプロセスもうまく回ってる。例えば不満があるとしても、不満を集めてきて修正する方のレイヤが割とうまく動いてるので、同じ不満をずっと持ってる、ということになりにくい。
プロダクトとかも、全体で見ると成功しているプロダクトがとても多くて、なんかあのプロダクトは地味かな？とか思ってるようなものでも、話を聞いてみると他の会社だと大成功レベルでうまくいってるような感じだったりして。成功してるおかげで投資がなされて面白プロジェクトが次々に出てくるし、自分自身はぱっとしないことやってても高い水準の給料が出る。
で、それらはすごくいいことなんだけど、なんかそういう良い環境に飽きてしまった。飽きたってのは単純な話で、単純な話だけに対処法が特に無い。しかも良い環境であることに飽きたという感じなので、どうしようもない。居心地いいからと言って11年もいたのは長過ぎでした。
というわけでグーグルはいい会社だと思います(言わされてるわけじゃないよ！)。辞める私が言うのもなんですが、おすすめ。
就職活動楽しかったという話
書きたかったのはこっちでした。人生初と言っていい就職活動がとても楽しかったんです、悩ましくもあったけど。
他の会社が何をやっているか、自分にあう仕事があるかなど、ハタから見ててもよくわからないので、気になる企業はサイトに書いてある連絡先から応募していきました。あと普段無視してるようなエージェントや会社の人事からのメールにも返事して、色々と対応していただきました。たくさん受けても一社以外行けないわけで、冷やかしみたいで失礼かなぁ……とも思ったのですが、まぁそんなしょっちゅうすることじゃないので許してもらおう……と考えることにしました。
知人がいる会社もあったので、そういう人に口を聞いてもらうという手もあるのかもしれなかったのですが、なんだか断りにくくなりそうなのでやめておきました。採用プロセスを実際に見た方が、未来の同僚がどういう方法で採用されるかを推測できるというメリットもあるな、とも思いました。かわりに、知人がいる会社では最初の面接時に「ご飯でもどう？」と声をかけてみたりもしてみました。
で、面接に行ってみるとすごく楽しいのでした。普通にオフィス見学に遊びに行っているのと違って、会社でやってることについて細かく説明をしてもらって、私が入社するとするとどういう仕事がありそうか、などに突っ込んで聞けるので。そういう突っ込んだ話をしていると、とても勉強になる。グーグルの X に対応するものは Y でこういうふうに使っているんだなぁ、とか、グーグルだと基本 B2C だけど B2B だとこういう感覚なんだなぁ、とか。
聞く話は大変面白そうな話が多くて、なんだそれ面白そう俺も混ぜろ、と思って毎度面接の後は「よしここにするかー」みたいに思ってるというような状態になりました。まぁ流されやすいのもあると思いますが。最初の頃は「グーグルには満足してるけど、もし面白そうな話が一つくらいあれば……」くらいの気持ちだったんですけど、これだけ面白い話があるなら、「どこかには転職するだろうな……飽きたし。あと転職活動に費した労力がもったいないし(サンクコスト)」、という気分になっていきました。
複数社から楽しそうな話を聞けたのは本当に嬉しい誤算でした。感じたこととして
- 人々が普通に楽しそう。10年前だと「エンジニア中心の会社です！」みたいな広告がなされてた気がするんだけど、もうそんなことは割と自明になってしまっている
- 小さい会社が普通にテクニカルな意味で(私の興味基準で)すさまじく面白そうなことをやっている
- お金も割とちゃんと出そう
体感ですが、10年前だと上のうち1つ満たす会社はあるけど、5年前くらい前までは2つ満たすのも難しかったのでは、と感じました。なんかいい時代になってるんじゃないかな、と思いました。AI系の会社に関してはAIバブルのおかげとかもありそうですが。
一方で、「どこも楽しそー」となってしまうと、候補を減らしていくのが大変でした。各社、楽しい議論を時間を割いて一緒にしていただいていただけに、断るのがとても心苦しくて。
最後、数社でどうしたもんか……と、今までこんなに悩んだことあったかなーというくらい考えました。結局なんで PFN のオファーを受けようと思ったかというと、いろいろあるけど、 PFN が一番うまくいかなさそうな気がしてきたからでした。良く言うとゴールが高いということもあるかと思います。うまくいかなさそうというか、「この会社どうなるんだろ？」と素直に疑問というか、良く言うとわくわくするという感じかもしれないです。
PFN より規模の小さい会社もいくつか候補にあって、割と高確率でうまくいくと思っていたので、会社が成功すると株とかで一攫千金！みたいなのはとても魅力的だったし、「もったいないことしたかなー」とも思っています。まぁでもグーグルで一番楽しかったプロジェクトはうまくいかないと思いつつ入って、実際にうまくいかなかったやつなんですよねえ(不吉)。
あとなんか、よく言われることですけど、採用とかはどっちから見ても縁というかタイミングというかですね。もう数年前だったら、もう数年後だったら、それぞれ違うところに行ってた気がします。実際、今回も他の会社のオファー受けかけたりもしましたし。なんにせよもう少し頻繁に転職とか考え(る|られる)べきだな、と思いました。
最後に、今回応募させてもらった会社の対応してくださった方々にとても感謝しています。色々と今まで考えてもなかった視点を持てたように思います。ありがとうございました。
まとめ
- グーグルいい会社だけど11年は長すぎた
- 転職活動楽しかった。おすすめ
- 8月まで暇なんで遊んでください
MJIT で dlopen 使わずに ELF オブジェクトを直接ロードする話
MJIT というのが Ruby に入ったのは聞いていて、すごいことするな、と思ってたんですが、実際に Ruby Kaigi で話を聞けて少し遊んでみたくなったのでした。そういえば https://turingcomplete.fm/5 の時に「MJITについてどう思うか聞いておいて下さい」とかリクエストしておいたのに聞いてくれなかったのであった。
https://k0kubun.hatenablog.com/entry/ruby26-jit
すごいことするな、と思ったのはその手法で、 C 生成して dlopen という、よく雑談とかで言う話ではあるけど、実際広く使われる用途で使われたのは見たことが無かった(ICFPCとかでは見たことがある)ので、すごいなと。
一方で、 dlopen たくさんすると、いくつかの意味でオーバヘッドがかかると思われるため、あとでマイクロベンチに出ないところで大変だったりするだろうなぁ……特にメモリのローカリティ的な、とか思いつつ聞いていると、やはりメモリのキャッシュヒット率が減りはじめると悪い影響が……という話になりました。一つ一つの C レベル関数は恐らく小さいのではないかな、と思っていたので、コードサイズにして例えば 100-1000 バイトくらいの関数のために、 dlopen すると少なくとも必要であろう r-x の .text ページと GOT のための r-- (or rw-) のせいで 8192 バイトを使うことになるのではないかなぁ……と思っていたのでした。
Ruby Kaigi 中に質問したのですが、「一つの関数ごとに最低 8 or 12kB 使うかな……」と思っていたところに「2MB/method！」みたいなスライドを見て、なんじゃそれと思ったからでした。あとで スライド をよく眺めると、 .text と .rodata の間のいじれないやつもカウントしてただけと気付きました。 2MB の仮想アドレスを取っちゃうのもどうなんだって話はあるかもしれないですが、それより3つのページに分割されるのが本質的な問題だと思います。かつ、 MJIT の吐いてるコードを見る限り .data と .rodata は使わなさげなので、実際に触るページは .text 用のやつと .got のやつで2枚だけでないかと思います。
さて、この問題についての正しい解決策は、適切な単位で複数のメソッドをまとめてコンパイルする、というものじゃないかと思います。でかつそれは提案されていた手法なので良いと思います。とはいえ .got のために .so 一つごとに無駄に 4kB 使うというのもなぁ……などとも思います。で、 .got と .text をまとめて同じページに突っ込んでくれそうなリンカオプション無いか……と探したり(なかった)、そもそも RELRO て .got を RX にすることできるの……とローダ眺めたり(できなかった)しました。
なーんていうことを考えてから、とりあえずムダをはぶくだけなら .so をローダに読ませるのではなくて、 .o を自力で適当にロードすればいいよね、ということで、そういうものをでっちあげました。
https://github.com/shinh/ruby/tree/objfcn
まあ……使いやすいものではないと思います。本質的に MJIT のような .so を読む以外の手法で書かれた JIT エンジンにある問題ですが、やはりデバッグは大変ですし、自分でちゃんと空いたメモリを解放するとかも面倒ですし(現状1GB固定アロケートするモードと遅い方法)、まあそんなこんな……
ただ、 C コード吐いてコンパイルしてロードする、って方針が変わらないのであれば、ロードに関しては最速な方法だと思うので、もっと適切な方法であろう、複数のコードをまとめてコンパイルする、という方法で理論限界に近付いてるかどうかは、私のコードと比較すれば評価できるのではないかと思っています。
あと最初にがーと書いたコードは2つクラッシュするバグがあって、それぞれなるほどなあと思ったので書いておきます。
一つ目は mmap を前もってする際に PLT/GOT のために生成するコードのサイズを計算に入れてない、というものでした。これは tinycc の時もどうしたもんかと思った記憶がありました……
二つ目はセクションヘッダに指定されてるアラインメントを適切に取っていない、というものでした。具体的には SSE 命令で data 領域を読んだりするコードの SSE アラインメントが壊れてる、という話でした。なんか低レイヤなとこいじってると SSE アラインメントは必ずバグりますね。スタックがアライン取れてない状態で printf 呼んで死んだりとか……
とりとめもないですが、こんな方法を MRI で採用すべきとは思ってないのですが、ただこの手法の JIT エンジンの持つ、いくつかあるオーバーヘッド源の一つであろう、メモリがページ境界で分断されてしまってローカリティが良くない、というやつがどのくらい悪さをしてるかの評価程度には使えるのではないかと思っています。